[DES] Thuật toán mã hóa và giải mã DES

Bài viết này giới thiệu về thuật toán mã hóa và giải mã dữ liệu DES (Data Encryption Standard). Đây là thuật toán mã hóa dữ liệu được công bố 25/10/1999 trong tài liệu về chuẩn xử lý thông tin liên bang Hoa Kỳ FIPS 46-3.

1. Một số thuật ngữ sử dụng

• Encipher - Bộ mã hóa
• Decipher - Bộ giải mã
• Plaintext - Bản rõ là dữ liệu gốc chưa được mã hóa
• Ciphertext - Bản mã là dữ liệu đã dược mã hóa
• Key - khóa mã là một giá trị được sử dụng để mã hóa và giải mã
• Round key - khóa vòng là những giá trị trung gian được tạo ra từ khóa mã trong suốt quá trình mã hóa và giải mã

2. Thuật toán mã hóa dữ liệu DES – Encipher

2.1 Lưu đồ thuật toán mã hóa

Thuật toán DES được sử dụng để mã hóa và giải mã các block (khối) dữ liệu 64 bit dựa trên một key (khóa mã) 64 bit. Chú ý, các block được đánh số thứ tự bit từ trái sang phải và bắt đầu từ 1, bit đầu tiên bên trái là bit số 1 và bit cuối cùng bên phải là bit số 64. Quá trình giải mã và mã hóa sử dụng cùng một key nhưng thứ tự phân phối các giá trị các bit key của quá trình giải mã ngược với quá trình mã hóa.

Một block dữ liệu sẽ được hoán vị khởi tạo (Initial Permutation) IP trước khi thực hiện tính toán mã hóa với key. Cuối cùng, kết quả tính toán với key sẽ được hoán vị lần nữa để tạo ra , đây là hoán vị đảo của hoán vị khởi tạo gọi là (Inverse Initial Permutation) IP-1. Việc tính toán dựa trên key được định nghĩa đơn giản trong một hàm f, gọi là hàm mã hóa, và một hàm KS, gọi là hàm phân phối key (key schedule). Hàm KS là hàm tạo ra các khóa vòng (round key) cho các lần lặp mã hóa. Có tất cả 16 khóa vòng từ K1 đến K16.

Hình 1. Giải thuật mã hóa DES

2.2 Hoán vị khởi tạo - IP

Hoán vị là thay đổi ví trí các bit trong một chuỗi giá trị nhưng không làm thay đổi giá trị của các bit này. Đây là bước đầu tiên trong quy trình mã hóa dữ liệu. 64 bit dữ liệu đầu vào, gọi là plaintext, sẽ được hoán vị theo bảng mô tả sau đây.

Hình 2. Sơ đồ hoán vị khởi tạo, ký hiệu IP

Chuỗi bit đầu vào được đánh số từ 1 đến 64 (tính từ trái qua phải). Sau đó, các bit này được thay đổi vị trí như sơ đồ IP, bit số 58 được đặt vào vị trí đầu tiên, bit số 50 được đặt vào vị trí thứ 2. Cứ như vậy, bit thứ 7 được đặt vào vị trí cuối cùng. 

Sau hoán vị, chuỗi bit mới được phân ra làm hai đoạn, mỗi đoạn 32 bit để bắt đầu vào quy trình tính toán mã hóa với key. Đoạn bên trái ký hiệu là L, đoạn bên phải ký hiệu là R. Đoạn L gồm các bit từ bit số 1 đến bit số 32, đoạn R gồm các bit từ bit số 33 đến bit số 64. Đoạn L của lần tính toán sau sẽ chính là đoạn R của lần tính toán trước. Đoạn R của lần tính toán sau sẽ được tính từ đoạn R trước đó qua hàm mã hóa f(R, K) rồi XOR với đoạn L của lần tính trước đó.

2.3 Hàm mã hóa f(R,K)

Hình 3. Tính toán hàm mã hóa f(R,K)

Đầu tiên, 32 bit của đoạn R được đánh số từ 1 đến 32 theo thứ tự từ trái qua phải. Giá trị này sẽ được chuyển đổi thông qua bảng tra E để tạo thành một giá trị 48 bit. Bit đầu tiên trong chuỗi giá trị 48 bit là bit số 32 của R, bit thứ 2 là bit số 1 của R, bit thứ 3 là bit số 2 của R và bit cuối cùng là bit số 1 của R.

Hình 4. Bảng tra E

Sau khi tra bảng E, giá trị 48 bit được XOR với 48 bit của khóa vòng (cách tạo ra khóa vòng 48 bit sẽ được trình bày sau). Kết quả phép XOR được chia làm 8 block được đánh số từ 1 đến 8 theo thứ tự từ trái qua phải, mỗi block 6 bit. Mỗi block sẽ được biến đổi thông qua các hàm lựa chọn riêng biệt. Tương ứng với 8 block sẽ có 8 hàm chuyển đổi (selection function) riêng biệt là S1, S2, S3, S4, S5, S6, S7 và S8.

Hình 5. Các hàm S (selection fuction)

Việc chuyển đổi giá trị của các hàm S1, S2, ..., S8 được thực hiện bằng cách tách block 6 bit thành hai phần. Phần thứ nhất là tổ hợp của bit đầu tiên và bit cuối cùng của block để tạo thành 2 bit chọn hàng của bảng S, bảng S có 4 hàng được đánh số từ 0 đến 3 theo thứ tự từ trên xuống. Phần thứ 2 là 4 bit còn lại dùng để chọn cột của bảng S, bảng S có 16 cột được đánh số từ 0 đến 15 theo thứ tự từ trái qua phải. Như vậy, với mỗi block 8 bit ta chọn được 1 giá trị trong bảng S. Giá trị này nằm trong khoảng từ 0 đến 15 sẽ được quy đổi thành chuỗi nhị phân 4 bit tương ứng. Các chuỗi nhị phân có được sau khi chuyển đổi từ S1 đến S8 sẽ được ghép lại theo thứ tự từ trái qua phải để tạo thành một giá trị 32 bit.

Ví dụ về việc thực hiện chuyển đổi hàm S, giả sử, giá trị block 6 bit đầu tiên là 011011. Ta tách chuỗi này ra làm hai tổ hợp giá trị là 01 (bit đầu tiên và bit cuối cùng) và 1101 (4 bit ở giữa). Hai tổ hợp này được dùng để chọn hàng và cột tương ứng như hình minh họa sau:

Hình 6. Minh họa việc sử dụng hàm S1

Tổ hợp 01 sẽ chọn hàng 1, tổ hợp 1101 sẽ chọn cột 13 và kết quả trả về là 5 có giá trị nhị phân 4 bit là 0101.

Qua bước chuyển đổi với các hàm lựa chọn S, kết quả thu được là một giá trị 32 bit. Giá trị này được đưa qua một hàm hoán vị P để tạo ra giá trị hàm f.

Hình 7. Hoán vị P trong thuật toán tính hàm mã hóa f(R,K)

Giá trị 32 bit thu được từ các chuyển đổi với hàm lựa chọn S sẽ được đánh số từ 1 đến 32 theo thứ tự từ trái qua phải.

Theo bảng hoán vị P, bit đầu tiên sau hoán vị sẽ là bit số 16, bit thứ 2 sẽ là bit số 7 và bit cuối cùng sẽ là bit số 25. Hàm tính toán mã hóa f(R, K) được định nghĩa như sau:

Trong đó: 

• P(): là phép hoán vị P 
• Sn: là phép chuyển đổi block n (n chạy từ 1 đến 8) với hàm lựa chọn S 
• Bn: là block 6 bit thứ n (n chạy từ 1 đến 8). Block này lấy từ phép toán XOR giữa khóa vòng K và giá trị hàm E(R)
• E(R): là hàm chuyển đổi giá trị R 32 bit thành giá trị 48 bit

