Bài giảng Thiết kế số - Hoàng Mạnh Thắng

st cho biểu thức SOP dưới đây f(x_1,..x_7)=x_1x_3x_6’+x_1x_4x_5x_6’+x_2x_3x_7+x_2x_4x_5x_7 Tổng hợp mạch đa mức (cont.) Xét việc thực hiện hàm f hai lớp với các PLD như CPLD hay FPGA . Với CPLD thì không sao bởi có đủ đầu vào, đủ cổng AND và cả cổng OR Tổng hợp mạch đa mức (cont.) Với FPGA có các LUTs 2 đầu vào thì hàm này ko thể thực hiện được trực tiếp vì: Dạng SOP có 3 và 4 thành phần (literals)  yêu cầu các cổng AND có 3 và 4 đầu vào Có 4 thành phần tích  cần các cổng OR có 3 và 4 đầu vào Fan-in để thực hiện mạch này là lớn hơn so với các LUTs 2 đầu vào của FPGA Tổng hợp mạch đa mức (cont.) Để giải quyết, hàm phải được biểu diễn ở dạng có số mức logic lớn hơn 2. Nó được gọi là biểu thứ logic đa mức Có 2 kỹ thuật tổng hợp các hàm logic đa mức là: factoring và functional decomposition (đặt thừa số và phân tách hàm) Factoring (đặt thừa số) Sử dụng tính chất phân bố để viết lại biểu thức dưới dạng có ít thành phần biến (literals) trong một nhóm hơn. Ví dụ Ở dạng này, hàm có ko quá 2 thành phần biến cho mỗi nhóm và có thể thực hiện với LUTs hai đầu vào Factoring (đặt thừa số) Các vấn đề của Fan-in Các hạn chế Fan-in ko những chỉ trong PLDs, mà còn trong các cổng logic đơn Nhìn chung, khi số đầu vào đến 1 cổng logic tăng dẫn đến trễ lan truyền tăng. Trễ lan truyền là tổng trễ cần thiết cho sự thay đổi ở đầu vào tạo ra thay đổi ở đầu ra Như vậy, mong muốn là hạn chế số đầu vào tới một phần tử. Thông thường tối đa là 5 Các vấn đề của Fan-in (cont.) Cho một hàm Thực hiện trực tiếp yêu cầu 2 cổng AND 6 đầu vào và 1 cổng OR 2 đầu vào Đặt thừa số cho hàm này có Hàm này giải quyết được vấn đề Fan-in Bài tập Thự c hiện factoring cho biểu thứ c sau với lời giải là chỉ dùng các cổng NA N D /AND và OR hai đầu vào Ảnh hưởng lên mức phức tạp của kết nối Không gian của IC được chiếm bởi mạch và các dây dẫn tạo nên kết nối cho các mạch Mối literal tưpưng ứng với 1 dây nối trong mạch, nó mang tín hiệu logic Factoring làm giảm tổng số literal và cũng giúp giảm mức phức tạp của kết nối Trong khi tổng hợp mạch logic, CAD tôls xem xét các tham số như: chi phí của mạch, fan-in, tốc độ của mạch và mức phức tạp của dây Functional decomposition (phân tách hàm) Mức phức tạp của mạch logic (cổng logic và kết nối) thường có thể được giảm bằng cách phân tách (decomposing) biểu thứ 2 mức thành nhiều mạch nhỏ hơn. Mạch nhỏ này có thể đuwocj dùng một số nơi trong mạch cuối cùng Một biểu thức 2 mức có thể được thay thế bởi 2 hay nhiều biểu thức mới. Các biểu thức mới được tổ hợp để hình thành mạch nhiều mức Ví dụ về phân tách hàm Xét biểu thức: Hàm này yêu cầu 1 cổng AND 3 đầu vào, 2 cổng AND 2 đầu vào và 1 cổng OR 3 đầu vào COST = 4 cổng + 10 đầu vào = 13. Và COST = 19 nếu cổng NOT được kèm thêm vào Viết lại hàm f: Gọi  Ví dụ về phân tách hàm (cont.) Hàm trở thành Mạch được xây dựng như sau với COST=16 bao gồm cả cổng NOT Các vấn đề thực tế Phân tách hàm là công cụ mạnh để giảm mức độ phức tạp cho mạch Nó có thể được dùng để thực hiện hàm logic với các ràng buộc. Ví dụ: thực hiện với PLD cụ thể. CAD tools dùng nhiều khái niệm này. Thiết kế số Thực hiện tối ưu hóa hàm logic: Phân tích và tổng hợp mạch đa mức Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A Các mạch NAND và NOR đa mức Các mạch 2 mức chứa các cổng AND và OR có thể dễ ràng được chuyển thành mạch chỉ dùng các cổng NAND và NOR Mạch 2 mức AND-OR (SOP) có thể được thực hiện trực tiếp thành mạch NAND-NAND Mạch 2 mức OR-AND (POS) có thể được thực hiện trực tiếp thành mạch NOR-NOR Cũng với tiếp cận này có thể được dùng cho các mạng đa mức AND-OR thành NAND-NAND OR-AND thành NOR-NOR Ví dụ mạch đa mức Mạch đa mức dùng NAND Chú ý: các vòng tròn thể hiện đảo (như NOT) Mạch đa mức dùng NAND Mạch đa mức dùng NOR Chú ý: các vòng tròn thể hiện đảo (như NOT) Mạch đa mức dùng NOR Quá trình chuyển đổi đa mức Dạng của mạch ko thay đổi nhiều khi chuyển từ AND và OR sang hoặc NAND hay OR Có thể cần thêm các phần tử làm việc như NOT Kết quả cho ra mạch có thể ko tối ưu Bài tập Chuyển mạch sau về dạng chỉ dùng NAND ? Phân tích mạch đa mức Đánh dấu đầu ra của các cổng như là hàm con Phân tích mạch đa mức ( cont. ) Thiết kế số Bi ểu diễn số và các mạch thực hiện phép toán: Biểu diễn số và phép cộng không dấu Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A Biểu diễn theo vị trí Trong hệ 10, thì (123) 10 =1x10^2+2x10^1+3x10^0 Số nguyên được biểu diễn bởi chữ số D=d n-1 d n-2 .. d 1 d 0 Giá trị được biểu diễn là: V(D)=d n-1 x10 n-1 + d n-2 x10 n-2 +...+ d 1 x10 1 +d 0 x10 0 Đây là hệ 10 nên các số có thể có 10 giá trị và mỗi số có trọng lượng theo lũy thừa của 10 Biểu diễn theo vị trí (cont.) Trong hệ cơ số 2, binary, mỗi chữ số được gọi là bit Biểu diễn theo vị trí là B=b n-1 b n-2 .. b 1 b 0 Biểu diễn số nguyên với giá trị là: V(B)=b n-1 x2 n-1 + b n-2 x2 n-2 +...+ b 1 x2 1 +b 0 x2 0 Biểu diễn theo vị trí (cont.) Số nhị phân (1101) 2 biểu diễn giá trị: V= 1x2 3 + 1x2 2 +0x2 1 + 1 x2 0 =13 Do vậy: (1101) 2 = (1 3 ) 10 Dải giá trị phụ thuộc vào số bit được dùng Trong hệ nhị phân số n -bit sẽ có dải giá trị từ 0-2 n -1 Chuyển đổi giữa hệ 2 và 10 Chuyển từ nhị phân sang hệ 10 có thể được thự hiện trực tiếp bằng biểu thức V(B)=b n-1 x2 n-1 + b n-2 x2 n-2 +...+ b 1 x2 1 +b 0 x2 0 Chuyển từ hệ 10 sang hệ 2 bằng việc chia liên tiếp cho 2 Chuyển đổi giữa hệ 2 và 10 (cont.) Hệ cơ số 8 và 16 (octal & hexadecimal) Ký hiệu theo vị trí có thể được dùng cho bất cứ hệ nào. Với hệ r thì số Có giá trị là Với hệ cơ số 8 gọi là Octal và hệ cơ số 16 gọi là hexadecimal. Hệ cơ số 8 có các chữ số 0-7 Hệ cơ số 16 có các chữ số 0-9 và A-F Số trong các hệ khác nhau Chuyển từ hệ 2 sang 16 và 8 Nhóm các số nhị phân thành các nhóm 4 số và gán mỗi nhóm cho một số hệ 16 và nhóm 3 số nhị phân cho một số trong hệ 8 Phép cộng số không dấu Cộng 2 số một bít sẽ có 4 trường hơp kết quả Phép cộng số không dấu (cont.) Cộng các số lớn Mạch của bộ cộng đầy đủ Mạch của bộ cộng đầy đủ (cont.) Phân tách mạch của bộ cộng đầy đủ Bộ cộng lan truyền (ripple-carry adder) Để thực hiện cộng, các cặp bit cùng trọng lượng được được đưa vào bộ cộng và đầu ra carry được đưa vào bộ cộng có trọng lượng cao hơn cho tới hết Mỗi nhịp sẽ trễ là t  carry sẽ trễ là (n-1) t và sum trễ là nt Thiết kế số Bi ểu diễn số và các mạch thực hiện phép toán: Số có dấu và phép cộng, trừ nhị phân Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A Số có dấu Bit cuối cùng bên trái được dùng để biểu diễn dấu: 0-số dương, 1-số âm Với số n-bit thì n-1 bit dùng để biểu diễn độ lớn Số có dấu (cont.) Có 3 dạng biểu diễn số âm: Dấu-giá trị (sign-magnitude) Bù 1 (1’s complement) Bù 2 (2’s complement) Dạng dấu-giá trị dùng 1 bit để biểu diễn dấu như đã nói trên, ví dụ Dạng này dễ hiểu nhưng ko phù hợp cho việc dùng trong máy tính Biểu diễn kiểu bù 1 Số âm K n-bit nhận được bằng cách lấy số 2 n -1 trừ giá trị dương P của nó K= ( 2 n -1 )-P Ví dụ với n=4 Như vậy , số âm được biểu diễn đơn giản bằng cách bù các bít kể cả bit dấu Dạng này có một số nhược điểm khi dùng cho phép toán Biểu diễn kiểu bù 2 Số âm K n-bit nhận được bằng cách trừ 2^n cho giá trị dương P của nó K= 2^n-P Ví dụ cho số 4 bit Cách đơn giản để tìm bù 2 của một số là cộng 1 vào số tìm được theo cách bù 1 Luật tìm số bù 2 Một số có dấu B=b n-1 b n-2 .. b 1 b 0 , có số sau khi bù là K=k n-1 k n-2 .. K 1 k 0 được tìm bằng cách bù tất cả các bit (kể từ trái quá) sau bit 1 đầu tiên Số nguyên có dấu 4 bit Cộng và trừ Theo cách biểu diễn dấu-giá trị , cộng và trừ được thực hiện đơn giản, nhưng nếu hai số có dấu thì phức tạp hơn Mạch so sánh và trừ cần có Có thể trừ mà không dùng mạch này Với lý do này, cách biểu diễn này ko được dùng trong máy tính Với cách biểu diễn bù 1, cộng và trừ các số có thể cần sửa để nhận được kết quả Ví dụ (-5)+(-2)=(-7), nhưng khi cộng cho ra kết quả 0111  cần đưa bit carry cộng quay lại để có kết quả 1000 Với biểu diễn bù 2 Với phép cộng, kết quả luôn đúng Bit carry-out từ vị trí bit dấu được lờ đi Phép trừ với biểu diễn bù 2 Phép trừ được thực hiện bằng cách cộng số trừ với bù 2 của số bị trừ Đơn vị cộng và trừ Phép trừ có thể được thực hiện thông qua phép cộng dùng bù 2 và ko quan tâm đến dấu của hai số hạng  dùng mạch cộng để thực hiện cả cộng và trừ Có thể dùng XOR để thực hiện tìm bù 1 Đơn vị cộng và trừ (cont.) Tràn trong khi thực hiện phép tóan Một số hữu hạn bit chỉ biểu diễn được một dải giá trị hữu hạn. Nếu số cần biểu diễn nằm ngòai dải thì sẽ dẫn đến tràn Số n-bit có dải giá trị từ -2 n-1 đến 2 n-1 -1 Ví dụ về c ó tràn ở phép tóan Nếu các số có dấu khác nhau sẽ ko có hiện tượng này Phát hiện tràn Trong ví dụ cộng các số được biểu diễn bởi 4 bit thì tiện tượng tràn có thể được phát hiện bởi: Trong trường hợp tổng quát n-bits Như vậy, mạch cộng và trừ có chức năng phát hiện tràn nếu có thêm 1 cổng XOR Thiết kế số Bi ểu diễn số và các mạch thực hiện phép toán: Bộ cộng nhanh, c ân bằng trong thiết kế và các ví dụ Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Các vấn đề hoạt động Các bộ cộng trừ được dùng thường xuyên, do đó, nó có ảnh hưởng lớn đến toàn bộ hoạt động của hệ thống máy tính Hoạt động của bộ cộng và trừ Quan tâm đến thời gian trễ lớn nhất từ khi đưa các giá trị vào cho tới lúc có kết quả ra, S và C. Giả sử bộ cộng được xây dựng từ bộ cộng có carry nối liên tiếp (ripple-carry adder), với mỗi bit được thực hiênk bởi bộ full adder Hoạt động của bộ cộng và trừ (cont.) Trễ cho carry-out là t, bằng với trễ của hai cổng Kết quả nhận được sau n.t, có thêm trễ t ở cổng XOR trước khi đưa Y vào bộ cộng  tổng là ( n+1)t Tốc độ lớn nhất của mạch bị giới hạn bởi trễ dài nhất của đường tín hiệu đi trong mạch. Gọi trễ đó là critical-path-delay đường đi đó gọi là critical path Bộ cộng carry-lookahead Để giảm trễ gây ra bởi đường lan truyền của carry  cố gắng đánh giá nhanh giá trị của carry-in  tăng hộat động Ở đọan/bit i , carry-out là: Gọi và thì g i = 1 nếu cả x i và y i bằng 1 bất kể c i bằng bao nhiêu  đảm bảo việc tạo ra carry và g được gọi là hàm tạo p i =1 khi hoặc x i hay y i bằng 1  c i+1 =1 nếu c i =1. Ảnh hưởng của c i =1 được lan truyền qua bit i; p được gọi là hàm lan truyền Bộ cộng carry-lookahead (cla) (cont.) Hàm cho carry-out của bộ cộng n-bit Như vậy, Bộ cộng carry-lookahead (cla) (cont.) Carry được tạo ra ở đoạn n-2 và lan truyền qua các đoạn còn lại Carry được tạo ra ở đoạn 0 và lan truyền qua các đoạn còn lại Carry được tạo ra ở đoạn cuối cùng Carry được tạo ra ở đoạn n-3 và lan truyền qua các đoạn còn lại Carry vào c 0 và lan truyền qua tất cả đoạn còn lại Đường đi dài nhất của bộ cộng ripple-carry Trễ 3 t cho c 1 Trễ 5 t cho c 2  Trễ (2n+1) t cho bộ công ripple-carry n-bit Đường đi dài nhất của bộ cộng carry-lookahead Trễ 3 t cho c 1 Trễ 3 t cho c 2 Trễ 3 t cho c n Trễ 4 t cho bộ cộng carry-aheadlook n-bit Tất cả g i và p i là một trễ Tất cả c i nhiều hơn g_i và p i 2 trễ s i nhiều hơn c i một trễ Các hạn chế của carry-lookahead Từ biểu thức cho carry trong bộ cộng CLA Thấy rằng: Kết quả nhận được nhanh vì ở dạng hàm 2 mức dùng AND-OR Hạn chế Fan-in có thể làm hạn chế tốc độ Mức độ phức tạp tăng nhanh khi n lớn Bộ cộng 32 bit Chia bộ cộng 32 bit thành 4 khối, mỗi khối là 1 bộ cộng CLA 8 bit. Bit b 7-0 là khối 0 Bit b 15-8 là khối 1 Bit b 23-16 là khối 2 Bit b 32-24 là khối 3 Có 2 cách cơ bản thực hiện nối các khối này: Rippple-carry và CLA mức thứ 2 Ripple-Carry CLA mức thứ 2 CLA mức thứ 2 (cont.) Ở lớp thứ 2: Ph ân tích cho bộ cộng CLA Nếu có hạn chế về fan-in ở 4 đầu vào thì thời gian để cộng các số 32 bit liên quan: Trễ qua 5 cổng để phát triển các thành phần g i và p i , trễ qua 3 cổng cho lookahead lớp thứ 2 và trễ qua một cổng (XOR) để tạo ra các bit tổng cuối cùng Bit tổng cuối cùng được tính toán sau trễ 8 cổng vì c 32 ko được dùng để xét các bit tổng Hoạt động hoàn chỉnh kể cả phát hiện tràn (c 31 XOR c 32 ) có 9 trễ qua cổng. Với bộ cộng Ripple-carry cần 65 Thiết kế số Bi ểu diễn số và các mạch thực hiện phép toán: Thiết kế bộ toán học dùng CAD tools Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Thiết kế dùng chương trình vẽ mạch- sch. capture M ột cách để thiết kế mạch toán học là vẽ tất cả các cổng logic cần thiết Tạo ra bộ cộng n-bit Bắt đầu với bộ cộng đầy đủ 1-bit Nối thành chuỗi để tạo thành bộ cộng n-bit Nếu là bộ cộng CLA thì cộng logic carry lookahead Quá trình thiết kế nhanh chóng phức tạp Cách tốt hơn là sử dụng các phần mạch đã được thiết kế sẵn CAD tools có sẵn thư viện các cổng logic cơ bản CAD tools cũng có thư viện các mạch thường được sử dụng, ví dụ bộ cộng mỗi phần mạch subcircuit là module có thể được gọi vào dùng Macro- và megafunctions Một số hệ thống CAD, ví dụ MAX:PLUS2, Altera, các hàm thư viện này được gọi là Macrofunctions hoặc Megafunctions Có hai loại cơ bản: Phụ thuộc công suất: được thiết kế cho loại chip cụ thể (ví dụ cho FPGA) Không phụ thuộc công nghệ: cho chip bất kỳ, các mạch khác nhau cho các loại chip khác nhau Ví dụ thư viện các macrofunctions như Library of Parameterized Modulé (LPM) như là một phần của hệ thống MAX+PLUS2 Các module không phụ thuộc công nghệ Các module được tham số hóa: nó có thể được dùng đa dạng LPM_ADD_SUB Thư viện LPM có bộ cộng n-bit tên: LPM_ADD_SUB Thực hiện mạch cộng/trừ cơ bản Số bit có thể được thiết lập bởi tham số LPM_WIDTH Tham số khác là LPM_REPRESENTATION dùng để chỉ ra số có dấu hay không dấu Bộ cộng dùng LPM_ADD_SUB Thực hiện Simulation Thiết kế dùng VHDL Có thể dùng cách chia tầng trong thiết kế dùng VHDL Xây dựng entity VHDL cho bộ cộng đầy đủ Dùng các Instances để tạo bộ cộng nhiều bit Tín hiệu logic trong VHDL được biểu diễn là các đối tượng dữ liệu Dùng kiểu BIT cho các giá trị 0 hoặc 1 Kiểu dữ liệu khác là STD_LOGIC thích được dùng vì nó có thể biểu diễn cho 3 trạng thái (0,1,Z, và don’t care) Phải khai báo thư viện kiểu dữ liệu được dùng và nơi nó tồn tại LIBRARY ieee; USE ieee.std_logic_1164.all Bộ cộng đầy đủ trong VHDL Bộ cộng Ripple Carry 4-bit đầy đủ Bộ cộng Ripple Carry 4-bit đầy đủ Khai b áo mới của VHDL Trong đoạn code vừa rồi có khai báo SIGNAL c1,c2,c3: STD_LOGIC; Để định nghĩa các tín hiệu sẽ dùng trong thiết kế Dùng trong ARCHITECTURE COMPONENT fulladd Dùng trong ARCHITECTURE Định nghĩa PORT cho phần mạch con (subcircuit này được định nghĩa ở file khác) File VHDL (fulladd.vhd) thường đươc đặt ở cùng đường dẫn với file adder4.vhd Khai b áo mới của VHDL, cont. stage0: fulladd PORT MAP (Cin, x0,y0,s0,c1); Chỉ ra đọan trong hoạt động Sử dụng phép kết hợp vị trí của các đầu vào/ra khai báo trong PORT MAP ứng với thứ tự vị trí trong khai báo COMPONENT stage3: fulladd PORT MAP (Cin=>c3,Cout=>Count,x=>x3,y=>y3,s=>s3); Sử dụng phép kết hợp tên với đàu vào/ra trong PORT MAP ứng với tín hiệu được đặt tên trong khai báo COMPONENT Các gói VHDL M ột gói VHDL có thể được tao ra cho một mạch con mà khai báo COMPONENT không được yêu cầu không rõ ràng trong khi tạo ta biến của mạch con khác trong file khác Các gói VHDL, cont, Được biên dịch như là file trong cùng đường dẫn với fulladd.vhd Các gói VHDL, cont, Số học trong VHDL Số là đối tượng dữ liệu SIGNAL nhiều bit SIGNAL C: STD_LOGIC_VECTOR (1 TO 3) C là tín hiệu STD_LOGIC 3-bit Phép gán C<=“100” C(1) là bit có trọng số lớn nhất C(3) là bit có trọng số nhỏ nhất Trọng số có thể bị đảo ngược nếu khai báo SIGNAL X: STD_LOGIC_VECTOR (3 TO 0) Số học trong VHDL, cont. Mô tả Behavioral trong VHDL Cho phép dùng các tín hiệu STD_LOGIC như là các giá trị có dấu Phần này mô tả behavior của mạch Các gói toán học của VHDL Bài tập: đọc và giải thích Thiết kế số Bi ểu diễn số và các mạch thực hiện phép toán: C ác biểu diễn số khác Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Các biểu diễn số khác Đã quan tâm đến số nguyên có và ko có dấu với phép biểu diễn liên quan đến vị trí Các biểu diễn số khác cũng thường được dùng: Dấu phảy cố định (fixed-point): dùng cho phân số Dấu phảy động: cho các số rất nhỏ và rất lớn với dộ chính xác cao Mã BCD (Binary-Coded Decimal): là một kiểu biểu diễn khác cho số nguyên Các số dấu phảy cố định Số gồm phần nguyên và phần phân số Ký hiêu vị trí được viết như sau B=b n-1 b n-2 ...b 1 b 0 .b -1 b -2 ...b -k Có giá trị tương ứng là: Vị trí của dấu p hả y được cho là cố định Các số dấu phảy cố định, cont. Ví dụ: B=(01001010.10101) 2 B=1x2 6 +1x2 3 +1x2 1 +12 {-1}+1x2 -3 +1x2 -5 B=64+8+.5+.125+.03125 B=(74.65625) 10 B=(8A.A8) 16 Các mạch logic thực hiện các số dấu phảy cố định giống như đối với các số nguyên Các số dấu phảy động Số có dấu phảy tĩnh có dải giá trị giới hạn bởi số chữ số dùng để biểu diễn Số có dấu phảy động được dùng cho thực tế để biểu diễn cho số rất lớn hoặc rất nhỏ. Số được biểu diễn bởi mantissa gồm các chữ số và lũy thừa của cơ số R , dạng: MantissaxR Exponent Thường được chuẩn hóa theo dạng ví dụ: 5.234x10 43 và 3.57x10 -35 Các số dấu phảy động, cont. IEEE chuẩn hóa dạng 32-bit (độ chính xác đơn) cho các giá trị dấu phảy động Bit dấu (S): bít có trọng số lớn nhất (MSB) 8-bit cho phần lũy thừa (E): E-127 Lũy thừa đúng = E-127 E=0  giá trị 32-bit =0 E=255  giá trị bằng ∞ 23-bit mantissa Các số dấu phảy động, cont. Chuẩn IEEE được dùng để chuẩn hóa cho mantissa với MSB luôn có giá trị 1 Không cần thiết chỉ ra bit này cụ thể trong phần mantissa. Nghĩa là nếu M là giá trị trong phần mantissa 23-bit, mantissa thực sự (24-bit) sẽ là 1.M Giá trị của số là: V=(-1) s .Mx2 E-127 Các số dấu phảy động, cont. Ví dụ: 0100 0000 0110 0000 0000 0000 0000 0000 =+(1.11) x 2 (128-127) =+(1.11) 2 x 2 1 =+(11.1) 2 =+(1x2 1 +1x2 0 +12 -1 )=(3.5) 10 Bài tập: tìm giá trị của 0011 1111 0110 0000 0000 0000 0000 0000 Các số mã BCD Có thể mã các số nguyên dưới dạng nhị phân, được gọi là BCD Dùng 4 bit cho một chữ số trong hệ 10 Từ 0=0000 to 9=1001 (01111000) BCD =(78) 10 Mã BCD đã được dùng trong các máy tính thế hệ cũ và các calculator. Vì dạng này thuận tiện cho thông tin số được hiển thị đơn giản dưới dạng số Mã ký tự ASCII Đựơc dùng để biểu diẽn trong máy tính đùng cho số, ký tự và mã điều khiển American Standard Code for Information Interchange (ASCII) dùng 7 bit để biểu diễn 128 ký hiệu gồm: (0-9), (a-z), (A-Z), các dấu chấm phảy..... ASCII có 8-bit mở rộng được dùng cho các ký tự lớn hơn 128 và các ký tự đồ họa Mã ký tự ASCII: ví dụ Thiết kế số Các khối mạch tổ hợp: Các bộ ghép kênh Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Các bộ ghép kênh Mạch ghép kênh có: Một số đầu vào dữ liệu Một/vài đầu chọn đầu vào Một đầu ra Nó chuyển giá trị tín hiệu trên một trong các đầu vào đến đầu ra dựa trên giá trị của đầu tín hiệu chọn Thực hiện bộ ghép kênh Hay được dùng hơn Bộ ghép kênh 4 đầu vào Đầu ra là từ 1 trong 4 đầu vào tùy theo 2 tín hiệu chon Xây dựng bộ ghép kênh 4 đầu vào Có thể được xây từ 2 bộ MUX 2 đầu vào Ứng dụng của MUX (crossbar 2x2) Mạch có n đầu vào và k đầu ra với chức năng là cung cấp khả năng kết nối bất kỳ đầu vào nào đến bất kỳ đầu ra, và được gọi nxk crossbar swich Hai đầu vào và 2 đầu ra  2x2 crossbar Dùng khi cần nối 1 tập các dây đến bất kỳ tập dây nào nơi mẫu kết nối thay đổi theo thời gian Mạng chuyển mạch là ví dụ Ứng dụng của MUX Trong các phần tử có thể lập trình (PLD, CPLD, FPGA), các chuyển mạch có thể lập trình dùng để thực hiện kết nối dây bên trong dùng MUX Hàm logic dùng MUX MUX có thể được dùng để tổng hợp hàm logic Thực hiện LUT dùng MUX để chọn một biến/hằng từ một look-up table Xét hàm XOR Hàm logic dùng MUX, cont Dùng XOR như trên không hiệu quả Hàm logic dùng MUX, cont-Bài tập Thực hiện dưới đây với MUX 2 đầu vào và bất kỳ cổng logic nào thêm Hàm logic dùng MUX, cont XOR 3 đầu vào có thể được thực hiện với MUX 2 đầu vào Hàm logic dùng MUX, cont-Bài tập Thực hiện hàm dưới với MUX 2 đầu vào và cổng logic cần thiết nếu cần Lý thuyết khai triển Shannon Bất kỳ hàm Boolean f(w 1 ,...w n ) có thể được viết dưới dạng f(w 1 ,...w n )=(w 1 )’. f(0, w 2 ...w n )+(w 1 ). f(1, w 2 ...w n ) Khai tri ển có thể được thực hiện dùng bất kỳ biến nào trong n biến Nếu f(w 1 , w 2 ,w 3 )=w 1 w 2 + w 1 w 3 + w 2 w 3 Triển khai theo w 1 có Lý thuyết khai triển Shannon-Ví dụ Lý thuyết khai triển Shannon-Ví dụ Chọn khai triển theo biến x Lý thuyết khai triển Shannon-Bài tập Chọn khai triển theo biến z Thiết kế số Các khối mạch tổ hợp: Các bộ giải mã, tách kênh mã hóa và chuyển đổi mã Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A C ác bộ giải mã Mạch giải mã thự hiện việc giải mã thông tin Bộ giải mã nhị phân có n đầu vào 2 n đầu ra Chỉ có một đầu ra được active và ứng với một giá trị của đầu vào Đầu vào cho phép (EN) được dùng để disable các đầu ra khi EN=0, ngược lại.... Mạch giải mã 2-to-4 (2 vào-4 ra) Mạch giải mã 3-to-8 (3 vào-8 ra) Mạch giải mã 3-to-8 (74138) Các đầu ra active ở mức thấp Ứng dụng của bộ giải mã Dùng để giải mã địa chỉ cho bộ nhớ Các bộ tách kênh (demultiplexer) Dùng để tách 1 đầu vào tới n đầu ra  ngược lại với bộ ghép kênh Bộ tách n-to-2 n thực hiện như một bộ tách kênh Làm việc như đầu vào chọn Làm việc như đầu vào dữ liệu Bộ mã hóa (encoder) Làm chức năng ngược lại với bộ giải mã Bộ mã hóa nhị phân mã hóa thông tin từ 2 n đầu và và cho ra mã n-bit Chính xác 1 đầu vào có giá trị “1” Các đầu ra biểu diễn số nhị phân Bộ mã hóa làm giảm số bit cần để biểu diễn thông tin Ứng dụng trong truyền tin ở hệ thống số Bộ mã hóa (encoder), cont. Bộ mã hóa ưu tiên (priority enc) Là loại dựa trên tính ưu tiên của tín hiệu vào Mỗi đầu vào có mức ưu tiên được định sẵn Đầu ra của bộ giải mã chỉ ra đầu vào active có mức ưu tiên cao nhất Khi đầu vào với mức ưu tiên cao hơn được xác định, đầu ra có mức ưu tiên thấp hơn được lờ đi Bộ mã hóa ưu tiên, cont. Ví dụ W_0 có mức ưu tiên thấp nhất và W_3 có ưu tiên cao nhất Đầu ra z=0 khi ko có đầu vào nào bằng 1 C ác bộ chuyển đổi mã Mục đích là chuyển đổi từ dạng mã hóa này sang dạng khác Ví dụ: Bộ giải mã 3-to-8 chuyển từ nhị phân sang mã one-hot ở đầu ra Bộ mã hóa 8-to-3 thực hiện ngược lại Nhiều loại khác nhau mạch chuyển đổi có thể được xây dựng Bộ giải mã BCD-to-7 segment Bộ giải mã BCD-to-7 segment Chuyển từ BD sang dạng thông tin phù hợp cho hiển thị, ví dụ máy bán nước tự động. Mỗi Segment là một đoạn LED được điều khiển bởi tín hiệu điện Bộ giải mã BCD-to-7 segment, cont. Bộ giải mã BCD-to-7 segment, cont. Thiết kế số Các khối mạch tổ hợp: VHDL cho mạch logic tổ hợp Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Các phép gán-asignment statement VHDL có vài loại phép gán có thể được dùng để gán giá trị logic vào tín hiệu Các phép gán đơn giản đã xét trong các phép toán Các phép gán tín hiệu lựa chọn một trong nhiều giá trị Các phép gán tín hiệu có điều kiện Tạo ra các statements Các mẫu If-then-else Các mẫu Case Các phép gán tín hiệu lựa chọn Cho phép một tín hiệu được gán một trong nhiều giá trị dựa trên tiêu chí lựa chọn. VD: Từ khóa WITH chỉ ra s được dùng để tiêu chí lựa chọn Hai chỗ WHEN chr ra f=w 0 khi s=0 và ngược lại f=w 1 Từ khóa OTHER phải được dùng Đoạn mã VHDL cho bộ ghép kênh 4-to-1 Đoạn mã VHDL cho bộ giải mã 2-to-4 Phép gán có điều kiện Tương tự với phép gán có lựa chọn, phép này cho phép một tín hiệu được thiết lập bằng một trong các giá trị Dùng WHEN và ELSE để chỉ ra điều kiện và các hoạt động được thực hiện Mã VHDL cho bộ mã hóa ưu tiên Tạo các statements Bất kỳ khi nào viết mã VHDL có dạng cấu trúc, ta thường tạo ra các biến (instances) của phần tử cụ thể Bộ cộng ripple carry là ví dụ Nếu cần tạo một số lớn các instances của một biến, dạng gọn hơn được mong muốn VHDL cung cấp đặc tính này gọi là FOR GENERATE statement Dùng để cung cấp một cấu trúc lặp cho quá trình mô tả mã phân tầng được cấu trúc hóa Bộ cộng Ripple Carry 4-bit Bộ cộng Ripple Carry 4-bit, cont Phát biểu tiến trình-process statement Các phép gán trên ko ảnh hưởng đến ý nghĩa của đọan mã  gọi là concurent assignment statements (các phép gán đồng thời) VHDL cung cấm kiểu gán khác, sequential assignment staements , ở đó thứ tự của khai báo ảnh hưởng ý nghĩa đoạn mã Ví dụ: if-then-else và CASE VHDL yêu cầu các phép này được đặt bên trong statement khác, process statement Process statements Bắt đầu bởi process , tiếp đến nhóm các tín hiệu sensitivity list , danh sách này kèm the tất cả các tín hiệu được dùng trong process Statements bên trong process được xét trong tứ tuần tự Các phép gán được tạo trong process ko thể nhìn được từ bên ngoài process cho tới khi các statements trọng process được xét  nhiều phép gán đến một tín hiệu trong process thì chỉ có phép cuối cùng có tác dụng MUX 2-to-1 làm việc như một process B ộ mã hóa ưu tiên (IF_THEN_ELSE) B ộ mã hóa ưu tiên (cách khác) Ám chỉ bộ nhớ trong Process ? Case statement Tương tự phép gán có lựa chọn với một tín hiệu và kèm WHEN cho các giá trị của tín hiệu chọn Bắt đầu với từ khóa CASE Mỗi WHEN hcỉ ra các statement được đánh giá khi tín hiệu chọn có giá trị được chỉ ra CASE statement phải kèm WHEN cho tất cả các đánh giá của tín hiệu chọn Dùng OTHER MUX 2-to-1 với CASE Bộ giải mã 2-to-4 với CASE Thiết kế số Các khối mạch tổ hợp: Các Flop-Flops, thanh ghi và các bộ đếm: Chốt Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Các phần tử lưu giữ Đã xét các mạch combinational circuit có đầu ra phụ thuộc vào các tín hiệu vào Một loại mạch khác là đầu ra phụ thuộc ko những trạng thái đầu vào hiện tại mà còn phụ thuộc trạng thái trước đó của mạch Mạch đó có các phần tử lưu trữ giá trị của các tín hiệu logic Mạch tuần tự-sequential circuit Nội dung của các phần tử nhớ biểu diễn trạng thái của mạch Thay đổi đầu vào có thể làm thay đổi hoặc ko làm thay đổi trạng thái của mạch Mạch thay đổi thông qua một chuõi các trạng thái như kết quả của các thay đổi ở đầu vào Mạch có đặc điểm này gọi là sequential circuits Hệ thống điều khiển báo động Mạch báo động ON khi đầu ra sensor bật Mạch cần phần tử nhớ để nhớ rằng báo động phải được active cho tới khi nhấn RESET Phần tử nhớ đơn giản Có đường hồi tiếp để nhớ dữ liệu Chốt SR Có thể biểu diễn dùng NOR Có các đầu vào Set và Reset làm thay đổi trạng thái Q c ủa mạch Mạch được xem như là chốt Chốt SR, cont. Sơ đồ thời gian của chốt SR Cùng về 0 Sơ đồ thời gian của chốt SR Nếu thời gian trễ lan truyền từ Q a và Q b chính xác giống nhau  ở t 10 tiếp tục không xác định Thực tế có thể có trễ khác nhau  chốt thiết lập về một trong hai trạng thái ổn định (nhưng ta ko biết trạng thái nào) Do vậy S=R=1 được xem như la tổ hợp cấm trong mạch chốt SR Chốt được đóng mở-Gated SR latch Chốt SR thay đổi trạng thái khi đầu vào thay đổi Có thể thêm tín hiệu cho phép vào SR để điều khiển quá trình thay đổi trạng thái Mạch đó được xem là chốt SR được đóng mở Chốt được đóng mở-Gated SR latch, cont. Sơ đồ thời gian Chốt SR dùng cổng NAND Chốt D có clk Chốt có một đầu vào dữ liêu D lưu giảtị vào dưới sự điều khiển của tín hiệu Clk  Gated D Latch Chốt D có clk, cont Cảm nhận them mức và sườn (level vs. edge) Đầu ra của chốt D được điều khiển bởi mức (0 hoặc 1) của đầu vào Clk  cảm nhận theo level Có thể thay đổi đầu ra khi Clk chuyển mức  cảm nhận theo sườn - edge Ảnh hưởng của trễ lan truyền Các phần trước chưa quan tâm đến tác động của trễ lan truyền. Thực tế nó xảy ra Cần đảm bảo ổn định tín hiệu đầu vào khi có thay đổi xảy ra ở Clk Thời gian tối thiểu để tín hiệu D duy trì ổn định trước khi sườn âm (1 0 ) của Clk được gọi là thời gian setup (t su ) Thời gian tối thiểu để tín hiệu D duy trì ổn định sau khi sườn âm của Clk gọilà thời gian giữ (hold time) - t h Với CMOS là t su =3ns và t h =2ns Các thời gian setup và hold Thiết kế số Các khối mạch tổ hợp: Các Flop-Flops, thanh ghi và các bộ đếm: Các Flip-Flop Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Flip-Flop Là gated latch cảm nhận theo mức và có thể thay đổi trạng thái nhiều hơn một lần mỗi khi giai đoạn active của tín hiệu Clk Phần tử lưu trữ có thể thay đổi trạng thái không nhiều hơn một lần trong một chu kỳ Clk Hai loại mạch có đặc điểm này là: Master-slave flip-flop Edge-triggered flip-flop Master-slave D flip-flip Gồm 2 chốt D: master và slave Master thay đổi trạng thái trong khi Clk=1 Slave thay đổi trạng thái khi Clk=0 Master-slave D flip-flip, cont Edge-triggered Flip-Flops Chức năng tương tự với Master-slave D flip-flop và được xây dựng từ cổng 6 NAND Edge-triggered Flip-Flops , cont Như vậy có So sánh các loại Các đầu vào Clear và Preset Một flip-flop cần có các đầu vào để có set (Q=1) và xóa (Q=0) Các đầu vào đó gọi là Preset và Clear Nhìn chung các đầu vào là không đồng bộ với Clk T flip-flop T flip-flop có thể được suy ra từ D flip-flop Các kết nối hồi tiếp làm cho đầu vào D bằng với Q hoặc Q’ tùy theo giá trị của T T flip-flop, cont Có tên là T từ đặc điểm “toggles” trạng thái của nó khi T=1 JK flip-flop JK flip-flop cũng được sinh ra từ D flip-flop D=JQ’+K’Q JK tổ hợp của SR và T flip-flop Làm việc giống SR khi J=S và K=R cho tất cả các giá trị trừ J=K=1 Với J=K=1, nó làm việc giồng T flip-flop JK flip-flop Sơ đồ thời gian của JK flip-flop Thiết kế số Các khối mạch tổ hợp: Các Flop-Flops, thanh ghi và các bộ đếm: Thạn ghivà các bộ đếm Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Thanh ghi - registers Các flip-flop lưu trữ một bit thông tin Khi n flip-flop được dùng để lưu n bit dữ liệu ta gọi là thanh ghi Thanh ghi được dùng để: giữ dữ liệu, giữ giá trị đếm.... Clk được dùng chung cho tất cả các flip-flop Thanh ghi dịch – Shift register Thanh ghi loại này cho phép dịch các bit thông tin: sang trái hoặc sang phải hoặc cả hai Thanh ghi dịch phải Dữ liệu được dịch nối tiếp sang phải dùng đầu vào In Hoạt động theo sườn dương Clk, theo mức ko phù hợp vì xảy ra dịch liên tiếp Thanh ghi dịch truy nhập song song Dữ loệi chuyển trong máy tính là hàm chung n-bit một lúc, gọi là song song. Nếu 1 bit một lần thì là nối tiếp Dữ liệu vào dong song rồi dịch nối tiếp gọi là Parallel-to-Serial conversion. Ngược lại có Serial-to-Parallel Thanh ghi dịch truy nhập song song, cont. Bộ đếm Dùng cho mục đích đếm tăng hoặc giảm Ứng dụng cho đếm sự kiện, thời gian... Thường dùng T flip-flop Bọ đếm tăng Bọ đếm giảm Bộ đếm không đồng bộ Các bộ đếm đã nói trên thuộc loại ko đồng bộ, hay Ripple Counters Đầu vào Clk chỉ nối với một flip-flop Clk cho các flip-flop khác là đầu ra của flpflop trước Loại không đồng bộ có tốc độ thấp do cách nối cascade Bộ đếm đồng bộ Clk được dùng chung cho tất cả các flip-flop Dùng T flip-flop Bộ đếm đồng bộ dùng T flip-flop Cho phép làm việc và xóa bộ đếm Tín hiệu enable là điều khiển. clear không đồng bộ Bộ đếm đồng bộ dùng D flip-flop Bộ đếm tăng 4 bit: 0,1,..,15,0,1.. Các đầu ra của bộ đếm: Q 3 Q 2 Q 1 Q 0 Cácđầu vào D: Bộ đếm 4-bit dùng D flip-flop Bộ đếm được nạp vào song song Thông thường đếm bắt đầu từ 0, nhưng có thể bắt đầu từ một giá trị được nạp song song Đầu vào điều kiểm load: Load=0, thực hiện đếm Load= 1 , nạp giá trị song song vào bộ đếm Bộ đếm được nạp vào song song, cont Bài tập: viết bảng trạng thái cho mạch trên Thiết kế số Các khối mạch tổ hợp: M ạch tuần tư đồng bộ: sơ đồ trạng thái và bảng trạng thái Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Mạch tuần tự đồng bộ M ạch Synchronous sequential có tín hiệu Clk điều khiển hoạt động Từ active clock edge là sự thay đổi trạng thái Mạch đươc thực hiện dùng combinational logic và một hay nhiều flip-flops Hai mô hình cho loại này là: Mô hình Moore: đầu ra chỉ phụ thuộc vào trạng thái hiện tại Mô hình Mealy: đầu ra phụ thuộc vào trạng thái hiện tại và đầu vào Các mạch sequential này còn được gọi là Finite State Machines (FSM) Các máy Moore và Mealy Các bước thiết kế Các kỹ thuật thiết kế thông qua ví dụ đơn giản Thiết kế mạch thỏa mãn các thông số sau: Mạch có một đầu vào, w, ào một đầu ra, z , Tất cả thay đổi xảy ra ở sườn dương của tín hiệu Clk Đầu ra z=1 nếu w=1 trong hai chu kỳ Clk Như vậy z không thể chỉ phụ thuộc vào w Tuân tự của tín hiệu Đầu vào và đầu ra như dưới đây là ví dụ Sơ đồ trạng thái Bước 1: trong quá trình thiết kế FSM là xem xét có bao nhiêu trạng thái cần thiết và dịch chuyển trạng thái có thể xảy ra. Không có thủ tục preset cho nó Người thiết kế phải nghĩ đến những gì để mạch hoàn thành Bắt đầu là phải định nghĩa trạng thái reset mà mạch thực hiện sau khi bật nguồn hoặc tín hiệu reset được đưa vào Sơ đồ trạng thái Giả sử trạng thái bắt đầu là A Khi w=0 , mạch ko thực hiện gì và z=0 Sơ đồ trạng thái, cont. Khi w=1, mạch nhớ trạng thái bằng cách chuyển đến trạng thái mới B Chuyển trạng thái nên xảy ra ở sườn xung nhịp tiếp theo Sơ đồ trạng thái, cont. Khi trong trạng thái B và w=1, mạch nhớ bằng cách chuyển đến trạng thái mới C Sơ đồ trạng thái đầy đủ Mô hình Moore Bảng trạng thái Sơ đồ trạng thái mô tả chức năng của mạch, nhưng không mô tả việc thực hiện mạch  cần chuyển thành dạng bảng Bảng trạng thái nên chứa Tát cả dịch chuyển từ trạng thái hiện tại sang trạng thái tiếp theo cho tất cả các giá trị tín hiệu vào Đầu ra z ứng với trạng thái hiện tại cũng được chỉ ra Ph ép gán trạng thái Các trạng thái được định nghĩa như là các biến Mỗi trạng thái được biểu diễn bởi một giá trị của các biến trạng thái cụ thể Mỗi biến được thực hiện với một flip-flop Vì chỉ có 3 trạng thái  chỉ cần 2 biến trạng thái y 2 y 1 biểu diễn trạng thái hiện tại Y 2 Y 1 dùng cho trạng thái tiếp theo Bảng trạng thái được gán Chú ý rằng ttrạng thái y2y1 ko dùngi Bảng đầu ra và trạng thái tiếp theo Bảng K-map được xây dựng từ bảng trạng thái: Đầu ra mạch, z Các đầu vào cho flip-flop (trạng thái tiếp của K-map) Xây dựng bảng trạng thái tiếp theo phụ thuộc vào loại flip-flop được dùng Loại D: bảng trạng thái xây dựng từ trực tiếp từ bảng trạng thái khi Q(t+1)=Q + =D. T và JK xét sau Bảng trang thái và bảng trạng thái tiếp theo Bảng trạng thái và bảng đầu ra Sơ đồ mạch Sơ đồ thời gian Thiết kế số Các khối mạch tổ hợp: M ạch tuần tư đồng bộ:  Th ực hiện mạch dùng Flip-Flop loại D, T và JK Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Ví dụ thiết kế bộ đếm Bộ đếm tăng giảm 2-bit với: Đếm tăng nếu U=1 và là 0,1,2,3,0,1... Đếm giảm nếu U=0 và là 0,3,2,1,0,3... U là đầu điều khiển, đầu vào Reset về 0, hai đầu ra Z_1Z_0 và bộ đếm active theo sườn dương xung nhịp Thiết kế dùng các flip-flop D, T và JK Sơ đồ trạng thái Bảng trạng thái Bảng trạng thái được mã hóa Các trạng thái A=00, B=01, C=10 và D=11 Thực hiện dùng Flip-flop loại D Khi dùng flip-flop loại D, trạng thái tiếp theo được đưa trực tiếp vào đầu vào của flip-flop Do vậy, K-map dinh ra trực tiếp từ bảng mã hóa trạng thái Cách làm này ko áp dụng cho T và JK được Bảng trạng thái được mã Thực hiện dùng flip-flop loại D Thiết kế dùng các loại flip-flop khác Với loai T hoặc JK, ta phải biến đổi các đầu vào cho flip-flop Trước khi thực hiện bảng dịch chuyển trạng thái, các đầu vào yêu cầu được liệt kê cho một dịch chuyển trạng thái cụ thể nào đó Bảng dịch chuyển được dùng với bảng mã hóa trạng thái để tạo ra bảng kích (excitation table) Bảng kích liệt kê tấ cả các đầu vào yêu cầu đầu của flip-flop gây dịch chuyển trạng thái Các bảng dịch chuyển trạng thái Thực hiện dùng flip-flop T Dùng các đầu vào của bảng dịch chuyển trạng thái để suy ra các đầu vào dựa trên bảng mã hóa trạng thái B ảng kích và K-map Sơ đồ mạch dùng flip-flop loại T Thự hiện dùng flip-flop JK Bảng kích thích và K-map Mạch điện thực hiện dùng JK Thiết kế số Các khối mạch tổ hợp: M ạch tuần tư đồng bộ: Vấn đề gán trạng thái, các máy trạng thái Mealy Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Vấn đề gán trạng thái Các ví dụ đã xét rất đơn giản và gán thẳng Vậy có phép gán nào khác có thể làm lời giải đơn giản hơn ? Thay đổi phép gán Thay đổi phép gán như sau: A=00, B=01, C=11, 10 ko được dùng. Kết quả Mạch được đơn giản hóa Vấn đề gán trạng thái Nhìn chung, chọn phép gán thích hợp sẽ có mạch đơn giản  low cost Mạch lớn sẽ rất khó tìn được phép gán tối ưu vì có quá nhiều biến CAD tools thường thực hiện gán dùng các kỹ thuật heuristic (thử từng phép) Gợi ý cho việc gán trạng thái Các phép gán cho trạng thái là lân cận nếu chúng khác nhau duy nhất một biến Các trạng thái có cùng trạng thái tiếp theo đối với một đầu vào nên được gán lân cận nhau Các trạng thái là trạng thái tiếp theo của cùng một trạng thái nên được gán lân cận Các trạng thái có cùng đầu ra ứng với đầu vào nào đó nên được gán là lân cận nhau Gợi ý cho việc gán trạng thái, cont. Các trạng thái là trạng thái tiếp theo của cùng một trạng thái nên được gán lân cận Các trạng thái có cùng trạng thái tiếp theo đối với một đầu vào nên gán lân cận nhau Ví dụ bảng trạng thái Moore Nhớ một số điều sau: Gán trạng thái ban đầu bằng 0..0 (đầu ra flip-flop) Xem xét theo 1 và 2 trước Nếu thấy có 3 hoặc 4 trạng thái lân cận nhau, đặt các trạng thái này vào nhóm 4 ô vuông trên Map 1 và 2 quan trọng hơn 3 Bảng dịch chuyển trạng thái Mã hóa trạng thái theo hướng dẫn Mealy model Đầu ra phụ thuọc vào trạng thái hiện tại và đầu vào Sơ đồ trạng thái Mealy Đầu ra không còn được kết hợp với trạng thái cụ thể nữa mà kết hợp với dịch chyển giữa các trạng thái Ví dụ cho trường hợp detect w=11 Bảng trạng thái mô hình Mealy Bảng trạng thái của Mealy model khác với Moore model chỉ ở chỗ đầu ra được view thế nào Bảng trạng thái được gán Bài tập Xây dựng sơ đồ trạng thái Mealy để nhận biết chuối w=101 Thiết kế số Các khối mạch tổ hợp: VHDL cho mạch tuần tư đồng bộ Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Dùng gói Flip-flop D Mã VHDL cho gated D lached Mã cho flip flop D Mã cho flip flop D (cách khác) Flip flop D có reset đồng bộ Flip flop D có đâu vào MUX Thanh ghi dịch 4-bit Thanh ghi dịch 4-bit (cách khác) Bộ đếm tăng 4-bit Bộ đếm tăng 4-bit có load Thiết kế số Các khối mạch tổ hợp: Thiết kế FSM dùng CAD tools Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Thiết kế FSM dùng CAD tools VHDL cung cấp một số cách tạo để thiết kế FSM Không có cách chuẩn nào cho địng nghĩa một FSM Tiếp cận cơ bản: Người dùng tạo ra dạng dữ liệu để biểu diễn các trạng thái có thể trong FSM Tín hiệu này biểu diễn các đầu ra (biến trạng thái) của flip flop Chương trình dịch VHDL chọn số flip flop phù hợp trong quá trình tổ hợp Gán trạng thái có thể được thực hiện bởi bộ dịch hoặc có thể là người dùng chỉ ra Các kiểu dữ liệu do người dùng chỉ ra Từ khóa TYPE được dùng để định nghĩa kiểu dữ liệu mới dùng để biểu diễn các trạng thái trong FSM Kiểu dữ liệu này có thể nhận 3 giá trị khác nhau: A, B và C Từ khóa Tên kiểu dữ liệu Các biến cho kiểu dl này Biểu diễn các trạng thái SIGNAL được định nghĩa với kiểu trạng thái như đã định nghĩa để biẻu diễn đầu ra của flip flop Ví dụ thiết kế Tạo đoạn VHDL cho mạch phát hiện chuỗi 11 ở đầu vào w Ví dụ thiết kế, cont Ví dụ thiết kế, cont Mã VHDL kiểu khác Cách khác này mô tả mạch trong VHDL định nghĩa hai tín hiệu biểu diễn trạng thái của FSM Một tín hiệu y_present chỉ ra trạng thái FSM Tín hiệu thứ 2 y_next chỉ ra trạng thái tiếp theo Hai khai báo PROCESS được dùng Một mô tả bảng trạng thái mạch combinational Cái thứ 2 dùng mô tả các flip flop với y_present sẽ nhận giá trị y_next sau mỗi sường xung nhịp Mã VHDL kiểu khác, cont Chỉ ra phép gán trạng thái Như phần trước thì phép gán trạng thái được thực hiện bởi bộ dịch VHDL Người dùng có thể thực hiện gán dùng: Mã VHDL của Mealy FSM Mealy FSM có thể được mô tả tương tự với Moore FSM Dịch chuyển trạng thái được mô tả tương tự Ví dụ sơ đồ trạng thái Mealy phát hiện chuỗi 11 Mã VHDL cho Mealy detector Thiết kế số Tối thiểu hóa trạng thái Người trình bày: TS. Hoàng Mạnh Thắng TexPoint fonts used in EMF: A A A A A A Tối thiểu hóa trạng thái Với FSM đơn giản thì có thể dễ thấy qua sơ đồ trạng thái mà số trạng thái được dùng có thể tối thiểu hóa Với FSM phức tạp, sơ đồ trạng thái có thể có nhiều trạng thái cần để thực hiện chức năng yêu cầu Tối thiểu hóa các trạng thái được quan tâm để tối thiểu hóa mạch Thay vì cố đưa ra các trạng thái nào tương đương, thường dễ hơn đưa ra các trạng thái không tương đương  định nghĩa thủ tục tối ưu Trạng thái tương đương Hai trạng thái S i và S j là tương nếu đối với mọi chuỗi vào có thể, chúng cho ra cùng một giá trị đầu ra không quan tâm đến S i hay S j là trạng thái đầu Nếu đầu vào w=0 đưa vào FSM khi đang ở S i và FSM dịch sang S u , thì S u được đặt là 0-successor của S i Tương tự, nếu w=1 va FSM chuyển sang S y thì S y được gọi là 1-successor của S i Các successor của S i là k-successor của nó, với nhiều biến vào Tối thiểu hóa phân tách nhỏ Từ định nghĩa về tương đương, nếu S_i và S_j là tương đương thì tương ứng có k-successor tương đương Nó được dùng tạo ra thủ tục tối thiểu hóa liên quan đến các trạng thái như là các tập và sau đó phá vỡ các tập đó thành các partitions gồm các tập con không tương đương Định nghĩa: một partition gồm một hay nhiều bloc, mỗ block gồm một tập con các trạng thái có thể là tương đương, nhưng các trạng thái trong một block không tương đương với các trạng thái trong block khác Ví dụ tối thiểu hóa partition Xem bảng trạng thái sau Partition ban đầu gồm tấ cả các trạng thái Ví dụ tối thiểu hóa partition, cont Partition tiếp theo tách các trạng thái có các đầu ra khác nhau Bây giờ xem xét tất cả 0- và 1- successor của tất cả các trạng thái trong mỗ block Với (ABD), 0-successors là (BDB): vẫn cùng một block  xem xét A,B và D vẫn còn tương đương 1-successors của (ABD) là (CFG)  xem xét A,B và D vẫn còn tương đương Tiếp theo xét đên (CEFG) Ví dụ tối thiểu hóa partition, cont P_2=(ABD)(CEFG) Đối với (CEFG), 0-successors là (FEFF), tất cả trong cùng block trong P_2 C,E,F và G vẫn còn tương đương 1-successors là (ECDG), chúng ko cùng trong một block ít nhất có một trạng thái trong (CEFG) không tương đương với các trạng thái kia F phải khác C, E, G bởi 1-successor, D, thuộc khối khác E, C và G Do đó, P_3=(ABD)(CEG)(F) Ở đây, ta biết rằng trạng thái F là duy nhất Ví dụ tối thiểu hóa partition, cont P_3=(ABD)(CEG)(F) Qúa trình được lặp lại và cuối cùng nhận được P_5=(AD)(B)(CEG)(F) A và D tương đương nhau, C,E và G cũng vậy Bảng trạng thái có thể được viết lại bằng cách xóa bỏ các hàng D, E và G Kết quả Bài tập Xét các trạng thái tương đương trong sơ đồ trạng thái sau