2.4 Tính khóa vòng - KS

Một key có 64 bit nhưng chỉ có 56 bit được sử dụng để thực hiện tính toán giá trị khóa vòng. Key được chia làm 8 byte. Các bit ở vị trí 8, 16, 32, 40, 48, 56 và 64 là các bit parity được sử dụng để kiểm tra độ chính xác của key theo từng byte vì khi key được phân phối trên đường truyền đến bộ mã hóa giải mã thì có thể xảy ra lỗi. Parity được sử dụng là parity lẻ (odd parity).

Hình 8. Thuật toán tính khóa vòng

Key gốc sẽ được thực hiện hoán vị lựa chọn PC-1. Key được đánh số từ 1 đến 64 theo thứ tự từ trái qua phải.

Hình 9. Bảng hoán vị lựa chọn PC-1

Bảng hoán vị lựa chọn PC-1 có hai phần. Phần đầu dùng để xác định giá trị C0 và phần sau dùng để xác định giá trị D0. Theo bảng trên thì C0 là chuỗi bit có thứ tự là 57, 49, 41, ..., 36 lấy từ key gốc, D0 là chuỗi bit có thứ tự là 63, 55, 47, ..., 4 lấy từ key gốc.

Sau khi xác định được giá trị ban đầu để tính key là C0 và D0 thì các khóa vòng Kn (với n từ 1 đến 16) sẽ được tính theo nguyên tắc giá trị của khóa vòng thứ n sẽ được tính từ giá trị khóa vòng thứ n-1.

Trong đó Cn và Dn được tạo từ Cn-1 và Dn-1 bằng cách dịch trái các giá trị này với số bit được quy định trong bảng sau đây:

Hình 10. Bảng quy định số bit dịch trái khi tính khóa vòng

Ví dụ, theo bảng trên, C3 và D3 có được từ C2 và D2 bằng cách dịch trái 2 bit. Hay C16 và D16 có được từ C15 và D15 bằng cách dịch trái 1 bit. Dịch trái ở đây được hiểu là quay trái như minh họa sau đây:

Hình 11. Minh họa phép dịch trái khi tính khóa vòng

Sau khi tính được Cn và Dn thì chuỗi CnDn sẽ được đánh số từ 1 đến 56 theo thứ tự từ trái sang phải và được hoán vị lựa chọn lần 2 theo bảng hoán vị PC-2.

Hình 12. Bảng hoán vị lựa chọn PC-2

Như vậy bit đầu tiên của khóa vòng Kn là bit số 14 của chuỗi CnDn, bit thứ 2 là bit số 17 của chuỗi CnDn và bit cuối cùng là bit số 32 của chuỗi CnDn.

2.5 Hoán vị khởi tạo đảo IP-1

Đây là bước cuối cùng để tạo ra giá trị mã hóa. Giá trị của lần lặp mã hóa cuối cùng sẽ được hoán vị khởi tạo đảo IP-1 và tạo ra giá trị mã hóa plaintext.

Hình 13. Bảng hoán vị khởi tạo đảo IP-1

2.6 Ví dụ về mã hóa DES

Giả sử ta có dữ liệu cần mã hóa và key là: 

• M = 00123456789abcde (Hex) = 0000 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1111 
• K = 0133457799bbcdff (Hex) = 0000 0001 0011 0011 0100 0101 0111 0111 1001 10001 1011 1011 1100 1100 1111 1111

Từ hai đầu vào này, giá trị của từng bước tính toán mã hóa DES sẽ được minh họa chi tiết sau đây.

2.6.1 Hoán vị khởi tạo – IP

Thông điệp M được đánh số vị trí bit từ trái qua phải như sau:

Sắp xếp lại thứ tự các bit của M theo bảng hoán vị IP, kết quả có được sau bước này là:

IP(M) = 98fecc00e054f0aa (Hex) = 1001 1000 1111 1110 1100 1100 0000 0000 1110 0000 0101 0100 1111 0000 1010 1010

2.6.2 Tính toán giá trị các khóa vòng – KS

Để tính toán hàm mã hóa f, chúng ta cần có giá trị khóa cho từng lần lặp mã hóa. Key ban đầu được đánh số thứ tự bit từ trái qua phải như sau:

Sau khi sắp xếp các bit theo bảng hoán vị PC-1 ở Hình 1‑8, kết quả thu được là hai giá trị đầu như sau: 

• C0 = f0ccaab (Hex) = 1111 0000 1100 1100 1010 1010 1011 
• D0 = aaccf0a (Hex) = 1010 1010 1100 1100 1111 0000 1010 

Để tính khóa vòng đầu tiên K1 thì C0 và D0 sẽ được dịch (quay) trái 1 bit. Giá trị thu được sau khi dịch trái là: 

• C1 = e199557 (Hex) = 1110 0001 1001 1001 0101 0101 0111 
• D1 = 5599e15 (Hex) = 0101 0101 1001 1001 1110 0001 0101 

Hai chuỗi C1 và D1 được ghép lài thành một chuỗi 56 bit là e1995575599e15. Chuỗi này được hoán vị bằng bảng PC-2 ở Hình 1‑11 để được giá trị khóa vòng 48 bit thứ nhất K1. 

• K1 = 1b02efdb49a5 (Hex) 

Để tính khóa vòng K2 thì lấy C1 và D1 dịch trái với số lượng bit theo bảng ở Hình 1‑9, rồi lấy kết quả hoán vị theo bảng PC-2. Quá trình cứ tiếp tục cho đến khóa vòng cuối cùng là K16. Kết quả các khóa vòng 48 bit thu được là:

• K2 = 69aed925ae66 (Hex) 
• K3 = 55fc8ab4acd2 
• K4 = 72add2ad8657 
• K5 = 7cec071fe6c2 
• K6 = 63a51e3cc545 
• K7 = 6c84b78ae4c6 
• K8 = f7883aece781 
• K9 = c0dbeb27b839 
• K10 = b1f347631d76 
• K11 = 215fc30d89be 
• K12 = 7171f5455cd5 
• K13 = 95c5d14b80fd 
• K14 = 5743b783đ8d 
• K15 = bf91850a17b5 K16 = cb3d0bbc7072

2.6.3 Tính hàm mã hóa f(R,K)

Sau bước hoán vị khởi tạo IP, giá trị IP(M) sẽ được tách làm hai phần là: 

• R0 = e054f0aa (Hex) = 1110 0000 0101 0100 1111 0000 1010 1010 
• L0 = 98fecc00 (Hex) = 1001 1000 1111 1110 1100 1100 0000 0000 

Giá trị 32 bit của R0 được tra qua bảng E để tạo ra một giá trị 48 bit. 

• E(R0) = 7002a97a1555 (Hex) 

Giá trị này được XOR với khóa vòng thứ nhất K1 và được kết quả 

• XOR(E(R0), K1) = 6b0046a15cf0 (Hex)

Giá trị trên được chia thành 8 nhóm theo thứ tự từ trái qua phải, mỗi nhóm 6 bit để đưa đến các bảng S.

Hình 14. Ví dụ về tra bảng S

Các giá trị đầu ra sau bước tra các bảng S sẽ được ghép lại theo thứ tự từ S1 đến S8 để được 1 giá trị 32 bit. 

• S1()S2()S3()S4()S5()S6()S7()S8() = 10010101110100111010110101010000 = 95d3ad50 (Hex) 

Giá trị này được hoán vị bằng bảng P để cho ra giá trị của hàm f. 

• f(R0,K1) = 97d1619a (Hex) = 1001 0111 1101 0001 0110 0001 1001 1010 

Tương tự, ta có giá trị hàm f tại các vòng lặp mã hóa còn lại như sau: 

• f(R1,K2) = 88488d0b (Hex) 
• f(R2,K3) = da3b2692 
• f(R3,K4) = f44950b2 
• f(R4,K5) = d83237fd 
• f(R5,K6) = afc43b25 
• f(R6,K7) = 4e5123a2 
• f(R7,K8) = 6cfdecb8 
• f(R8,K9) = fb0600b1 
• f(R9,K10) = d51508e4 
• f(R10,K11) = fcf67146 
• f(R11,K12) = 704fa3a5 
• f(R12,K13) = 7bfe2806 
• f(R13,K14) = 65fc7a48 
• f(R14,K15) = 513f1d11 f(R15,K16) = cbf5252d

2.6.4 Giá trị tại mỗi vòng lặp mã hóa

Giá trị của hàm f(R,K) được sử dụng để tính giá trị Rn và Ln tại mỗi vòng lặp mã hóa theo công thức:

Thay vào công thức trên ta có các kết quả như sau:

2.6.5 Hoán vị khởi tạo đảo IP-1 

Giá trị R16 và L16 của vòng lặp mã hóa cuối cùng sẽ được ghép lại thành một chuỗi 64 bit để thực hiện hoán vị theo bảng IP-1.

Kết quả của phép hoán vị này chính là giá trị mã hóa (ciphertext) cần tính.

IP-1(R16, L16) = 1abff69d5a93e80b (Hex) = 0001 1010 1011 1111 1111 0110 1001 1101 0101 1010 1001 0011 1110 1000 0000 1011

3. Thuật toán giải mã dữ liệu DES

Các bước của quá trình giải mã dữ liệu được thực hiện tương tự như quá trình mã hóa dữ liệu. Trong quá trình giải mã có một số thay đổi như sau: 

• Đầu vào lúc này là dữ liệu cần giải mã (ciphertext) và đầu ra là kết quả giải mã được (plaintext).
• Khóa vòng sử dụng trong các vòng lặp giải mã có thứ tự ngược với quá trình mã hóa. Nghĩa là, tại vòng lặp giải mã đầu tiên, khóa vòng được sử dụng là K16. Tại vòng lặp giải mã thứ 2, khóa vòng được sử dụng là K15, và tại vòng lặp giải mã cuối cùng thì khóa vòng được sử dụng là K1.

Hình 16. Quá trình giải mã dữ liệu DES

Các bạn có thể trao đổi thêm ở dưới vài viết hoặc thông qua mục liên hệ ở cột ngoài cùng bên phải của trang.

Lịch sử cập nhật:
1) 2019.10.21 - Sửa link các hình ảnh
2) 2020.04.19 - Sửa chuỗi binary (4 bit cuối) của C1 từ 1110 thành 0111 như góp ý dưới comment

Đọc thêm

[Multi-clock Design] Bài 2 - Kỹ thuật đồng bộ tín hiệu điều khiển giữa các miền clock bất đồng bộ

Bài này mô tả các kỹ thuật được sử dụng để đồng bộ tại giao tiếp của các miền clock bất đồng bộ. Mỗi trường hợp cụ thể, kỹ thuật sử dụng để thiết kế mạch đồng bộ sẽ khác nhau nhưng đều nhằm hai mục đích chính là hạn chế sự lan truyền của trạng thái bất ổn định (metastability) và lấy mẫu đúng giá trị mong muốn ở ngõ vào bất đồng bộ.

Trước khi đọc bài này, các bạn hãy đọc kỹ bài viết sau vì nhiều khái niệm sử dụng sẽ không được nhắc lại.

http://nguyenquanicd.blogspot.com/2017/08/multi-clock-design-bai-1-ky-thuat-thiet.html

1. Kỹ thuật đảm bảo độ rộng tín hiệu bất đồng bộ

1.1 Đảm bảo độ rộng tín hiệu dựa trên tỷ lệ của tần số xung clock

Việc đồng bộ tín hiệu 1 bit sử dụng 2 hoặc nhiều Flip-Flop (FF) chỉ đảm bảo hạn chế trạng thái bất ổn định (metastability state) lan truyền trong thiết kế chứ không đảm bảo nhận (lấy mẫu) đúng dữ liệu ngõ vào mong muốn ở ngõ vào do 2 yếu tố:

1. Cạnh tích cực (trong bài này minh họa theo cạnh lên xung clock) của xung clock nhận chưa chắc bắt đúng được vị trí có giá trị mong muốn của ngõ vào vì ngõ vào thay đổi bất cứ khi nào không phụ thuộc vào xung clock nhận.
2. Cạnh tích cực của clock nhận có thể bắt được giá trị thay đổi của ngõ vào nhưng có thể vi phạm định thời (timing) và gây ra trạng thái bất ổn định làm cho giá trị ngõ ra có thể ổn định về một giá trị logic không xác định trước

Do đó, việc sử dụng mạch đồng bộ mắc nối tiếp dùng nhiều FF cần có những tín toán và ràng buộc thêm để đảm bảo lấy đúng được dữ liệu ngõ vào mong muốn. Hình sau sẽ được dùng để phân tích về vấn đề này.

Hình 1. Mạch đồng bộ tín hiệu 1 bit dùng 2 FF

Điểm chính của vấn đề là mối liên hệ giữa độ rộng tín hiệu d_outa và xung clock clk_b. d_outa là tín hiệu thay đổi giá trị theo xung clock clk_a và bất đồng bộ với xung clock clk_b.

Trường hợp xung clock clk_a có tần số thấp hơn tần số xung clock clk_b, độ rộng* tối thiểu của tín hiệu d_outa nhỏ hơn chu kỳ xung clock clk_b. Việc lấy mẫu đúng được dữ liệu d_outa gần như là bất khả thi.

Hình 2. Độ rộng tín hiệu ngõ vào nhỏ hơn chu kỳ xung clock nhận làm cho xung clock clk_b không thể lấy mẫu đầy đủ các giá trị ở ngõ vào d_outa

Trường hợp xung clock clk_a cùng tần số với xung clock clk_b, lúc này độ rộng tín hiệu d_outa bằng độ rộng xung clk_b nhưng vẫn không đảm bảo clk_b có thể lấy mẫu đúng d_outa vì độ lệch pha giữa clk_a và clk_b là không biết trước nên tín hiệu d_outa sinh ra hoàn toàn có thể vi phạm định thời clk_b.

Hình 3. Độ rộng tín hiệu ngõ vào d_outa bằng chu kỳ xung clock clk_b vẫn không đảm bảo lấy mẫu đúng dữ liệu

Tổng quát, nếu độ rộng tín hiệu d_outa, ký hiệu td_outa, nhỏ hơn hoặc bằng tổng chu kỳ clk_b (Tclk_b) cộng setup time (tsu) và hold time (th) của clk_b thì vấn đề xảy ra giống như trường hợp hình 3.

Xét trường hợp sau:

td_outa > Tclk_b + tsu + th

Hình 4 (A) minh họa độ rộng tối thiểu của ngõ vào bất đồng bộ d_outa lớn hơn Tclk_b + tsu + th.

Hình 4 (B) minh họa sự kiện chuyển trạng thái từ mức 0 lên mức 1 của d_outa bị vi phạm timing và làm cho d_outb đạt đến giá trị không mong muốn ở cạnh lên xung clock đầu tiên nhưng ở cạnh xung clock clk_b thứ 2, d_outb cập nhật đúng giá trị ngõ vào mong muốn. Đến cạnh xung clock thứ 3, ngõ ra mạch đồng bộ là d_outc sẽ thể hiện được giá trị mới của ngõ vào d_outa.

Hình (C) thể hiện việc 1 giá trị logic của ngõ vào d_outa có thể được thể hiện ở ngõ ra trong 2 chu kỳ dù giá trị ngõ vào không tồn tại trong khoảng thời gian 2 chu kỳ. Tuy nhiên, bất cứ thay đổi nào của ngõ vào d_outa đều được thể hiện ở ngõ ra d_outc của mạch đồng bộ:

• d_outa chuyển từ mức 0 lên mức 1 thì chắc chắn d_outc cũng sẽ chuyển từ mức 0 lên mức 1
• d_outa chuyển từ mức 1 xuống mức 0 thì chắc chắn là d_outc cũng sẽ chuyển từ mức 1 lên mức 0

Hình 4. Mạch đồng bộ bắt được tất cả các sự kiện đổi trạng thái ngõ vào khi độ rộng tín hiệu bất đồng bộ d_outa lớn hơn Tclk_b + tsu + th

Tóm lại, nếu độ rộng tín hiệu bất đồng bộ lớn hơn Tclk_b + tsu + th thì mạch đồng bộ luôn bắt được tất cả các sự kiện chuyển trạng thái, từ 0 lên 1 hoặc từ 1 xuống 0, của d_outa. Chú ý, mạch đồng bộ phát hiện và báo đúng các sự kiện chuyển trạng thái chứ không phải thể hiện đúng độ rộng của giá trị ngõ vào.

Ví dụ, nếu miền xung clock clk_a cần phát một tín hiệu điều khiển bật/tắt (ON/OFF) một chức năng nào đó sang miền xung clock clk_b với chu kỳ các xung clock biết trước thì nó có thể sử dụng cạnh lên để ON, cạnh xuống để OFF. Tín hiệu này cần duy trì với độ rộng như ràng buộc trên đây. Giả sử, tần số clk_a là 75 Mhz ứng với chu kỳ 13.333ns; tần số xung clock clk_b là 25 Mhz ứng với chu kỳ 40ns; setup time của D-FF trên clk_b là 1ns, hold time của D-FF trên clk_b là 2ns. Để miền clock clk_b có thể bắt được các sự kiện điều khiển từ clk_a thì d_outa có độ rộng như sau:

td_outa > 40 + 1 + 2 (ns)

td_outa > 43 (ns)

d_outa có thể được thiết kế bằng cách duy trì trong 4 xung clock clk_a ứng với độ rộng:

td_outa ≈ 4 x 13.333 ≈ 53.333

Do độ rộng của một giá trị logic ở ngõ ra mạch đồng bộ (d_outc) không cố định do ảnh hưởng của hiện tượng bất ổn định nên một mạch phát hiện cạnh được sử dụng để phát hiện sự kiện chuyển trạng thái và báo hiệu trong 1 chu kỳ xung clock.

Hình 5. Mạch phát hiện cạnh của tín hiệu ngõ ra mạch đồng bộ

Hình 6. Dạng sóng minh họa hoạt động của mạch hình 5

Quan sát dạng sóng ví dụ, khi xảy ra trạng thái bất ổn định trên d_outb, tùy vào giá trị ổn định sau đó của d_outb là "0" hoặc "1" mà ngõ ra mạch đồng bộ là d_outc sẽ khác nhau làm cho ví trí báo hiệu của xung falling_edge sẽ khác nhau.

Cách đảm bảo độ rộng tín hiệu trên đây yêu cầu cần biết trước tần số xung clock nhận để miền phát có thể tạo được độ rộng xung phù hợp. Nếu miền xung clock phát chỉ tạo một độ rộng xung cố định thì phải giới hạn tần số miền xung clock nhận cho phù hợp.

1.2 Đảm bảo độ rộng tín hiệu bất đồng bộ bằng phương pháp hồi tiếp

Phương pháp này sử dụng ngõ ra mạch đồng bộ của miền clock nhận để hồi tiếp lại miền xung clock phát. Miền clock phát sẽ nhận tín hiệu hồi tiếp, đồng bộ lại theo xung clock miền phát để điều khiển độ rộng tín hiệu gửi sang miền clock nhận.

Hình 7. Đảm bảo độ rộng xung bằng phương pháp hồi tiếp

Hình trên minh họa việc miền xung clock clk_a (miền phát) gửi tín hiệu req tích cực mức "1" sang miền xung clock clk_b (miền nhận). Tín hiệu req sau khi được đồng bộ ở miền xung clock clk_b để tạo ra tín hiệu sync_req thì sync_req sẽ được hồi tiếp lại miền xung clock clk_a. Tín hiệu hồi tiếp sẽ được đồng bộ lại theo xung clock clk_a trước khi đi qua khối tạo tín hiệu xóa req là REG_CLR. Như vậy, khi req tích cực nó sẽ duy trì mức tích cực đến khi khối REQ_CLR nhận được đúng giá trị req đã hồi tiếp về, nghĩa là đã đảm bảo miền xung clock clk_b nhận được req, thì mới thôi tích cực req.

Phương pháp hồi tiếp này không cần quan tâm đến mối liên hệ giữa tần số clk_a và clk_b vì độ rộng tín hiệu req ở miền xung clock clk_a được duy trì cho đến khi biết chắc chắn miền xung clock clk_b đã nhận req.

2. Đồng bộ nhiều tín hiệu điều khiển

Đồng bộ nhiều tín hiệu giữa hai miền clock bất đồng bộ có một số điểm cần phải lưu ý hơn so với việc đồng bộ một tín hiệu như đã trình bày trên đây. Việc đồng bộ nhiều tín hiệu không phải chỉ cần dùng 2 hay nhiều FF mắc nối tiếp là được. Một số ví dụ sau đây sẽ giải thích tại sao việc chỉ dùng 2 hay nhiều FF mắc nối tiếp là không đảm bảo.

2.1 Đồng bộ hai tín hiệu hoạt động song song

Ví dụ, một giao tiếp cần truyền hai tín hiệu điều khiển từ miền xung clock clk_a sang miền xung clock clk_b như sau:

• sel là tín hiệu lựa chọn tích cực mức 1 khi miền clock clk_a cần truyền dữ liệu cho miền clock clk_b
• enable là tín hiệu tích cực mức 1 khi có dữ liệu hợp lệ
• data_in là bus dữ liệu 

Hình 8. Một mạch đồng bộ các tín hiệu điều khiển không đúng

Trong hình trên, hai tín hiệu điều khiển sel và enable được đồng bộ thông qua mạch sử dụng 2 FF. Tại vị trí sel và enable cùng tích cực mức 1, tương ứng với việc sync_sel và sync_en cùng tích cực mức 1 thì dữ liệu sẽ data_in[7:0] sẽ được ghi vào thanh ghi data_reg[7:0]. Đấy là mong muốn của người thiết kế khi thực hiện mạch trên. Tuy nhiên việc đồng bộ như vậy là không đủ để mạch hoạt động chính xác cho dù độ rộng các tín hiệu sel, enable và data đã được đảm bảo như đã trình bày ở mục 1. Ví dụ như trong hình minh họa sau đây, do độ trễ giữa các tín hiệu  khác nhau nên sel vi phạm định thời trước, enable vi phạm định thời sau. Sau trạng thái bất ổn định, giá trị logic ở pre_sel và pre_en có thể đều về "0" làm cho sync_sel và sync_en không cùng một thời điểm như mong muốn và tín hiệu load không được tích cực.

Hình 9. Do độ trễ giữa các tín hiệu khác nhau nên dữ liệu không được nhận ở miền clk_b

Nếu vẫn muốn sử dụng cách đồng bộ này, giải pháp là phải lái hai tín hiệu điều khiển theo một giao thức ràng buộc về mặt định thời sao cho bất cứ vi phạm timing nào xảy ra thì miền xung clock nhận vẫn lấy được dữ liệu đúng. Ví dụ, tín hiệu enable không cùng chuyển trạng thái logic với tín hiệu sel như hình sau đây.

Hình 10. Tạo một giao thức ràng buộc giữa tín hiệu sel và enable

Một giải pháp khác là biến đổi hai hoặc nhiều tín hiệu điều khiển về một tín hiệu nếu có thể trước khi đồng bộ. Ví dụ như hình sau, sel và enable được xử lý AND ở miền xung clock clk_a trước thành tín hiệu load trước khi được đồng bộ qua miền xung clock clk_b. Dù xảy ra vi phạm thì miền clk_b vẫn nhận đúng dữ liệu khi data_in[7:0] được duy trì độ rộng phù hợp. Độ rộng của data_in[7:0] là:

Tdata > 3*Tclk_b + tsu + th

Hình 11. Biến đổi về đồng bộ 1 tín hiệu

2.2 Đồng bộ hai tín hiệu hoạt động tuần tự

Hai tín hiệu điều khiển được tích cực tuần tự trước sau. Tín hiệu load chỉ tích cực khi tín hiệu en1 tích cực trước và ngay sau đó, en2 tích cực. Tuy nhiên, việc sử dụng mạch đồng bộ 2 FF cho từng tín hiệu en1 và en2 cho kết quả không mong muốn khi trạng thái bất ổn định xảy ra như hình sau. Trường hợp này giả sử các tín hiệu ổn định về "0" sau trạng thái bất ổn định.

Hình 12. Hai tín hiệu tuần tự được đồng bộ không đúng

Giải pháp đầu tiên là chuyển về 1 tín hiệu, xử lý tổ hợp tín hiệu ở miền xung clock clk_a trước khi đưa qua miền clk_b như hình sau.

Hình 13. Xử lý 2 tín hiệu hoạt động tuần tự trước khi đồng bộ

Nếu không thể tổ hợp được hai tín hiệu en1 và en2 thành một tín hiệu nhưng en1 và en2 luôn hoạt động tuần tự trước sau như đã mô tả thì chỉ cần đồng bộ một tín hiệu en1 và dịch tín hiệu sau đồng bộ thêm 1 xung clock ở miền clk_b để tạo ra tín hiệu sync_en2 như minh họa dưới đây.

Hình 14. Tạo tín hiệu phù hợp sử dụng phương pháp dịch

2.3 Đồng bộ các tín hiệu được sử dụng cho encoder, MUX hoặc DEMUX

Giả sử một bộ MUX ở miền clock clk_b sử dụng 2 hoặc nhiều tín hiệu điều khiển từ miền clock clk_a. Nếu chỉ đồng bộ tất cả các tín hiệu bằng FF thì encoder không đảm bảo được hoạt động chính xác vì các tín hiệu điều khiển có thể xuất hiện các tổ hợp giá trị không mong muốn. Nguyên nhân là do độ trễ khác nhau trên các tín hiệu hoặc sự xuất hiện của trạng thái bất ổn định.

Hình 15. Ngõ ra bộ MUX xuất hiện giá trị sai khi đồng bộ song song 2 tín hiệu điều khiển

Một giải pháp cho vấn đề này là tạo thêm một tín hiệu cho phép. Tín hiệu này tích cực sau một chu kỳ xung clock clk_b khi sel1 và sel2 chuyển sang giá trị mới và thôi tích cực trước 1 chu kỳ khi sel1 và sel2 chuyển sang giá trị tiếp theo.

Hình 16. Sử dụng tín hiệu cho phép để lấy được giá trị điều khiển chính xác từ sel1 và sel2

Trên đây là một số trường hợp đồng bộ tín hiệu điều khiển giữa hai miền clock bất đồng bộ.

** Nếu có ý kiến cần trao đổi, bạn có thể comment dưới bài viết để cùng nhau hoàn thiện thêm kiến thức.

Lịch sử cập nhật:
2020.01.07 - Sửa link hình ảnh

Đọc thêm

[Multi-clock Design] Bài 1 - Đồng bộ tín hiệu bất đồng bộ

Bài viết này giới thiệu những vấn đề và các kỹ thuật được áp dụng trong thiết kế sử dụng nhiều nguồn clock bất đồng bộ. Một thiết kế an toàn và đơn giản nhất là thiết kế sử dụng một nguồn clock. Tuy nhiên, nhiều vi mạch ngày nay sử dụng rất nhiều nguồn clock khác nhau trong cùng một thiết kế nhằm đạt hiệu quả xử lý cao nhất nhưng vần đảm bảo tiết kiệm năng lượng.

Về các loại thiết kế trong vi mạch số các bạn có thể tham khảo ở bài viết [Basic Knowledge] Phân loại thiết kế trong thiết kế vi mạch số.

1. Trạng thái bất ổn định (Metastability)

Trạng thái bất ổn định chính là vấn đề chính được sinh ra tại các giao tiếp bất đồng bộ. Các kỹ thuật thiết kế đa miền clock bất đồng bộ đều nhằm mục đích tránh, hạn chế trạng thái này hoặc tìm cách "sống chung" với trạng thái này.

Trạng thái bất ổn định sinh ra khi xuất hiện sự vi phạm định thời (timing) giữa các tín hiệu đến và tín hiệu xung clock. Tín hiệu đến ở đây có thể là tín hiệu dữ liệu hoặc tín hiệu set/reset. Vi phạm định thời sẽ làm ngõ ra của Flip-Flop (FF) rơi vào trạng thái bất ổn định và xả ra hiện tượng dao động.

Hình 1. Trạng thái bất ổn định xảy ra trên giao tiếp giữa 2 miền clock bất đồng bộ

Hình 1 minh họa việc trạng thái bất ổn định xảy ra như thế nào. clk_a và clk_b là 2 xung clock bất đông bộ, nghĩa là 2 nguồn xung clock độc lập với nhau. d_outa thay đổi theo cạnh lên xung clock clk_a và vi phạm định thời, vi phạm setup time hoặc hold time, của miền xung clock clk_b. Lúc này, ngõ ra DFFB là d_outb rơi vào trạng thái bất ổn định và bắt đầu dao động. Trong trạng thái dao động, mức logic của d_outb là không xác định. Sau một thời gian khoảng thời gian không xác định, d_outb sẽ trở về trạng thái ổn định là mức "0" hoặc mức "1". Việc d_outb ổn định về trạng thái nào là ngẫu nhiên và không biết trước được.
Trạng thái bất ổn định thường được minh họa như việc thả một quả cầu lên một đỉnh một quả đồi. Nó luôn có xu hướng lăn xuống một trong hai bên sườn đồi và nằm cố định khi xuống đến chân đồi.

Hình 2. Minh họa trạng thái bất ổn định như việc thả một quả bóng trên đỉnh đồi

2. Những nguy hiểm sinh ra do trạng thái bất ổn định

Truyền sai giá trị: đây là nguy hiểm có thể thấy rõ. Xét đoạn thời gian ngõ ra d_outb dao động, đây là đoạn thời gian giá trị d_outb không xác định nếu d_outb tiếp tục được lan truyền trong các mạch tiếp theo thì giá trị logic ở các mạch tiếp theo cũng không chính xác. Thêm nữa, cho dù sau đó d_outb sẽ ổn định nhưng giá trị d_outb chưa chắc là đúng vì giá trị ổn định là "0" hay "1" là ngẫu nhiên. Tất nhiên, việc sai giá trị logic sẽ dẫn đến việc hoạt động sai không kiểm soát được khi lan truyền trong mạch.

Hình 3. Trạng thái bất ổn định sẽ lan truyền các giá trị logic sai trong mạch

Tiêu hao năng lượng lớn: Việc tiêu hao năng lượng lớn trên các cổng logic sinh ra do chuyển mạch (chuyển mức logic). Xét một ví dụ đơn giản về cổng đảo (inverter), khi chuyển mạch, điện áp ngõ vào IN thay đổi, tại thời điểm Vi không xác định rõ mức logic "0" hay "1" dòng điện sẽ tăng đột biến vì hiện tượng ngắn mạch tức thời Vdd-Vss khi cả PMOS và NMOS đều dẫn. Ở hiện tượng bất ổn định, tín hiệu dao động và không xác định rõ mức logic được suy trì trong một khoảng thời gian sẽ làm cho quá trình "ngắn mạch" này kéo dài hơn bình thường. Nếu tín hiệu bất ổn định nối đến càng nhiều các cổng logic (mạch tổ hợp) sẽ làm tiêu hao năng lượng lớn khi nhiều cổng bị "ngắn mạch" cùng lúc.

Hình 4. Mô hình cổng đảo mức CMOS (trái) và mối quan hệ dòng-áp khi chuyển mạch (phải). Ở đây, dòng ID tăng đạt mức cực đại tại điện áp trung gian VM khi hiện tượng "ngắn mạch" xảy ra do cả PMOS và NMOS cùng dẫn

Chính vì những nguy hiểm mà trạng thái bất ổn định mang lại mà khi thiết kế đa miền clock bất đồng bộ, nhiệm vụ chính và quan trọng hàng đầu là:

1. Hạn chế hiện tượng này lan truyền trong mạch
2. Dù hiện tượng này có xảy ra thì chức năng mạch vẫn phải đảm bảo hoạt động đúng.

3. Mạch đồng bộ
Mạch đồng bộ là mạch được sử dụng để đồng bộ các tín hiệu bất đồng bộ. Tín hiệu bất đồng bộ có thể chuyển trạng thái bất cứ lúc nào và không tuân theo định thời của miền clock nhận nó. Tín hiệu bất đồng bộ có nhiều dạng như:

1. Tín hiệu input từ ngoài chip
2. Tín hiệu đến từ một miền clock độc lập với miền clock nhận
3. Tín hiệu giữa các miền clock sử dụng các clock sinh ra từ PLL
4. ....

Hình 5. Minh họa một số trường hợp của tín hiệu bất đồng bộ

Để sử dụng một tín hiệu bất đồng bộ thì trong thiết kế phải có mạch đồng bộ. Mạch đồng bộ có nhiệm vụ lấy mẫu tín hiệu ngõ vào bất đồng bộ và cung cấp một ngõ ra đồng bộ theo xung clock được sử dụng bên trong thiết kế.

Mạch đồng bộ "huyền thoại" là mạch đồng bộ sử dụng 2 FF. Câu hỏi là tại sao lại sử dụng 2 FF?

Hình 6. Mạch đồng bộ tín hiệu 1 bit dùng 2 FF

Mạch đồng bộ dùng 2 FF được sử dụng với mong muốn giải quyết 2 vấn đề sau đây:

1. Ngăn chặn việc truyền trạng thái bất ổn định đến các mạch phía sau
2. Lấy mẫu đúng giá trị logic mong muốn

Hình 7. Sơ đồ dạng sóng mong muốn khi sử dụng mạch đồng bộ 2 FF

Tuy nhiên, vì d_outa có thể vi phạm timing của clk_b bất cứ lúc nào nên d_outb có thể dao động bất cứ lúc nào. Để trạng thái bất ổn định không lan truyền tiếp đến các mạch phía sau thì dao động của d_outb phải xong trước khi vi phạm timing của clk_b, nghĩa là phải ổn định trước thời gian setup của clk_b. Để ngõ ra d_outc mang giá trị chính xác như ngõ vào d_outa thì sau khoảng thời gian dao động, d_outb phải ổn định về logic 1. Theo những gì đã trình bày về trạng thái bất ổn định trên đây thì mạch dùng 2 FF không có đảm bảo được cả 2 mong muốn đã đề ra vì:

1. Trạng thái bất ổn định có thể kéo dài hơn 1 chu kỳ xung clock clk_b nên trạng thái bất ổn định có thể lan truyền tiếp đến FF thứ 2 ở ngõ ra d_outc
2. d_outb có thể ổn định về "0" hoặc "1" chứ không luôn là "1" nên ngõ ra d_outc chưa chắc có được giá trị logic mong muốn

4. Thời gian trung bình giữa các lỗi MTBF

Lý thuyết về thời gian trung bình giữa các lỗi MTBF (Mean Time Between Failures) sẽ giải thích vì sao 2 FF có thể hạn chế được trạng thái bất ổn định lan truyền trong thiết kế.

MTBF cung cấp cách ước lượng khoảng thời gian giữa các lần xảy ra trạng thái bất ổn định làm cho thiết kế bị lỗi. Lỗi này gọi là lỗi đồng bộ (synchronous failure).

Như đã trình bày ở trên, thời gian để thoát khởi trạng thái bất ổn định là không xác định. Gọi thời gian mong muốn để thoát khỏi trạng thái bất ổn định là tMET thì xác xuất để trạng thái bất ổn định không thể kết thúc trong khoảng thời gian này là:

Trong đó:

• tMET (resolution time) là thời gian yêu cầu để tín hiệu đạt trạng thái ổn định sau khi rơi vào trạng trạng thái bất ổn định.
• C2 (decay time constant) là hằng số thời gian suy hao được xác định bởi các thông số điện của FF. 

Hình 8. Minh họa về thời gian tMET

Bên cạnh đó, tốc độ trung bình (average rate) để FF rơi vào trạng thái bất ổn định được tính như sau:

Trong đó:

• C1 (susceptible time window) là hằng số thời gian phụ thuộc vào thông số điện của FF. Đây là khoảng thời gian mà nếu có sự thay đổi của ngõ vào thì ngõ ra FF sẽ rơi vào trạng thái bất ổn định.
• fCLK là tần số clock miền nhận tín hiệu bất đồng bộ. Như minh họa hình 6, fclk là tần số của clk_b
• fDATA là tần số thay đổi mức logic của tín hiệu ngõ vào hay số lần tín hiệu ngõ vào thay đổi giá trị trong 1 giây. Ví dụ, theo hình 6, tín hiệu dữ liệu d_outa thay đổi theo xung clock clk_a nên fDATA = fclk_a.

Rmeta biểu thị số lần FF có thể sẽ rơi vào trạng thái bất ổn định trong 1 giây. Như vậy, số lỗi đồng bộ trung bình trong 1 giây là:

Thời gian trung bình giữa các lỗi MTBF ứng với một một giá trị tMET mong muốn là:

MTBF sẽ được dùng để đáng giá một mạch đồng bộ trong thiết kế có đáp ứng được yêu cầu hay không. Ví dụ, một FF có thông số C1 là 0,1 ns, thông số C2 là 0,5 ns, tần số clock hệ thống là fCLK = 50 Mhz và tốc độ dữ liệu là fDATA = 10 Mhz. Ở đây, tần số clock hệ thống là 50 Mhz, tương ứng chu kỳ là 20 ns. Chúng ta kỳ vọng tMET < (tCLK - setup time), tức là tín hiệu được mong muốn sẽ ổn định trước thời gian setup của xung clock fCLK nếu xảy ra trạng thái bất ổn định. Hình sau là bảng tính MTBF ứng với từng trường hợp kỳ vọng tMET từ 0ns đến 19ns.

Hình 9. Tính toán giá trị MTBF

Qua ví dụ trên, chúng ta có thể thấy thời gian dự trữ dành cho trạng thái bất ổn định càng lớn, tức tMET càng lớn, thì thời gian giữa 2 lần xuất hiện lỗi đồng bộ càng dài, tức MTBF càng lớn. Đồng nghĩa với việc xác suất xuất hiện lỗi đồng bộ càng thấp. Ví dụ, nếu kỳ vọng lỗi đồng bộ ngay lập tức có thể ổn định (tMET = 0), nghĩ là không có khoảng thời gian dự trữ cho trạng thái bất ổn định, thì cứ mỗi 0.02ms là có thể xuất hiện một lỗi đồng bộ. Nếu tMET tăng lên 19ns thì khoảng cách trung bình giữa 2 lỗi đồng bộ là khoảng 20202 năm. Tuy nhiên, MTBF là thời gian "trung bình" nên trên thực tế, không phải cứ sau 20202 năm mới xuất hiện một lỗi đồng bộ mà khoảng cách giữa 2 lần xuất hiện lỗi đồng bộ có thể ngắn hoặc dài hơn 20202 năm nhưng trong suốt quá trình hoạt động của thiết kế, khoảng cách trung bình là 20202 năm.

Như vậy để hạn chế lỗi đồng bộ thì MTBF phải đủ lớn để đáp ứng nhu cầu của ứng dụng thực tế và mạch đồng bộ là mạch có vai trò làm tăng MTBF để hạn chế tối đa sự xuất hiện lỗi đồng bộ.

Bên cạnh đó, MTBF rất nhạy với sự thay đổi của tMET vì phụ thuộc vào tMET theo hàm mũ, vì vậy chỉ cần sự thay đổi nhỏ của tMET cũng làm cho giá trị MTBF biến đổi lớn.

5. Tính toán MTBF cho mạch đồng bộ sử dụng chuỗi FF mắc nối tiếp

5.1 Trường hợp không sử dụng mạch đồng bộ

Trong hình minh họa sau không sử dụng mạch đồng bộ giữa hai miền clock bất đồng bộ. Gọi:

• Tclk_b là chu kỳ clock clk_b
• Tsu là thời gian setup (setup time) của FF miền clk_b
• Tcom là thời gian trễ trên mạch tổ hợp ngõ vào

Hình 10. Giao tiếp giữa 2 miền clock không sử dụng mạch đồng bộ

Nếu tín hiệu bất đồng bộ được sử dụng trực tiếp thì không có thời gian dự trữ nào để để tín hiệu ổn định trước khi được sử dụng, tức là tMET=0. Theo bảng tính của ví dụ hình 9, khả năng xuất hiện lỗi đồng bộ là sau mỗi 0,02ms. Sau mỗi 0,02ms, một lỗi đồng bộ xuất hiện là không thể chấp nhận được đối với bất kỳ thiết kế nào.

5.1 Trường hợp sử dụng 1 FF để làm mạch đồng bộ

Nếu sử dụng một FF để đồng bộ tín hiệu thì khoảng thời gian dự trữ (khoảng thời gian mong muốn) để trạng thái bất ổn định trở về trạng thái ổn định nếu xảy ra vi phạm timing là:

tMET = Tclk_b - (Tcom + Tsu)

Trong đó Tsu là thông số của FF nên tMET phụ thuộc vào Tcom. Tcom càng lớn thì tMET càng nhỏ và MTBF càng nhỏ. Xét lại bảng tính hình 9, giả sử Tsu=1ns, nếu:

1. Mạch tổ hợp đơn giản có độ trễ nhỏ, ví dụ Tcom=2ns thì tMET=20-3=17ns sẽ ứng với MTBF là 370 năm
2. Mạch tổ hợp phức tạp có độ trễ lớn, ví dụ Tcom=13ns thì tMET=20-14=6ns sẽ ứng với MTBF là 3,255s

Hình 11. Sử dụng 1 FF để làm mạch đồng bộ

Việc sử dụng 1 FF làm cho Tcom ảnh hưởng trực tiếp đến tMET. Như đã trình bày trước đó, MTBF rất nhạy với sự thay đổi của tMET nên việc chỉ sử dụng một FF để đồng bộ là vô cùng rủi ro và phụ thuộc quá nhiều vào việc thiết kế phía sau mạch đồng bộ.

5.2 Trường hợp sử dụng 2 FF để làm mạch đồng bộ

Để thời gian dữ trữ cho việc giải phóng khỏi trạng thái bất ổn định tMET được lớn nhất thì Tcom phải nhỏ nhất. Chèn thêm 1 FF là cách đơn giản và không làm thay đổi mạch chức năng phía sau. Khi 2 FF được sử dụng, giữa 2 FF chỉ là dây dẫn và không có mạch tổ hợp nào. Để độ trễ dây dẫn là không đáng kể thì khi layout mạch 2 FF của mạch đồng bộ phải đặt gần nhau, Tcom xem như bằng 0.

tMET = Tclk_b - Tsu

Theo ví dụ trên nếu Tsu = 1ns thì tMET = 19ns và MTBF là 20202 năm.

Hình 12. Sử dụng 2 FF để làm mạch đồng bộ

Đến đây, chúng ta cần lưu ý hai điểm khi sử dụng chuỗi FF để đồng bộ:

1. Mạch đồng bộ phải dùng ít nhất là 2 FF
2. Giữa hai FF của mạch đồng bộ không được phép chèn thêm bất cứ logic mạch tổ hợp nào.

Tiếp theo nếu tăng tần số xung clock clk_b lên, chu kỳ Tclk_b sẽ giảm và thời gian tMET cũng sẽ giảm theo. Ví dụ, tăng tần số clk_b lên 100Mhz, chu kỳ là 10ns, tMET sẽ là:

tMET = Tclk_b - Tsu = 10 - 1 = 9ns

Tính lại MTBF, ta sẽ có:

MTBF ≈ 10,94 phút

Để giải quyết vấn đề này, nhiều thư viện công nghệ (thư viện để tổng hợp và chế tạo vi mạch) hỗ trợ loại D-FF đặc biệt gọi là metastablility-hardened D-FF, tạm dịch là "D-FF kháng bất ổn định", dùng riêng cho mạch đồng bộ. Loại FF này có các hệ số C1, C2 và Tsu nhỏ hơn các FF thông thường nên MTBF sẽ tăng đáng kể.

5.3 Sử dụng nhiều hơn 2 FF để thực hiện mạch đồng bộ

Nếu thư viện công nghệ không có FF đáp ứng được thông số MTBF cần thiết thì sao? Chúng ta có thể tăng MTBF bằng cách mắc nối tiếp nhiều hơn 2 FF. Xét ví dụ, mạch đồng bộ dùng 3 FF để xem tại sao mắc thêm nhiều FF hơn thì có thể đạt MTBF mong muốn.

Hình 13. Mạch đồng bộ sử dụng 3 FF

Tốc độ trung bình để FF đầu tiên rơi vào trạng thái bất ổn định:

Khi FF đầu tiên rơi vào trạng thái bất ổn định thì xác suất để điều kiện bất ổn định tồn tại vượt qua chu kỳ clock hiện tại là:

Nếu trạng thái bất ổn định của FF đầu tiên duy trì quá một chu kỳ xung clk_b thì FF thứ 2 sẽ rơi vào trạng thái bất ổn định và xác suất để điều kiện bất ổn định tồn tại vượt qua 1 chu kỳ clock là:

MTBF của mạch đồng bộ 3 FF sẽ là:

Nếu so với mạch đồng bộ dùng 2 FF, số mũ của tử số MTBF ở mạch dùng 3 FF lớn gấp 2 lần số mũ của tử số ở mạch dùng 2 FF. Sô mũ của tử số mạch dùng 3 FF:

Xét lại ví dụ trước, giá trị MTBF ứng với fclk_b = 100Mhz, fDATA = 10Mhz, C1 = 0,1ns, C2 = 0,5ns, Tsu = 1ns là 1367 năm. Như vậy, chỉ cần mắc thêm 1 FF mà MTBF tăng từ 10,94 phút ở mạch dùng 2 FF lên 1367 năm ở mạch dùng 3 FF.

6. Tóm tắt

Bài này giải thích rõ về:

1. Trạng thái bất ổn định và những nguy hiểm của trạng thái này
2. Tại sao mạch mắc nhiều FF nối tiếp lại hạn chế được trạng thái bất ổn định lan truyền trong thiết kế

Vấn đề kế tiếp đối với việc thiết kế mạch đồng bộ các tín hiệu bất đồng bộ là:

1. Trường hợp nào sử dụng mạch đồng bộ mắc nối tiếp nhiều FF
2. Làm sao để lấy mẫu đúng được dữ liệu mong muốn. Bạn đọc có thể quan sát lại hình 7, trong hình này, việc sử dụng 2 FF chỉ có thể hạn chế được sự lan truyền của trạng thái bất ổn định chứ không đảm bảo lấy được giá trị mong muốn ở ngõ vào.

Các vấn đề trên sẽ được trình bày trong những bài tiếp theo.

Lịch sử cập nhật:

2020.01.07 - Sửa link hình minh họa

Đọc thêm

[Basic Knowledge] Quy trình cơ bản tạo ra vi mạch số

Một quy trình cơ bản để tạo ra một vi mạch số bao gồm các bước chính là phân tích thiết kế, kiểm tra và sửa lỗi, thiết kế vật lý, chế tạo/sản xuất.

Hình 1. Quy trình cơ bản để tạo ra một vi mạch số

1. Phân tích thiết kế (Design Analyzation)

Phân tích thiết kế bao gồm hai công đoạn chính là phân tích cấu trúc và mô tả mã nguồn.
Phân tích cấu trúc thiết kế là phân tích sơ đồ khối, sơ đồ tín hiệu giao tiếp, mạch nguyên lý, giản đồ định thời,... dựa trên các yêu cầu thiết kế. Các thông tin này được thể hiện bằng các hình vẽ  hoặc mô tả. Các phần mềm có thể sử dụng là Microsoft Ofice (Microsoft), Open Office (Sun Microsystems) hoặc Kingsoft Office (Kingsoft),...

Hình 2. Minh họa cách biểu diễn sơ đồ tín hiệu giao tiếp, sơ đồ khối và mạch nguyên lý

Mô tả mã nguồn, thường gọi là mô tả RTL code, là sử dụng ngôn ngữ mô tả phần cứng để mô tả thiết kế dựa trên các phân tích cấu trúc đã thực hiện. Hai ngôn ngữ mô tả phần cứng thông dụng là Verilog và VHDL. Phần mềm có thể sử dụng là các trình soạn thảo có sẵn trong các phần mềm thiết kế hoặc Notepad++, EmEditor, VI, VIM, XEmacs, conTEXT, ...

Hình 3.  Một đoạn RTL code viết bằng ngôn ngữ Verilog mô tả cho mạch nguyên lý 

Sau khi đã hoàn thành RTL code, người thiết kế cần thực hiện kiểm tra các quy định về cú pháp (syntax), luật thiết kế vi mạch số (Design rule) hoặc các luật riêng của các phần mềm thiết kế,... Phần mềm có thể sử dụng là LEDA (Synopsys), NC-Verilog (Cadence) dùng cho thiết kế hướng ASIC hoặc Quartus II (Altera), Vivado (Xilinx) dùng cho thiết kế trên FPGA. 

Hình 3. Minh họa kiểm tra syntax và design rule với phần mềm LEDA - Synopsys

Kết quả chính của bước phân tích thiết kế:

• Bản phân tích mạch nguyên lý của thiết kế
• Các tập tin mã nguồn (RTL code)
• Tài liệu mô tả thiết kế  

2. Kiểm tra và sửa lỗi (Verification and Debug)

Kiểm tra và sửa lỗi là công đoạn thực hiện mô phỏng thiết kế trên các phần mềm chuyên dụng. Có hai cấp độ mô phỏng là mô phỏng mã nguồn, hay mô phỏng mức RTL code, và mô phỏng mức cổng.

Mô phỏng mức RTL code là thực hiện mô phỏng thiết kế đối với RTL code. Công việc chính của bước này là mô phỏng chức năng mà không tính đến định thời và độ trễ vật lý của các tín hiệu.

Mô phỏng mức cổng là thực hiện mô phỏng thiết kế sau khi tổng hợp và sau khi layout. Công việc chính của bước này là mô phỏng chức năng có tính đến định thời và độ trễ của các tín hiệu.

Phần mềm sử dụng có thể là VCS (Synopsys), ModelSim hay Questa Sim (Mentor Graphic), Verilogger Extreme (SynaptiCAD), Verilogger Pro (SynaptiCAD),Veriwell (Wellspring) ... 

Hình 5. Waveform khi chạy mô phỏng 1 thiết kế trên Questa SIM

Kết quả chính của bước này gồm:

• Môi trường mô phỏng của thiết kế
• RTL code đã được sửa lỗi và đảm bảo thực thi đúng chức năng sau khi thực hiện mô phỏng mức RTL code
• Các file tổng hợp và layout đã được sửa lỗi và đảm bảo thực thi đúng chức năng thiết kế và định thời sau khi thực thi mô phỏng mức cổng.  

3. Thiết kế vật lý (Physical Design)

Thiết kế vật lý thực hiện hai công đoạn chính là tổng hợp và layout. Tổng hợp là biên dịch RTL code trên một thư viện công nghệ xác định để tạo ra tập tin netlist. Phần mềm sử dụng để biên dịch có thể là Design Compiler (Synopsys), EncounterTM RTL Compiler (Cadence), Leonardo Spectrum (Mentor Graphics),...

Layout là sử dụng netlist để bố trí vị trí các thành phần logic trên một diện tích xác định để tạo thành bản thiết kế của lõi chip. Phần mềm layout có thể sử dụng là IC Compiler (Synopsys), Encounter Digital Implementation (Cadence), IC Station (Mentor Graphic),...

Kết quả chính của bước này gồm:

• Sau tổng hợp: file netlist
• Sau layout: file .gds
• Các file liên quan khác  

Hình 6. Sơ đồ mạch của một thiết kế sau khi tổng hợp

Hình 7. Nội dung của một file netlist sau khi tổng hợp thể hiện sự kết nối của các cell thư viện

Hình 8. Minh họa bản layout của một chip

4. Chế tạo/sản xuất

Quy trình chế tạo và sản xuất chip trải qua nhiều công đoạn, trong đó, hai công việc chính là chế tạo các lõi chip trên wafer và đóng gói chip.

Chế tạo các lõi chip trên wafer là công đoạn sử dụng kết quả sau bước layout để chế tạo ra các lõi chip.

Đóng gói chip là cắt riêng từng lõi chip trên wafer và mỗi lõi chip được đóng gói trong một vỏ để tạo thành chip hoàn chỉnh. Kết quả của bước này là vi mạch (chip).  

Hình 9.  Các lõi chip trên wafer

Hiện nay, ở Việt Nam, không có công ty nào làm về chế tạo wafer cho vi mạch, chỉ có Intel là làm khâu đóng gói. Các công ty ở Việt Nam chỉ tuyển dụng và làm bước 1, 2 và 3. Trong đó, công việc về Verification và thiết kế vật lý là nhiều nhất. 

Đọc thêm