Giáo trình Thiết kế mạch logic số - Chương III: Thiết kế các khối logic tổ hợp và tuần tự thường gặp

54 trang ngocly 2540

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Thiết kế mạch logic số - Chương III: Thiết kế các khối logic tổ hợp và tuần tự thường gặp", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_thiet_ke_mach_logic_so_chuong_iii_thiet_ke_cac_kh.pdf

Nội dung text: Giáo trình Thiết kế mạch logic số - Chương III: Thiết kế các khối logic tổ hợp và tuần tự thường gặp

Chương III: Thiết kế các khối logic tổ hợp và tuần tự thường gặp 1. Khối cộng/trừ 1.1. Khối cộng đơn giản Khối cộng đơn giản: thực hiện phép cộng giữa hai số được biểu diễn dưới dạng std_logic_vector hay bit_vector. Các cổng vào gồm hạng tử A, B, bit nhớ Cin, các cổng ra bao gồm tổng Sum, và bit nhớ ra Cout: A B Cin Cout Σ Sum Hình 2.6: Sơ đồ khối bộ cộng Hàm cộng có thể được mô tả trực tiếp bằng toán tử “+” mặc dù với kết quả này thì mạch cộng tổng hợp ra sẽ không đạt được tối ưu về tốc độ, mô tả VHDL của bộ cộng như sau: Bo cong don gian library IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.STD_LOGIC_ARITH.ALL; use IEEE.STD_LOGIC_UNSIGNED.ALL; entity adder32 is port( Cin : in std_logic; A : in std_logic_vector(31 downto 0); B : in std_logic_vector(31 downto 0);
SUM : out std_logic_vector(31 downto 0); Cout: out std_logic ); end adder32; architecture behavioral of adder32 is signal A_temp : std_logic_vector(32 downto 0); signal B_temp : std_logic_vector(32 downto 0); signal Sum_temp : std_logic_vector(32 downto 0); begin A_temp <= '0'& A; B_temp <= '0'& B; plus: process (A_temp, B_temp, Cin) begin sum_temp <= a_temp + b_temp + Cin; end process plus; SUM <= sum_temp(31 downto 0); Cout <= sum_temp(32); end behavioral; Kết quả mô phỏng cho thấy giá trị đầu ra Sum và Cout, thay đổi tức thì mỗi khi có sự thay đổi các giá trị đầu vào A, B hoặc Cin. Hình 2.7: Kết quả mô phỏng bộ cộng 1.2. Khối trừ Vì các số có dấu trên máy tính được biểu diễn dưới dạng số bù 2 (2’complement), do đó để thực hiện phép trừ A-B thì tương đương với thực hiện A + bù2(B) Xét ví dụ A = 10 = 1010, B = 5 = 0101 biểu diễn dưới dạng số có dấu 5-bit ta phải thêm bit dấu bằng 0 vào trước. A = 01010, Bù2(A) = not (A) + 1 = 10101 + 1 = 10110 B = 00101, Bù2(B) = not (B) + 1 = 11010 + 1 = 11011
Tính A – B: A 01010 01010 - = - = + B 00101 11011 1 00101 Loại bỏ bit nhớ ở kết quả cuối cùng ta được A – B = 00101 = 5. Tính B – A: B 00101 00101 - = - = + A 01010 10110 0 11011 Loại bỏ bit nhớ ta được B – A = 11101, đây là số âm, muốn tính giá trị tuyệt đối để kiểm tra lại lấy bù 2 của 11101 Bù 2 (11101) = 00100 + 1 = 00101 = 5 vậy B – A = -5 Dựa trên tính chất trên của số bù hai ta chỉ cần thay đổi một chút trong cấu trúc của bộ cộng để nó có khả năng thực hiện cả phép cộng lẫn phép trừ mà không phải thay đổi nhiều về cấu trúc phần cứng. Tại đầu vào có thêm tín hiệu SUB, tín hiệu này quyết định sẽ thực hiện phép cộng hay phép trừ. Khi SUB = 1 để lấy bù 2 của B sẽ lấy đảo B và cho giá trị đầu vào Cin =1, để hiện thực trên mạch cấu trúc bộ cộng được bổ xung một khối MUX trước cổng B, khối này có hai đầu vào là B và not B, nếu SUB= 0 thì B được chọn, nếu SUB = 1 thì not B được chọn. Đầu vào Cin được OR với SUB trước khi vào bộ cộng.
Cin A B Sub MUX Cout Σ Sum Hình 2.8: Sơ đồ khối bộ cộng trừ đơn giản Trong mã nguồn cho module cộng/trừ adder_sub.vhd sử dụng bộ cộng adder32 như một module con (component). Bo cong trừ đơn giản library IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.STD_LOGIC_ARITH.ALL; use IEEE.STD_LOGIC_UNSIGNED.ALL; entity adder_sub is port( SUB : in std_logic; Cin : in std_logic; A : in std_logic_vector(31 downto 0); B : in std_logic_vector(31 downto 0); SUM : out std_logic_vector(31 downto 0); Cout: out std_logic ); end adder_sub; architecture rtl of adder_sub is signal B_temp : std_logic_vector(31 downto 0); signal Cin_temp : std_logic; component adder32 is
port ( Cin : in std_logic; A : in std_logic_vector(31 downto 0); B : in std_logic_vector(31 downto 0); SUM : out std_logic_vector(31 downto 0); Cout : out std_logic ); end component; begin Cin_temp <= SUB or Cin; MUX32: process (B, SUB) begin if SUB = '1' then B_temp <= not B; else B_temp <= B; end if; end process MUX32; add: component adder32 port map (Cin_temp, A, B_temp, SUM, Cout); end rtl; 1.3. Khối cộng thấy nhớ trước. Độ trễ tổ hợp của khối cộng gây ra bởi chuỗi bit nhớ, bộ cộng nối tiếp có đặc điểm là độ trễ cao do đặc điểm của chuỗi bit nhớ là bit nhớ sau phải đợi bit nhớ trước nó. A B Cout Sum Cin Hình 2.9: Sơ đồ khối bộ cộng 1 bit đầy đủ Như thấy trên hình vẽ thì thời gian trễ của chuỗi bit nhớ phải thông qua tối thiểu một cổng AND và một cổng OR, nếu là bộ cộng 32-bit thì tổng thời gian trễ là thời gian trễ của 32 cổng AND và 32 cổng OR. Trên thực tế độ trễ của cổng AND, cổng OR gần tương đương nên để đơn giản ta xem độ trễ của một trong hai cổng này là một lớp trễ hay một level trễ logic.
Như vậy bộ cộng nối tiếp có 32x2 = 64 lớp trễ. Phép cộng là một phép toán cơ bản và sử dụng nhiều do vậy việc nghiên cứu, sử dụng các thuật toán tăng tốc bộ cộng đã và đang được nghiên cứu rất nhiều. Trong phần này ta xem xét một thuật toán phổ biến nhằm rút ngắn thời gian thực hiện tính toán chuỗi bit nhớ là thuật toán thấy nhớ trước (Crarry Look- Ahead). Thuật toán này sử dụng sơ đồ toán trong đó phát huy tối đa các phép toán song song cho các đại lượng trung gian độc lập với nhau nhằm giảm thời gian đợi giữa các bit nhớ. Giả sử các đầu và là a(31:0), b(31:0) và đầu vào Cin. Khi đó định nghĩa: gi = ai and bi = ai .bi – nhớ phát sinh (generate carry) Nếu ai, bi bằng 1 thì gi bằng 1 khi đó sẽ có bit nhớ sinh ra ở vị trí thứ i của chuỗi. pi = ai or bi = ai + bi – nhớ lan truyền (propogation carry). Nếu hoặc ai, bi bằng 1 thì ở vị trí thứ i bít nhớ sẽ được chuyển tiếp sang vị trí i+1, nếu cả hai ai, bi bằng 0 thì chuỗi nhớ trước sẽ dừng lại ở vị trí i. Các giá trị p, g có thể được tính song song sau một lớp trễ. Từ { nghĩa của pi và gi có thể xây dựng công thức cho chuỗi nhớ như sau, gọi ci là bit nhớ sinh ra ở vị trí thứ i. Khi đó ci = 1 nếu hoặc gi bằng 1 nghĩa là có sinh nhớ tại vị trí này, hoặc có một bit nhớ sinh ra tại vị trí thứ -1≤ j < i gj = 1 (với quy uớc g-1 = Cin) và bit nhớ này lan truyền qua các bít tương ứng từ j+1, j+2 , i. nghĩa là tích gj . pj+1 .pj+2 .pi = 1. Ví dụ bit nhớ ở vị trí thứ 0 là c0 = 1 nếu như có nhớ sang vị trí thứ 1 và bằng 0 nếu như không có nhớ. C0 bằng 1 nếu như hoặc tại vị trí 0 có sinh nhớ g0 = 1, hoặc có nhớ của Cin và nhớ này được “lan truyền” qua vị trí thứ 0 Cin = 1 và P0 = 1. Công thức cho các bit nhớ có thể viết theo quy luật sau: c0 = g0 + Cin . p0 , c1 = g1 + g0 . p1 + Cin . p0 . p1 = g1 + c0 .p1 , c2 = g2 + g0 . p1 . p2 + g1 . p2 + Cin . p0 . p1 . p2 = g2 + c1 .p2 , (1)
c3 = g3 + g0 . p1 . p2 . p3 + g1 . p2 . p3 + g2 . p3 + Cin . p0 . p1 . p2 . p3= g3 + c2 .p3 , Theo công thức trên thì các giá trị bit nhớ sau vẫn phụ thuộc vào giá trị bit nhớ trước, ví dụ để tính c0, c1, c2, c3 thì phải có Cin xác định. Sự phụ thuộc này là tự nhiên và không thể thay đổi. Tuy vậy ta có thể rút ngắn thời gian tính các giá trị c bằng cách tính trước các giá trị trung gian mà không phụ thuộc Cin. Cụ thể ta sẽ xây dựng khối CLA tính các đại lượng trung gian sau từ đầu vào A(3:0), B(3:0) pi = ai + bi (với i =0 -3) gi = ai . bi (với i =0 -3) p01 = p0 . p1 p02 = p0 . p1. p2 p03 = p0 . p1 . p2 . p3 g01 = g1 + g0 . p1 g02 = g2 + g0 . p1 . p2 + g1 . p2 g03 = g3 + g0 . p1 . p2 . p3 + g1 . p2 . p3 + g2 . p3 = g01p23+g23 Có thể phân tích được độ trễ của một CLA như sau Level p G 1 pi = ai + bi (với i =0 -3) gi = ai . bi (với i =0 -3) 2 p01, p12, p23 g0p1, g1p2, g2,p3 3 P03 g01, g23 = (g3+g2p3) 4 g02, g01p23 5 g03 Có thể tính được để tính xong p03 phải cần 3 levels trễ logic, để tính được g03 cần 5 levels trễ logic.
Ta viết lại công thức cho các bit nhớ c3, và tương tự cho c7, c11, c15 như sau c3 = g03 + Cin . p03 c7 = g47 + g03 .p47 + Cin . p03 . p47 c12 = g811 + g47 . p811 + g03 .p47 . p811 + Cin . p03 . p47 . p811 c15 = g1215 + g811 . p1215 + g47 . p811 . p1215 + g03 .p47 . p811 . p1215 + Cin . p03 . p47 . p811. p1215 Trong đó các đại lượng g03, p03, g47, p47 , g811, p811, g1215, p1215 được tính song song. Các công thức trên hoàn toàn trùng lặp với công thức tính bit nhớ cho một bộ cộng 4 bit (1), do vậy khối trên lại được xây dựng trên cơ sở một khối CLA. Từ bảng tính độ trễ của một CLA có thể suy ra để tính được c3 cần 6 levels logic, tính được c7 cần 7 levels logic, c11 cần 8 levels logic, c15 cần 9 levels logic Nếu so sánh với bộ cộng 16 bít cần 16 x 2 = 32 levels logic thì đó đã là một sự cải thiện đáng kể về tốc độ, bù lại ta sẽ mất nhiều tài nguyên hơn do việc sử dụng để tính các giá trị trung gian trên. Trên thực tế bộ cộng Carry Look Ahead Adder thường được xây dựng từ các bộ 4 bít CLA, mỗi bộ này có nhiệm vụ tính toán các giá trị trung gian. Sơ đồ khối của chuỗi bit nhớ như sau.
A(15:12) B(15:12) A(11:8) B(11:8) A(7:4) B(7:4) A(3:0) B(3:0) Cin PG2 PG2 PG1 PG0 g(15:12) p(15:12) g(11:8) p(11:8) g(7:4) p(7:4) g(3:0) p(3:0) CLA3 CLA2 CLA1 CLA0 g1512 p1512 g118 p118 g74 p74 g30 p30 A(3:0) B(3:0) CLA4 Hình 2.10: Sơ đồ khối chuỗi bit nhớ dùng CLA 2. Thanh ghi Thanh ghi là chuỗi các phần tử nhớ được ghép với nhau và là thành phần không thể thiếu của các thiết kế mạch dãy, đặc điểm quan trọng nhất để phân biệt thanh ghi với các khối tổ hợp là thanh ghi bao giờ cũng chịu sự điều khiển của xung nhịp đồng bộ, giá trị đầu ra là giá trị lưu trong các ô nhớ của thanh ghi được gán bằng giá trị của đầu vào tại các thời điểm nhất định theo điều khiển xung nhịp đồng bộ, nếu so sánh với khối tổ hợp thì giá trị đầu ra của mạch tổ hợp thay đổi tức thì ngay sau khi có sự thay đổi của các đầu vào. Thường gặp và phổ biến nhất là các thanh ghi sử dụng D-flipflop và làm việc đồng bộ theo sườn dương của xung nhịp hệ thống. Giản đồ sóng và biểu diễn của thanh ghi thể hiện ở hình dưới đây:
Hình 2.11: Sơ đồ khối và giản đồ sóng của thanh ghi Như quan sát trên giản đồ sóng, giá trị đầu ra Q thay đổi chỉ tại các thời điểm có sườn dương của tín hiệu clk, tại thời điểm đó giá trị của Q sẽ được gán bằng giá trị đầu vào D của thanh ghi. Tại các thời điểm khác giá trị của Q được giữ không đổi. Mô tả thanh ghi trên VHDL khá đơn giản như sau: register 32-bit library IEEE; use IEEE.STD_LOGIC_1164.ALL; entity reg_32 is port( D : in std_logic_vector(31 downto 0); Q : out std_logic_vector(31 downto 0); CLK : in std_logic; RESET : in std_logic ); end reg_32; architecture behavioral of reg_32 is begin reg_p: process (CLK, RESET) begin if RESET = '1' then Q '0'); elsif CLK = '1' and CLK'event then Q <= D; end if; end process reg_p; end behavioral;
Cấu trúc if CLK = '1' and CLK'event then quy định thanh ghi làm việc theo tín hiệu sườn dương của xung nhịp clk, một cách viết khác tương đương là if rising_edge(clk) then 3. Bộ cộng tích lũy Bộ cộng tích lũy là sự kết hợp giữa bộ cộng và thanh ghi, cấu trúc của khối này thể hiện ở hình dưới đây: clk, reset A B Σ Sum REG1 Q Hình 2.12: Sơ đồ khối bộ cộng tích lũy Đầu ra của bộ cộng được nối với đầu vào của thanh ghi, còn đầu ra của thanh ghi được dẫn vào cổng B của bộ cộng, sau mỗi xung nhịp đồng hồ giá trị này được cộng thêm giá trị ở cổng A và lưu lại vào thanh ghi. Với mô tả của bộ cộng và thanh ghi ở trên, mô tả của bộ cộng tích lũy như sau: accumullator library IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.STD_LOGIC_ARITH.ALL; use IEEE.STD_LOGIC_UNSIGNED.ALL; entity accumulator_32 is port( A : in std_logic_vector(31 downto 0); Q : buffer std_logic_vector(31 downto 0);
CLK : in std_logic; RESET : in std_logic ); end accumulator_32; architecture structure of accumulator_32 is signal sum32 : std_logic_vector(31 downto 0); signal Q_sig : std_logic_vector(31 downto 0); signal Cout : std_logic; signal Cin : std_logic; COMPONENT ADD_32 component adder32 is port ( Cin: std_logic; A : in std_logic_vector(31 downto 0); B : in std_logic_vector(31 downto 0); SUM : out std_logic_vector(31 downto 0); Cout: out std_logic ); end component; COMPONENT REG_32 component reg_32 is port ( D : in std_logic_vector(31 downto 0); Q : out std_logic_vector(31 downto 0); CLK : in std_logic; RESET: in std_logic ); end component; begin Q_sig <= Q; Cin <= '0'; add32: component adder32 port map (Cin, A, Q_sig, sum32, Cout); reg32: component reg_32 port map (sum32, Q, CLK, RESET); end structure; Kết quả mô phỏng thu được giản đồ sóng như sau:
Hình 2.13: Kết quả mô phỏng bộ cộng tích lũy Sau xung nhịp reset giá trị q của thanh ghi bằng 0, sau đó cứ mỗi xung nhịp giá trị này tăng thêm 17, bằng giá trị đầu vào của A. Quan sát trên giản đồ sóng cũng dễ dàng nhận thấy giá trị tại đầu ra q của thanh ghi bao giờ cũng chậm hơn giá trị đầu vào sum của thanh ghi một xung nhịp clk. 4. Bộ đếm Bộ đếm là một trường hợp đặc biệt của bộ cộng tích lũy, nếu ta cho đầu vào của bộ cộng A luôn nhận giá trị bằng 1 thì sau mỗi xung nhịp giá trị trong thanh ghi tăng thêm 1. Trong trường hợp đếm ngược thì cho giá trị của A bằng -1. Giá trị đếm là giá trị lưu trong thanh ghi còn xung đếm chính là xung nhịp hệ thống. Cách mô tả bộ đếm trên VHDL như sau: Counter library ieee; use ieee.std_logic_1164.all; use IEEE.STD_LOGIC_ARITH.ALL; use IEEE.STD_LOGIC_UNSIGNED.ALL; entity counter4 is port ( count :out std_logic_vector( 3 downto 0); enable :in std_logic; clk :in std_logic; Dau vao xung đếm clock reset :in std_logic ); end entity; architecture rtl of counter4 is signal cnt :std_logic_vector ( 3 downto 0) := "0000"; begin process (clk, reset) begin if (reset = '1') then cnt <= "0000";
elsif (rising_edge(clk)) then if (enable = '1') then cnt <= cnt + 1; end if; end if; end process; count <= cnt; end architecture; Trong đoạn mã trên tín hiệu reset được mô tả ở chế độ không đồng bộ, nghĩa là khi reset = 1 thì ngay lập tức giá trị đếm cnt bị reset về 0. Trong trường hợp đồng bộ thì giá trị đếm bị reset chỉ tại sườn dương của xung nhịp clk. Ngoài tín hiệu reset, bộ đếm còn được điều khiển bởi enable, nếu enable =1 thì bộ đếm làm việc, nếu enable = 0 thì giá trị đếm được giữ nguyên. Bộ đếm trên ở chế độ đếm sẽ đếm nhị phân với Kđ = 2i, các giá trị đếm thay đổi từ từ 0 đến 15 sau đó lại bắt đầu đếm từ 0, trong trường hợp muốn đặt Kd bằng một giá trị khác cần thêm một khối tổ hợp làm nhiệm vụ so sánh giá trị đếm với Kd để đặt lại giá trị đếm như ở mô tả dưới đây, bộ đếm với Kd = 10: Counter set library ieee; use ieee.std_logic_1164.all; use IEEE.STD_LOGIC_ARITH.ALL; use IEEE.STD_LOGIC_UNSIGNED.ALL; entity counter4_set is port ( count :out std_logic_vector( 3 downto 0); enable :in std_logic; clk :in std_logic; reset :in std_logic ); end entity; architecture rtl of counter4_set is signal cnt :std_logic_vector ( 3 downto 0) := "0000"; begin process (clk, reset) begin if (reset = '1') then cnt <= "0000"; elsif (rising_edge(clk)) then if (enable = '1') then
if cnt = "1010" then –cnt = 10 thi reset cnt <= "0000"; else cnt <= cnt + 1; end if; end if; end if; end process; count <= cnt; end architecture; Kết quả mô phỏng của hai bộ đếm như sau: Hình 2.14: Kết quả mô phỏng các bộ đếm Các giá trị đếm bị reset đồng bộ về 0, sau đó đếm lần lượt từ 0 đến 8, tín hiệu enable sau đó bằng 0, nên giá trị này giữ nguyên, khi enable =1 các bộ đếm tiếp tục đếm, bộ đếm đặt lại trạng thái (count4_set) chỉ đếm đến 10 rồi quay lại đếm từ 0, trong khi bộ đếm bình thường (count2) đếm đến 15. 6. Bộ dịch và thanh ghi dịch. 6.1. Bộ dịch Shift_in Shift_value SHIFTER Hình 2.15: Kết quả mô phỏng các bộ đếm Bộ dịch là khối logic tổ hợp thực hiện động tác dịch chuỗi bít đầu vào, có tất cả 6 phép toán dịch gồm dịch trái logic, dịch trái số học, dịch phải logic, dịch phải
số học, dịch tròn trái, dịch tròn phải, chi tiết về các lệnh dịch này xem trong mục 5.3 của chương 2. Đầu vào của khối dịch gồm chuỗi nhị phân cần phải dịch shift_in và giá trị số lượng bit cần phải dịch shift_value. Đầu ra là giá trị chuỗi nhị phân sau khi thực hiện dịch. Khi viết mã cho bộ dịch lưu { nếu dùng các toán tử dịch của VHDL thì các chuỗi nhị phân dịch phải được khai báo dưới dạng bit_vector. Ví dụ dưới đây là một bộ dịch với đầu vào 32-bit: SHIFTER library IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.STD_LOGIC_arith.ALL; use IEEE.STD_LOGIC_unsigned.ALL; USE ieee.Numeric_STD.all; USE ieee.Numeric_BIT.all; entity shifter_32 is port( shift_in : in std_logic_vector(31 downto 0); shift_value: in std_logic_vector(4 downto 0); shift_out : out std_logic_vector(31 downto 0) ); end shifter_32; architecture behavioral of shifter_32 is signal shi: bit_vector(31 downto 0); signal sho: bit_vector(31 downto 0); signal sa : integer; begin shi <= TO_BITVECTOR(shift_in); sa <= CONV_INTEGER('0' & shift_value); sho <= shi sll sa; shift_out <= TO_STDLOGICVECTOR(sho); end behavioral; Ở ví dụ trên vì đầu vào dịch shift_in là giá trị 32-bit nên số bít dịch tối đa là 31, biểu diễn dưới dạng nhị phân cần 5-bit nên shift_value được khai báo là std_logic_vector(4 downto 0). Kết quả mô phỏng như sau:
Hình 2.15: Kết quả mô phỏng khối dịch tổ hợp Tương ứng với phần mô tả, giá trị shift_out bằng shift_in được dịch logic sang bên trái 3-bit. Phương pháp sử dụng trực tiếp toán tử dịch của VHDL không được một số trình tổng hợp không hỗ trợ, nghĩa là không tổng hợp được mạch, trong trường hợp đó khối dịch phải được viết chi tiêt hơn. Nhận xét rằng độ phức tạp của khối dịch trên nằm ở chỗ giá trị dịch là không xác định, nếu giá trị dịch xác định thì phép dịch có thể thực hiện hết sức dễ dàng bằng toán tử hợp &. Ví dụ để dịch chuỗi bit đi 4 bit logic sang phải shift_out = “0000” & shift_in(31 downto 4); Từ đó có thể xây dựng khối dịch bằng sơ đồ thuật toán đơn giản như sau. Giả sử ta cần thiết kế khối dịch cho dữ liệu dịch shift_in 32 bit, giá trị dịch shift_value được biểu diễn là 5 bit. Các bit của shift_value từ cao nhất tới thấp nhất sẽ được xét. Ví dụ, với bit đầu tiên shift_value(4) được đưa vào làm tín hiệu điều khiển cho khối chọn kênh thứ nhất, nếu shift_value(4) = 1 giá trị được chọn sẽ là đầu vào shift_in được dịch đi 16 bit bởi bộ dịch SH16, nếu shift_value(4) = 0 thì giá trị shift_in được chọn, nghĩa là đầu vào không bị dịch đi. Sơ đồ cứ tiếp tục như vậy cho đến bit cuối cùng shift_value(0), đầu ra của khối chọn kênh cuối cùng chính là giá trị shift_out.
Shift_in SH16 Shift16 Shift_value(4) Shift_in4 SH8 Shift8 Shift_value(3) Shift_in3 SH4 Shift4 Shift_value(2) Shift_in2 SH2 Shift2 Shift_value(1) Shift_in1 SH1 Shift1 Shift_value(0) Shift_out Hình 2.16: Sơ đồ thuật toán khối dịch đơn giản 6.1. Thanh ghi dịch Tương tự như trường hợp của khối cộng tích lũy, kết hợp khối dịch và thanh ghi ta được cấu trúc của thanh ghi dịch như ở hình sau:
clk, reset WE D Shift_value Shift_in SHIFTER Shift_out MUX REG1 Q Hình 2.17: Sơ đồ thuật toán khối dịch đơn giản Thanh ghi có thể làm việc ở hai chế độ, chế độ thứ nhất dữ liệu đầu vào được lấy từ đầu vào D, chế độ thứ hai là chế độ dịch, khi đó dữ liệu đầu vào của thanh ghi lấy từ khối dịch, đầu ra của thanh ghi được gán bằng đầu vào của khối dịch. Ở chế độ này dữ liệu sẽ bị dịch mỗi xung nhịp một lần. Mã mô tả thanh ghi dịch như sau: SHIFTER_REG module library IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.STD_LOGIC_ARITH.ALL; use IEEE.STD_LOGIC_UNSIGNED.ALL; entity shift_reg_32 is port( shift_value : in std_logic_vector(4 downto 0); D : in std_logic_vector(31 downto 0); Q : buffer std_logic_vector(31 downto 0); CLK : in std_logic; WE : in std_logic; RESET : in std_logic ); end shift_reg_32; architecture structure of shift_reg_32 is signal shift_temp : std_logic_vector(31 downto 0); signal D_temp : std_logic_vector(31 downto 0); COMPONENT SHIFTER
component shifter_32 is port ( shift_in : in std_logic_vector(31 downto 0); shift_value : in std_logic_vector(4 downto 0); shift_out : out std_logic_vector(31 downto 0) ); end component; COMPONENT REG_32 component reg_32 is port ( D : in std_logic_vector(31 downto 0); Q : out std_logic_vector(31 downto 0); CLK : in std_logic; RESET: in std_logic ); end component; begin process (WE, shift_temp) begin if WE = '1' then D_temp <= D; else D_temp <= shift_temp; end if; end process; sh32: component shifter_32 port map (Q, shift_value, shift_temp); reg32: component reg_32 port map (D_temp, Q, CLK, RESET); end structure; Kết quả mô phỏng ra như sau: Hình 2.18: Kết quả mô phỏng thanh ghi dịch Khi tín hiệu WE bằng 1 (mức tích cực cao) giá trị thanh ghi được gán bằng giá trị của cổng D, su đó E chuyển về thấp, giá trị trong thanh ghi Q được dich sang trái mỗi lần shift_value = “00101” = 5 bit.
7. Khối nhân số nguyên Phép nhân cũng là một phép toán rất hay sử dụng trong tính toán xử lý, việc thiết kế khối nhân phức tạp và cần nhiều tài nguyên hơn khối cộng, trên thực tế ở một số dòng vi xử l{ đơn giản phép nhân được thực hiện thông qua khối cộng bằng phần mềm. Trong các vi xử lý hiện đại thì khối nhân được hỗ trợ phần cứng hoàn toàn. Dưới đây ta sẽ lần lượt nghiên cứu hai thuật toán cơ bản của khối nhân. Các thuật toán khác có thể tham khảo trong các tài liệu [4], [8] 7.1. Nhân số nguyên không dấu dùng phương pháp cộng dịch Khối nhân dùng thuật toán cộng dịch (shift-add multiplier), xét phép nhân hai số 4 bit không dấu như sau 0101 - số bị nhân multiplicand 0111 - số nhân multiplier 0101 - tích riêng partial products 0101 0101 0000 0100011 - kết quả nhân product Theo sơ đồ trên thì số bị nhân (multiplicand) sẽ được nhân lần lượt với các bit từ thấp đến cao của số nhân (multiplier), kết quả của phép nhân này bằng số bị nhân “0101” nếu bit nhân tương ứng bằng ‘1’, và bằng “0000” nếu như bit nhân bằng ‘0’, như vậy bản chất là thực hiện hàm AND của bit nhân với 4 bit của số bị nhân. Để thu được các tích riêng (partial products) ta phải dịch các kết quả nhân lần lượt sang trái với bít nhân thứ 0 là 0 bit, thứ 1 là 1 bít, thứ 2 là hai bit và thứ 3 là 3 bít. Kết quả nhân (product) thu được sau khi thực hiện phép cộng cho 4 tích riêng. Sơ đồ trên giúp chúng ta hiểu phép nhân được thực hiện như thế nào nhưng khi xây dụng phần cứng dựa trên sơ đồ này có một nhược điểm là các tích riêng bị dịch bởi các giá trị dịch khác nhau. Nếu xây dựng khối nhân thuần túy là khối tổ hợp thì để nhân hai số 4 bit cần 4 khối dịch và 3 khối cộng 8 bit, nếu số lượng bit của các nhân tử tăng lên thì tài nguyên phần cứng tăng lên rất nhiều và
không phù hợp với thực tế. Nếu xây dựng khối nhân theo dạng mạch tổ hợp dùng thanh ghi dịch và bộ cộng tích lũy thì cần thêm một bộ đếm để đếm giá trị dịch, việc này làm cho khối nhân trở nên phức tạp. Giải pháp để đơn giản hóa cấu trúc của khối nhân có thể sử dụng một trong hai sơ đồ thuật toán cộng dịch trái, và cộng dịch phải như minh họa dưới đây. Thuật toán cộng dịch phải: a 0 1 0 1 x 0 1 1 1 P(0) 0 0 0 0 +x0.a 0 1 0 1 2p(1) 0 0 1 0 1 P(1) 0 0 1 0 1 +x1.a 0 1 0 1 2p(2) 0 0 1 1 1 1 P(2) 0 0 1 1 1 1 +x2.a 0 1 0 1 2p(3) 0 1 0 0 0 1 1 P(3) 0 1 0 0 0 1 1 +x3.a 0 0 0 0 P(4) 0 0 1 0 0 0 1 1 P 0 0 1 0 0 0 1 1 Với sơ đồ này thì các tích riêng được tính từ phải qua trái, tức là số bị nhân sẽ được nhân lần lượt với x0, x1, x2, x3. Các giá trị p(i) là giá trị tích lũy của các tích riêng. Giá trị p(0) được khởi tạo bằng 0. P(1) = p(0) + x0.a, đây là phép cộng 4 bit và p(1) cho ra kết quả 5 bit trong đó bit thứ 5 là bit nhớ, riêng trường hợp p(1) thì bit nhớ này chắc chắn bằng 0 do p(0) = 0. Kết quả p(2) có 6 bit sẽ bằng kết quả phép cộng của x1.a đã dịch sang phải 1 bít và cộng với giá trị p(1). Nhận xét rằng bit cuối cùng của x1.a khi dịch sang trái luôn bằng 0 do vậy hay vì phải dịch x1.a sang phải 1 bit ta xem như p(1) đã bị dịch sang trái 1 bit, nghĩa là phải lấy 4 bit cao của p(1) cộng với x1.a. Kết quả thu được
của phép cộng này là một số 5 bit đem hợp với bit cuối cùng của p(1) sẽ thu được p(2) là một số 6 bit. Tiếp tục như vậy thay vì dịch x2.a ta lại xem như p(2) dịch sang trái 1 bit và cộng 4 bit cao của p(2) với x2.a, kết quả phép cộng hợp với 2 bit sau của p(2) thu được p(3) là một số 7 bit. Làm như vậy với tích riêng cuối cùng thu được kết quả product là một số 8 bit. Như vậy trên sơ đồ trên ta luôn cộng 4 bít cao của kết quả tích lũy với kết quả nhân. Sở dĩ được gọi là phép cộng dịch phải vì các kết quả nhân được tính từ trái qua phải và bị hiểu là luôn dịch sang bên phải 1 bit trước khi cộng với giá trị tích lũy, mặc dù trên thực tế thì kết quả tích lũy mới là đối tượng bị dịch. Sơ đồ hiện thực hóa sử dụng thanh ghi dịch và bộ cộng tích lũy như sau: K+1bit K-1 bit Multiplicand product Multiplier K bit K-1 bit 0 SHIFT_REG MUX Kbit Σ k bit Hình 2.19: Sơ đồ hiện thực hóa thuật toán nhân cộng dịch phải cho hai số k-bit Khối cộng có một đầu vào cố định k bit là đầu vào tích riêng, để tính các tích riêng sử dụng một khối chọn kênh MUX k-bit, khối này chọn giữa giá trị số bị nhân (multiplicand) và 0 phụ thuộc vào bit tương ứng của số nhân(multiplier) là 1 hay 0. Để đưa lần lượt các bit của số nhân vào khối chọn này thì giá trị của số nhân được lưu trong một thanh ghi dịch samg trái mỗi xung nhịp 1 bit.
Đầu vào thứ hai của bộ cộng lấy từ k bit cao của thanh ghi 2k-bit. Thanh ghi này trong qua trình làm việc lưu trữ kết quả tích lũy của các tích riêng. Đầu vào của thanh ghi này bao gồm K+1 bit cao lấy từ kết quả của bộ cộng tích lũy còn K-1 bit thấp lấy từ bít thứ K-1 đến 1 của chính nó ở xung nhịp trước đó, nói một cách khác, đây là thanh ghi có phần K bit thấp hoạt động trong chế độ dịch sang phải 1 bit, còn K+1 bit cao làm việc ở chế độ nạp song song. Phép nhân được thực hiện sau K xung nhịp, kết quả lưu trong thanh ghi 2k- bit. Thuật toán cộng dịch trái: a 0 1 0 1 x 0 1 1 1 P(0) 0 0 0 0 2 p(0) 0 0 0 0 0 +x3.a 0 0 0 0 p(1) 0 0 0 0 0 2P(1) 0 0 0 0 0 0 +x2.a 0 1 0 1 2p(2) 0 0 0 1 0 1 P(2) 0 0 0 1 0 1 0 +x2.a 0 1 0 1 2p(3) 0 0 0 1 1 1 1 P(2) 0 0 0 1 1 1 1 0 +x3.a 0 1 0 1 P 0 0 0 1 0 0 0 1 1 Sơ đồ cộng dịch trái khác sơ đồ cộng dịch phải ở chỗ các tích riêng được tính lần lượt từ trái qua phải, tức là từ bit cao đến bit thấp, kết quả tích lũy khi đó không phải dịch dịch sang trái trước khi cộng với kết quả nhân của bit kế tiếp. Kết quả tích lũy ban đầu được khởi tạo bằng p(0) = 0 và thực hiện dịch sang trái 1 bit trước khi cộng với x3.a để thu được p(1) là một số 5 bit. P(1) tiếp tục được dịch trái 1 bit và cộng với x2.a để thu được p(2) là một số 6 bít. Làm tương tự như vậy cho tới cuối ta thu được p là một số 8 bit.
Như vậy cũng giống như sơ đồ cộng dịch phải ở sơ đồ cộng dịch trái sẽ chỉ cần dùng một khối dịch cố định cho kết quả trung gian, điểm khác biệt là phép cộng ở sơ đồ này luôn cộng các bit thấp với nhau, bit nhớ của phép cộng này sẽ ảnh hưởng tới giá trị các bit cao nên buộc phải sử dụng một khối cộng 8 bit để thực hiện cộng. Sơ đồ hiện thực thuật toán cộng dịch trái trên phần cứng như sau: Multiplicand product 2K bit Multiplier 0 SHIFT_REG MUX Kbit SHIFT LEFT Σ 2k bit Hình 2.20: Sơ đồ hiện thực hóa thuật toán nhân cộng dịch trái Đối với sơ đồ dùng thuật toán cộng dịch trái, khối dịch cho số nhân phải là khối dịch phải mỗi xung nhịp một bit do các tích riêng được tính lần lượt từ trái qua phải. Khối cộng sẽ luôn là khối cộng 2k bit, mặc dù hạng tử thứ hai từ MUX k- bit chỉ thực sự biểu diễn bằng k-bit. Thanh ghi kết quả trung gian là thanh ghi 2K bit, Giá trị trong thanh ghi được dịch sang trái 1 bít bằng khối dịch trước khi đi vào khối cộng. 7.2. Nhân số nguyên có dấu Số có dấu trong máy tính được biểu diễn dưới dạng bù 2 (2s’complements) theo đó giá trị của một chuỗi bit được tính theo công thức: n-1 n-2 xn-1 xn-2 x1 x0 = -2 xn-1 +2 xn-2 + + 2x1 + x0 (2) trong đó xn-1xn-2 x1x0 là biểu diễn dưới dạng nhị phân.
Công thức trên đúng cho cả số âm lẫn số dương, nếu số là âm thì bit có trọng số lớn nhất xn-1 bằng 1 và ngược lai. Trong hệ thống biểu diễn này định nghĩa: Bù 1 của số đó xn-1xn-2 x1x0 là số nhận bởi các bit này nhưng lấy đảo Bù 2 của số đó xn-1xn-2 x1x0 lá số bù 1 của số đó cộng thêm 1. Một tính chất quan trọng của số bù 2 là số bù hai của một số A bằng số đối của số đó, hay nói cách khác bù2 (A) + A = 0. Tính chất này cho phép ta xây dựng khối nhân số có dấu bằng cách đơn giản nhất là đưa các số về dạng biểu diễn không âm, hay trị tuyệt đối của các số đó và nhân với nhau sử dụng một trong các sơ đồ trên. Riêng bit dấu của kết quả được tính riêng. Nếu như hai số nhân và số bị nhân khác dấu để đưa về dạng biểu diễn đúng của kết quả cần lấy bù 2 của kết quả phép nhân không dấu. Cách thực hiện trên khá đơn giản tuy vậy đỏi hỏi nhiều tài nguyên logic cũng như tăng độ trễ của khối nhân do phải bổ xung các khối tính bù 2 vào đầu và cuối chuỗi tính toán. Ta lại có nhận xét rằng nếu biểu diễn giá trị a dưới dạng số bù hai bằng k bit, giá trị này được biểu diễn tương ứng bằng k+m bit bằng cách điền vào m bít mở rộng bên trái giá trị dấu (bit thứ k-1) của số đó, toàn bộ k bit bên phải giữ nguyên. Động tác bổ xung các dấu như thế được gọi là mở rộng có dấu (signed- extend) Ví dụ -4 = (1100)4 bit = (11111100)8-bit Với nhận xét này có thể thực hiện một vài điều chỉnh nhỏ trong sơ đồ nhân công dịch để sơ đồ này cũng đúng với số có dấu. Yêu cầu là khi mở rộng các kết quả tích lũy cần phải mở rộng theo kiểu có dấu (signed-extend). Yêu cầu khác là khi số nhân là số âm thì khi nhân với bit dấu (bit cao nhất) thì theo công thức (2) kết quả thu được là số đối của số bị nhân hay là số bù 2 của số bị nhân. Nhược điểm của phương pháp này là phải thiết kế hai khối nhân riêng cho số có dấu và không dấu.
Xét ví dụ về phép nhân của hai số có dấu 4 bit dùng thuật toán cộng dịch phải. a 1 1 0 1 Bù 2 a = 0011 (a = -3) x 1 1 0 0 x = -4 P(0) 0 0 0 0 +x0.a 0 0 0 0 2p(1) 0 0 0 0 0 vì p(1) >= 0 chèn thêm 0 vào trái P(1) 0 0 0 0 0 +x1.a 0 0 0 0 2p(2) 0 0 0 0 0 0 vì p(2) >= 0 chèn thêm 0 vào trái P(2) 0 0 0 0 0 0 +x2.a 1 1 0 1 2p(3) 1 1 1 0 1 0 0 vì p(2) =0 chèn thêm 0 vào trái P 0 0 0 0 1 1 0 0 = +12 Sơ đồ hiện thực khối nhân có dấu trên phần cứng như sau: SHIFTER _ SIGNED EXTEND Multiplicand 2s’ complement product 2K bit Multiplier 0 SHIFT_REG MUX Σ
Hình 2.21: Sơ đồ hiện thực hóa thuật toán nhân cộng dịch trái Về cơ bản sơ đồ này không khác nhiều so với sơ đồ nhân không dấu, điểm khác biệt là ở đây trước khi kết quả tích lũy được lưu vào thanh ghi trung gian thì được dịch và chèn các bit dấu mở rộng theo quy tắc đối với số có đấu ở khối SHIFTER SIGNED-EXTEND. Và MUX thực hiện lựa chọn giữa 3 giá trị là số bị nhân, 0 và số đối của nó. Số đối của số bị nhân được chọn nếu bit nhân là bit dấu và bit này bằng 1. Một phương pháp khác để thực hiện phép nhân với số có dấu biểu diễn dưới dạng bù 2 là sử dụng mã hóa Booth. Ở đâu bước đầu ta sẽ xét mã hóa Booth ở cơ số 2. (Radix 2 Booth encoding). Để hiểu về mã hóa Booth quay trở lại với công thức tính giá trị cho số biểu diễn dạng bù 2. Công thức này có thể được biến đổi như sau: n-1 n-2 xn-1 xn-2 x1 x0 = -2 xn-1 +2 xn-2 + + 2x1 + x0 n-1 n-1 n-2 2 = -2 xn-1 + 2 xn-2 -2 xn-2 + + 2 x1 – 2 x1 + 2 x0 –x0 + 0 n-1 n-2 = 2 (- xn-1 + xn-2) +2 (-xn-2 + xn-3 )+ + 2(-x1 + x0) + (-x0 + 0) Từ đó xây dựng bảng mã như sau, cặp hai bit liên tiếp xi+1, xi sẽ được thay bằng giá trị bi = (-xi+1 + xi) với i = -1, n-2, và x-1 = 0. Bảng chuyển mã như sau: xi+1 xi Radix-2 booth encoding 0 0 0 0 1 1 1 0 -1 1 1 0 Theo bảng mã trên hai bit nhị phân tương ứng sẽ được mã hóa bằng các giá trị 0, 1, -1. Ví dụ chuỗi bit và mã hóa Booth cơ số hai tương ứng:
2’s complemnt 1 1 1 0 0 1 0 1 1 0 1 0 0 1(0) Radix-2 booth 0 0-1 0 1-1 1 0-1 1-1 0 1-1 Để thực hiện phép nhân số có dấu đầu tiên sẽ mã hóa số nhân dưới dạng mẫ Booth, khi thực hiện phép nhân nếu bit nhân là 0, 1 ta vẫn làm bình thường, nếu bit nhân là -1 thì kết quả nhân bằng số bù hai của số bị nhân. Có thể áp dụng mã hóa Booth cho cả sơ đồ cộng dịch trái và cộng dịch phải và hỗ trợ thao tác mở rộng có dấu. Sơ đồ trên có thể sửa đổi một chút để nó vẫn đúng với cả phép nhân với số không dấu, khi đó ta bổ xung thêm bit 0 vào bên trái của số bị nhân và chuỗi Booth sẽ dài hơn một bit. 2’s complemnt (0) 1 1 1 0 0 1 0 1 1 0 1 0 0 1(0) Radix-2 Booth (1) 0 0-1 0 1-1 1 0-1 1-1 0 1-1 Ví dụ đầy đủ về phép nhân có dấu sử dụng mã hóa Booth cơ số 2 như sau: a 1 1 0 1 Bù 2 a = 0 0 1 1 (a = -3) x 0 1 1 1 x = + 7 b 1 0 0-1 Radix 2 booth encoding of x P(0) 0 0 0 0 +b0.a 0 0 1 1 2p(1) 0 0 0 1 1 P(1) 0 0 0 1 1 +b1.a 0 0 0 0 2p(2) 0 0 0 0 1 1 P(2) 0 0 0 0 1 1 +x2.a 0 0 0 0 2p(2) 0 0 0 0 0 1 1 P(3) 0 0 0 0 0 1 1 +x3.a 1 1 0 1 2p(3) 1 1 0 1 0 1 1 P 1 1 1 0 1 0 1 1 = -21 Sơ đồ của khối nhân có dấu dùng mã hóa Booth cơ số 2
SHIFTER _ SIGNED 2s’ complement EXTEND Multiplicand product RADIX 2 REG Multiplier BOOTH ENCODING 0 SHIFT_REG MUX Σ Hình 2.22: Sơ đồ hiện thực hóa thuật toán nhân dùng mã hóa Booth cơ số 2 Số nhân được đưa vào một khối mã hóa BOOTH theo cơ số 2, theo thuật toán thì khối này mã hóa số nhân thành các giá trị 1, 0, -1 nhưng trên thực tế phần cứng là tổ hợp giá trị 01, 00, 10. Phần còn lại của sơ đồ giống như sơ đồ nhân có dấu dùng thuật toán cộng dịch phải trình bày ở trên. 7.3. Khối nhân dùng mã hóa Booth cơ số 4 Mã hóa Booth cơ số 2 không được ứng dụng thực tế nhưng là cơ sở giúp hiểu các dạng mã hóa Booth cao hơn. Trong nỗ lực tăng tốc cho phép nhân trong phần cứng một trong những phương pháp là thực hiện nhân không phải từng bit của số nhân mà nhân với một nhóm bit cùng một lúc. Khối nhân theo cơ số 5 (Radix-4 multiplier) sử dụng sơ đồ nhân với cặp 2 bit, với cặp 2 bit thì có thể có 4 giá trị 0, 1, 2, 3. Dễ dàng nhận thấy các phép nhân một số với 0 bằng 0 với 1 bằng chính nó, nhân với 2 là phép dịch sang phải 1 bit, tuy vậy nhân với 3 là một phép toán mà thực hiện không đơn giản trên phần cứng và thường phải dùng tới bộ cộng. Tuy vậy khối nhân vẫn có thể tăng tốc theo sơ đồ này bằng cách tính trước số bị nhân với 3. Nhằm tránh việc nhân với 3, sơ đồ nhân theo cơ số 4 trên được cải tiến bằng mã hóa Booth theo cơ số 4 (radix-4 Booth encoding), mã hóa này giúp việc
tính các tích riêng trở nên dễ dàng hơn, cụ thể công thức biểu diễn giá trị của số bù 2 có thể biến đổi về dạng sau: n-1 n-2 xn-1xn-2 x1x0 = -2 xn-1 +2 xn-2 + + 2x1 + x0 n-2 n-2 n-2 n-4 n-4 n-4 = -2 2.xn-1 + 2 xn-2 +2 xn-3 - 2 2.xn-3 + 2 xn-4 +2 xn-5 + - 2.2. x1 + 2 x0 + 2. 0 n-2 n-4 = 2 (- 2xn-1 + xn-2 + xn-3) +2 (-2xn-3 + xn-4 + xn-5)+ + (-2x1 + x0 + 0) Như vậy nếu ta xây dựng bảng mã hóa theo công thức bi = (- 2xi+1 + xi + xi-1) với i = 0, 2, 4, n-2 ta sẽ mã hóa n bit của số nhân bằng [n/2] giá trị theo bảng mã sau: xi+1 xi xi Radix-4 Booth encoding 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 2 1 0 0 -2 1 0 1 -1 1 1 0 -1 1 1 1 0 Ví dụ đầy đủ về phép nhân có dấu sử dụng mã hóa Booth cơ số 2 như sau: Thuật toán cộng dịch phải cho số có dấu dùng Radix-4 booth encoding a 1 1 0 1 0 1 Bù 2 a = 0 0 1 0 1 1(a = -11) x 0 1 1 0 1 0 (0) x = + 26 b 2 -1 -2 Radix 4 booth encoding of x P(0) 0 0 0 0 0 0 0 +b0.a 0 0 1 0 1 1 0 2p(1) (0)0 0 1 0 1 1 0 P(1) 0 0 0 1 0 1 1 0 +b1.a 0 0 1 0 1 1
2p(2) (0)0 1 0 0 0 0 1 0 P(2) 0 0 0 1 0 0 0 0 1 0 +x2.a 1 1 0 1 0 1 0 2p(2) (1)1 1 0 1 1 1 0 0 0 1 0 P 1 1 1 0 1 1 1 0 0 0 1 0 = -286 Sơ đồ hiện thực trên phần cứng của thuật toán nhân dùng mã hóa Booth cơ số 4 giống hệt sơ đồ của phép nhân số có dấu dùng mã hóa Booth cơ số 2, điểm khác biệt là thay khối mã hóa Booth cơ số 2 bằng cơ số 4. SHIFTER _ SIGNED 2s’ complement EXTEND Multiplicand product RADIX 4 K bit Multiplier BOOTH ENCODING 0 SHIFT_REG MUX Kbit Σ k-bit Hình 2.23: Sơ đồ hiện thực hóa thuật toán nhân dùng mã hóa Booth cơ số 4 Bằng cách tương tự có thể xây dựng sơ đồ nhân với mã hóa Booth cho các cơ số cao hơn. 8. Khối chia số nguyên Khối chia là một khối số học khá phức tạp nếu so sánh với khối cộng hay khối nhân, trên thực tế các vi điều khiển và vi xử l{ trước đây thường không hỗ trợ phép chia ở cấp độ phần cứng mà được thực hiện bằng phần mềm. Ở các vi xử lý hiện đại thì phép chia được hỗ trợ hoàn toàn, tuy vậy nếu so sánh về tốc độ thực hiện thì phép chia vẫn chậm hơn nhiều so với các phép toán khác, ngay cả
đối với các phép toán trên số thực. Ví dụ phép nhân với số nguyên 32 bit dùng 4 xung nhịp Clk, còn phép chia dùng tới 35 xung nhịp. Dưới đây ta sẽ nghiên cứu các thuật toán cơ bản để thực hiện phép chia trên phần cứng, đây chưa phải là những thuật toán nhanh nhất của phép chia nhưng là là những thuật toán cơ sở để người đọc nghiên cứu các thuật toán khác. Ký hiệu z : số bị chia (dividend) d: số chia (divisor) q: thương số (quotient) s: số dư (remainder) Sơ đồ thực hiện của phép chia số nhị phân tương tự như sơ đồ thực hiện phép chia đối với số thập phân. Ví dụ dưới đây minh họa một phép chia số 8 bit cho số 4 bit không có dấu. z 1 1 0 0 0 1 0 1 z = 197 2^4d 1 1 1 0 d = 14 s(0) 1 1 0 1 0 1 0 1 2s(0) 1 1 0 0 0 1 0 1 -q3.2^4d 1 1 1 0 q3 = 1 s(1) 1 0 1 0 1 0 1 2s(1) 1 0 1 0 1 0 1 -q2.2^4d 1 1 1 0 q2 = 1 s(2) 0 1 1 1 0 1 2s(2) 0 1 1 1 0 1 -q1.2^4d 1 1 1 0 q1 = 1 s(3) 0 0 0 0 1 2s(3) 0 0 0 0 1 -q.0^4d 0 0 0 0 q0 = 0 s = 0 0 0 1 = 1 q = 1 1 1 0 = 14
Phép chia được thực hiện bằng cách dịch số bị chia sang bên phải 4 bit để vị trí bit có trọng số cao nhất trùng với số bị chia. Tiếp đó khởi tạo số dư bằng số bị chia, nếu số này lớn hơn 24.d thì bit thứ 4 tương ứng của thương số bằng q3 = 1, Trong trường hợp ngược lại q3 = 0. Thực hiện phép trừ số dư hiện tai cho q3.24.d. Kết quả phép trừ được dịch sang phải 1 bit để thu được số dư trung gian mới và lặp lại quá trình trên. Cho tới bước thứ 4, số dư ở bước cuối cùng thu được là số dư cần tìm. Thương số được ghép bởi các bit từ cao đến thấp từ bước 1 đến 4. 8.1. Khối chia dùng sơ đồ khôi phục phần dư Khối chia trên phần cứng được xây dựng trên cơ sở nguyên l{ như trên, điểm khác biệt là phép trừ được thay tương đương bằng phép cộng với số bù hai, và cần thực hiện phép trừ trước để xác định giá trị của q3, q2, q1, q0. Sơ đồ sau được gọi là sơ đồ chia có khối phục phần dư vì sau mỗi phép trừ nếu kết quả là âm thì phần dư sẽ được khôi phục lại thành giá trị cũ và dịch thêm một bit trước khi thực hiện trừ tiếp. Ví dụ một phép chia thực hiện theo sơ đồ đó như sau: z 1 1 0 0 0 1 0 1 z = 197 2^4d 1 1 1 0 d = 14 s(0) 0 1 1 0 1 0 1 0 1 2s(0) (0)1 1 0 0 0 1 0 1 +(-2^4d) 1 0 0 1 0 s(1) (0)0 1 0 1 0 1 0 1 kết quả dương q3 = 1 2s(1) 1 0 1 0 1 0 1 +(-2^4d) 1 0 0 1 0 s(2) (0)0 0 1 1 1 0 1 kết quả dương q2 = 1 2s(2) 0 1 1 1 0 1 +(-2^4d) 1 0 0 1 0 s(3) (0)0 0 0 0 0 1 kết quả dương q1 = 1 2s(3) 0 0 0 0 1 +(-2^4d) 1 0 0 1 0
S(4) = 1 0 0 1 1 = 1 kết quả âm q0 = 0 S(4) = 0 0 0 1 trả về giá trị dư cũ s = 2s(4) = 0 0 0 1 = 1 q = 1 1 1 0 = 14 Sơ đồ phần chi tiết phần cứng được thiết kế như sau: Load MUX Quotient (SHIFT LEFT) Remainder (SHIFT LEFT) divisor 2s’ complement SUB Cout Σ k-bit Hình 2.24 Sơ đồ khối chia có khôi phục phần dư Gọi k là số bit của số chia và thương số. Thanh ghi dịch Remainder 2k+1-bit trong sơ đồ trên được sử dụng để lưu trữ giá trị dư trung gian. Thanh ghi này được khởi tạo giá trị bằng giá trị của số bị chia và mỗi xung nhịp được dịch sang bên trái một bit. Bit nhớ đặc biệt thứ 2k+1 luôn lưu trữ bít có trọng số cao nhất của phần dư. Thanh ghi dịch Quotient k-bit được sử dụng lưu trữ giá trị thương số, thanh ghi này cũng được dịch sang phải mỗi lần một bit. Bộ cộng k-bit được sử dụng để thực hiện phép trừ 5 bit bằng cách cộng phần 5 bit cao của thanh ghi remainder với bù hai của số chia. Trên thực tế để biểu diễn số có dấu 5 bit cần 6 bit nhưng lợi dụng tính chất của số dư trong phép chia không dấu là không âm nên bit dấu luôn bằng 0 ta giảm bớt 1 bit của bộ cộng tuy vậy để xác định giá trị thương số qi cần xét hai giá trị là bit có trọng số cao
nhất của phần dư, nếu giá trị này bằng 1 thì dĩ nhiên phần dư lớn hơn số chia, còn bit số này bằng 0, nhưng phép trừ đưa ra bit nhớ Cout = 1, tương ứng kết quả là số dương thì phần dư cũng lớn hơn hoặc bằng số chia. Trong cả hai trường hợp này qi =1, trong các trường hợp khác qi =0, đó là l{ do tại sao trước thanh ghi quotient đặt một cổng logic OR hai đầu vào. 8.2. Khối chia dùng sơ đồ không khôi phục phần dư Khi phân tích về sơ đồ thuật toán chia có phục hồi số dư, có một nhận xét là không nhất thiết phải thực hiện thao tác phục hồi giá trị phần dư, và trên cơ sở đó có thể xây dựng sơ đồ khối chia không khôi phục hồi phần dư. Về mặt toán học, giả sử giá trị tại thanh ghi chứa phần dư là u, ở bước tiếp theo ta sẽ thực hiện u – 24d, phép trừ này cho ra kết quả âm, tức là kết quả không mong muốn, nếu như với sơ đồ khôi phục phần dư ở bước tiếp theo ta sẽ trả lại giá trị u, dịch sang phải 1 bit và thực hiện phép trừ 2.u -24d. Tuy vậy nếu lưu { rằng 2.u – 24d = 2(u-24d) + 24d. Ta có thể thay đổi sơ đồ đi một chút mà chức năng của mạch vẫn không thay đổi, ở bước trên ta vẫn lưu giá trị sai vào thanh ghi, ở bước sau ta sẽ vẫn dịch giá trị trong thanh ghi sang phải 1 bit nhưng thay vì cộng với số bù 2 của 24d ta sẽ cộng trực tiếp với 24d, việc đó đảm bảo kết quả của bước tiếp theo vẫn đúng. Quy luật chung là: Nếu giá trị trong thanh ghi là âm -> thực hiện cộng với 24d. Nếu giá trị trong thanh ghi là âm -> thực hiện trừ với 24d. Khối chia sử dụng sơ đồ khôi phục phần dư dễ hiểu, tuy vậy nếu nghiên cứu kỹ về độ trễ logic ta sẽ thấy tín đường dữ liệu dài nhất (trong 1 xung nhịp đồng bộ) phải trải qua ba thao tác: thao tác dịch ở thanh ghi, thao tác cộng ở bộ cộng, và thao tác lưu giá trị vào thanh ghi Quotient và thanh ghi Remainder. Thao tác cuối được thực hiện sau khi bit nhớ Cout của chuỗi cộng xác định. Nếu chấp nhận luôn lưu trữ giá trị kết quả phép trừ vào thanh ghi, không quan tâm dù đó là giá trị đúng hay sai, bỏ qua thao tác phục hồi giá trị phần dư thì đồng thời sẽ bỏ sự lệ thuộc vào Cout và tốc độ của bộ chia có thể được cải thiện thêm một lớp trễ. Về mặt tài nguyên thì không có sự thay đổi nhiều vì thay cho
thao tác phục hồi mà thực chất là khối chọn kênh 5 bit thì phải thực hiện chọn hạng tử cho khối cộng giữa d và bù 2 của d cũng là một khối chọn kênh 5 bit. Ví dụ một phép chia theo sơ đồ không phục hồi phần dư như sau: z 1 0 0 0 0 1 0 1 z = 133 2^4d 1 1 1 0 d = 14 s(0) 0 1 0 0 1 0 1 0 1 2s(0) (0)1 0 0 0 0 1 0 1 +(-2^4d) 1 0 0 1 0 s(1) (1)0 0 0 1 0 1 0 1 kết quả dương q3 = 1 2s(1) 0 0 1 0 1 0 1 +(-2^4d) 1 0 0 1 0 s(2) (0)1 0 1 1 1 0 1 kết quả âm q2 = 0 2s(2) (1)0 1 1 1 0 1 +(+2^4d) 0 1 1 1 0 s(3) (0)1 1 1 0 0 1 kết quả âm q1 = 0 2s(3) 1 1 0 0 1 +(+2^4d) 0 1 1 1 0 S(4) = 0 0 1 1 1 kết quả dương q0 = 1 s = 2s(4) = 0 0 1 1 = 7 q = 1 0 0 1 = 9 Sơ đồ phần chi tiết phần cứng được thiết kế như sau: Remainder (SHIFT LEFT) divisor 2s’ complement Quotient (SHIFT LEFT) SUB MUX (K+1) bit Σ k-bit
Hình 2.25 Sơ đồ khối chia không phục phần dư Sơ đồ về cơ bản giống như sơ đồ khối chia thực hiện bằng thuật toán không phục hồi phần dư, điểm khác biệt duy nhất là multiplexer được chuyển xuống vị trí trước bộ cộng để chọn giá trị tương ứng cho khối này, việc chọn giá trị cộng cũng như thực hiện phép toán cộng hay trừ trong bộ cộng được quyết định bởi bit dấu của phần dư được lưu trong ô nhớ có trọng số cao nhất (2k+1) của thanh ghi Remainder. 8.3. Khối chia số nguyên có dấu Hai sơ đồ trên chỉ đúng cho phép chia đối với số không dấu, để thực hiện phép chia đối với số có dấu cũng giống như trường hợp của khối nhân, phép chia được thực hiện bằng cách chuyển toàn bộ số chia và số bị chia thành hai phần giá trị tuyệt đối và dấu, phần giá trị tuyệt đối có thể tiến hành chia theo một trong hai sơ đồ trên, phần dấu được tính toán đơn giản bằng một cổng XOR, kết quả thu được lại chuyển ngược lại thành biểu diễn dưới dạng số bù 2. Dưới đây ta sẽ tìm hiểu một thuật toán khác nhanh hơn và tiết kiệm hơn để thực hiện phép chia có dấu. Ý tưởng của thuật toán này xuất phát từ sơ đồ chia không phục hồi phần dư. Mục đích của phép chia là đi tìm biểu diễn sau k-1 k-2 z = qk-1 . 2 .d + qk-2 .2 .d + +q0.d + s. trong đó z là số bị chia, d là số chia, s là phần dư còn thương số chính là giá trị nhị phân của qk-1qk-2 q0. Qi nhận giá trị 0 hay 1 tương ứng ở bước thứ i phần dư được cộng thêm hoặc trừ đi tương ứng giá trị d tương ứng với giá trị phần dư là dương hay âm. Một cách tổng quát cho phép chia: mục đích của các sơ đồ trên là làm giảm dần trị tuyệt đối của phần dư bằng cách trừ nếu nó cùng dấu với số chia và cộng nếu nó khác dấu với số chia, quá trình này kết thúc khi hai điều kiện sau được thỏa mãn: 1. Phần dư s cùng dấu với z
2. Trị tuyệt đối của s nhỏ hơn trị tuyệt đối của q. Cũng tổng quát hóa từ sơ đồ chia không phục hồi phần dư, nếu ta mã hóa qi khác đi như sau: qi = 1 nếu s(i) và d cùng dấu qi = -1 nếu s(i) và d khác dấu. k-1 k-2 Khi đó đẳng thức biểu diễn ở trên z = qk-1 . 2 .d + qk-2 .2 .d + +q0.d + s, vẫn đúng, chỉ khác ở tập giá trị của qi là {-1, 1}. Có thể chứng minh rằng nếu ta làm lần lượt các bước sau thì có thể đưa q = qk-1qk-2 q0 về dạng biểu diễn nhị phân p = pkpk-1 p0 với pi = {0,1} và giá trị p = q. - Chuyển tất cả các giá trị -1 thành 0. Gọi giá trị này là r = rk-1rk-2 r0. Có thể dễ dàng chứng minh qi = 2ri – 1. - Lấy đảo của rk-1, thêm 1 vào cuối r và lấy bù hai của giá trị thu được ta sẽ thu được p = ( k-1rk-2 r01)2’s complement Có thể chứng minh như sau: p = ( k-1rk-2 r01)2’s complement k = - (1-pk-1). 2 + 1 + k = -(2 -1) +2. = = q Ví dụ một phép chia hai số có dấu như sau: z 1 1 0 1 0 1 0 1 z = -43 2^4d 0 1 1 0 d = 6 s(0) 1 1 0 1 0 1 0 1 2s(0) 1 1 0 1 0 1 0 1 d,s khác dấu q3 = -1 +(2^4d) 0 0 1 1 0 thực hiện cộng s(1) 0 0 0 0 0 1 0 1 d,s cùng dấu q2 = 1 2s(1) 0 0 0 0 1 0 1 thực hiện trừ
+(-2^4d) 1 1 0 1 1 s(2) 1 1 1 0 0 0 1 d,s khác dấu q1 = -1 2s(2) 1 1 0 0 0 1 thực hiện cộng +(+2^4d) 0 0 1 1 0 s(3) 1 1 1 1 0 1 d,s khác dấu q0 = -1 2s(3) 1 1 1 0 1 +(+2^4d) 0 0 1 1 0 S(4) = 0 0 0 1 1 s, q cùng dấu sửa lại số dư +(-2^4d) 1 1 0 0 1 S = 1 1 1 1 1 = - 1 p = -1 1 -1 -1 r = 0 1 0 0 q = (1 1 0 0 1)2’s complement = -7 Sơ đồ phần chi tiết phần cứng được thiết kế như sau: Remainder (SHIFT LEFT) divisor 2s’ complement R (SHIFRT_LEFT) SUB MUX (K+1) bit Quotient Σ k+1-bit Hình 2.25 Sơ đồ khối chia có dấu Sơ đồ trên được phát triển từ sơ đồ chia không phục hồi phần dư, điểm khác biệt là tín hiệu lựa chọn việc thực hiện phép cộng hay phép trừ tương ứng được thực hiện bằng một cổng XNOR với hai đầu vào là giá trị dấu của phần dư hiện tại và dấu của số chia, nếu hai giá trị này khác nhau thì giá trị pi tương ứng bằng -1, trên thực tế ta không biểu diễn giá trị -1 mà quy ước biểu diễn là số 0, nếu dấu hai số như nhau thì giá trị pi bằng 1. Các giá trị này được đẩy dần vào
thanh ghi R, giá trị r = rk-1rk-2 r0 thu được sau k xung nhipk chưa phải là giá trị thương cần tìm, để tìm đúng giá trị thương ta phải có một khối thực hiện việc chuyển đổi r về giá trị q theo quy tắc trình bày ở trên. 9. Bộ nhớ 9.1. Bộ nhớ RAM RAM (Random Access Memory) là một phần tử rất hay được sử dụng trong thiết kế các hệ thống số. RAM có thể phân loại theo số lượng cổng và cách thức làm việc đồng bộ hay không đồng bộ của các thao tác đọc và ghi. CLKA WEA CLK CSA WE OEA CS DATA_INA OE ADDRESSA ADDR_decoder t t i i b b - ADDRESS DATA_OUTA - N ADDR_decoder N x x M DATA_IN CLKB M WEB DATA_OUT CSB OEB DATA_INB ADDRESSB DATA_OUTB Single-port RAM Dual-port RAM Hình 2.26 Sơ đồ khối Single-port RAM và Dual-port RAM - Single port RAM là RAM chỉ có một kênh đọc và ghi, một đường vào địa chỉ, các động tác đọc ghi trên kênh này chỉ có thể thực hiện lần lượt. - Dual-port RAM là RAM có hai kênh đọc ghi riêng biệt tương ứng hai kênh địa chỉ, các kênh đọc ghi này có thể dùng chung xung nhịp đồng bộ cũng có thể không dùng chung. Đối với Dual-port RAM có thể đọc và ghi đồng thời trên hai kênh.
- Synchronous RAM - RAM đồng bộ là RAM thực hiện thao tác đọc hoặc ghi đồng bộ. - Asynchronous RAM- RAM không đồng bộ là RAM thực hiện thao tác đọc hoặc ghi không đồng bộ, thời gian kể từ khi có có các tín hiệu yêu cầu đọc ghi cho tới khi thao tác thực hiện xong thuần túy là trễ tổ hợp. Kết hợp cả hai đặc điểm trên có thể có thể tạo thành nhiều kiểu RAM khác nhau, ví dụ single-port RAM synchronous READ synchronous WRITE nghĩa là RAM 1 cổng đọc ghi đồng bộ, hay Dual-port RAM synchronous WRITE asynchronous READ là RAM hai cổng ghi đồng bộ đọc không đồng bộ Khối RAM được cấu thành từ hai bộ phận là khối giải mã địa chỉ và dãy các thanh ghi, khối giải mã địa chỉ sẽ đọc địa chỉ và quyết định sẽ truy cập tới vị trí thanh ghi nào để thực hiện thao tác đọc hoặc ghi. Kích thước của khối RAM thường được ký hiệu là Mx N-bit trong đó M là số lượng thanh ghi, N là số bit trên 1 thanh ghi. Ví dụ 128 x 8 bit là khối RAM gồm 128 thanh ghi, mỗi thanh ghi 8 bit. Số bit cần thiết cho kênh địa chỉ là ADDR_WIDTH = [log2 M], nếu M = 128 nên số ADDR_WIDTH = 7. Mô tả VHDL một khối single-port RAM synchronous READ/WRITE ở dưới đây: simple RAM unit library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_unsigned.all; entity simple_ram is generic ( DATA_WIDTH :integer := 8; ADDR_WIDTH :integer := 4 ); port( clk :in std_logic; address :in std_logic_vector (ADDR_WIDTH-1 downto 0); data_in :in std_logic_vector (DATA_WIDTH-1 downto 0); data_out :out std_logic_vector (DATA_WIDTH-1 downto 0); cs :in std_logic; Chip Select we :in std_logic; we = 1 write, we = 0 read oe :in std_logic OutputEnable when reading ); end entity;
architecture rtl of simple_ram is constant RAM_DEPTH :integer := 2 ADDR_WIDTH; type RAM is array (integer range <>)of std_logic_vector (DATA_WIDTH-1 downto 0); signal mem : RAM (0 to RAM_DEPTH-1); begin WRITTING: process (clk) begin if (rising_edge(clk)) then if (cs = '1' and we = '1') then mem(conv_integer(address)) <= data_in; end if; end if; end process; READING: process (clk) begin if (rising_edge(clk)) then if (cs = '1' and we = '0' and oe = '1') then data_out <= mem(conv_integer(address)); end if; end if; end process; end architecture; Các tín hiệu điều khiển thao tác đối với RAM bao gồm CS – chip select, với mọi thao tác thì đều yêu cầu CS phải ở mức cao. WE – write enable bằng 1 nếu cần ghi dữ liệu vào RAM. Tín hiệu OE – output enable bằng 1 nếu là đọc dữ liệu từ RAM, với thiết kế như vậy thì WE và OE không bao giờ đồng thời bằng 1. Hình dưới đây mô phỏng làm việc của một khối RAM.
Hình 2.27: Kết quả mô phỏng khối RAM Khi tín hiệu CS, WE ở mức tích cực cao, thực hiện động tác ghi vào RAM, mỗi xung nhịp ta ghi một giá trị bất kz, sau đó giá trị địa chỉ được tăng lên 1 đơn vị để thực hiện ghi vào ô nhớ kế tiếp. Cứ như thế khối RAM ta sẽ thực hiện ghi 8 giá trị 174, 178. 182 202 vào các thanh ghi có địa chỉ tương ứng là 1,2, 8. Sau đó thực hiện động tác đọc giá trị từ RAM, tín hiệu CS giứ ở mức cao, WE bây giờ có mức thấp còn OE được đẩy lên mức cao, lần lượt thực hiện đọc giá trị từ thanh ghi thứ 7 đến thanh ghi thứ 1, mỗi lần đọc ta giảm giá trị địa chỉ đi 1 đơn vị. 9.2. Bộ nhớ ROM ROM (Read-only Memory) là cấu trúc nhớ chỉ đọc trong đó các giá trị ô nhớ được lưu cố định khi khởi tạo ROM và không thay đổi trong quá trình sử dụng, thậm chí khi không có nguồn cấp giá trị trong ROM vẫn được giữ nguyên.
CS DATA_OUT RE t i b ADDR_decoder - ADDRESS N x M DATA ROM Hình 2.28: Sơ đồ khối ROM Cấu trúc của ROM về cơ bản giống như của RAM, có một khối chứa dữ liệu cố định, không nhất thiết phải sử dụng xung nhịp CLK, khối giải mã địa chỉ. Các tín hiệu đầu vào là địa chỉ ADDRESS, tín hiệu CS – chip select, tín hiệu cho phép đọc RE – read enable. Đầu ra của khối ROM là giá trị DATA Mô tả VHDL của khối ROM khá đơn giản nếu so sánh với khối RAM, thông thường khối ROM được mô tả dưới dạng một khối tổ hợp, code dưới đây mô tả một khối ROM 16x8-bit Simple ROM unit library ieee; use ieee.std_logic_1164.all; entity simple_rom is port ( cs :in std_logic; re :in std_logic; address :in std_logic_vector (3 downto 0); data :out std_logic_vector (7 downto 0) ); end entity; architecture behavioral of simple_rom is Du lieu trong ROM duoc nap cac gia tri co dinh begin
process (re, cs, address) begin if re = '1' and cs = '1' then case (address) is when x"0" => data data data data data data data data data data data data data data data data data <= x"0f"; end case; end if; end process; end architecture; Mô phỏng thao tác đọc dữ liệu như ở giản đồ sóng dưới đây: Hình 2.29: Kết quả mô phỏng khối ROM Ở ví dụ trên khối ROM được đọc lần lượt các ô nhớ từ thứ 1 đến thứ 11, để thực hiện thao tác đọc thì tín hiệu CS và RE phải đồng thời để ở mức cao. 9.3. Bộ nhớ FIFO FIFO (First-In-First-Out) là một khối nhớ đặc biệt, rất hay ứng dụng trong các hệ thống truyền dẫn số, dùng làm các khối đệm trong các thiết bị lưu trữ Đặc điểm duy nhất cũng là yêu cầu khi thiết kế khối này là dữ liệu nào vào trước thì khi đọc sẽ ra trước. Đối với FIFO không còn khái niệm địa chỉ mà chỉ còn các
cổng điểu khiển đọc và ghi dữ liệu. Tùy theo yêu cầu cụ thể mà FIFO có thể được thiết kế bằng các cách khác nhau. Sơ đồ đơn giản và tổng quát nhất của FIFO là sơ đồ sử dụng khối RAM đồng bộ hai cổng đọc ghi độc lập. CLK CLKA WRITE WEA CSA DATA_IN OEA WRITE_CS WRITE_FIFO DATA_INA ADDRESSA ADDR_decoder t i b CLKB DATA_OUTA - N x M WEB READ CSB READ_CS OEB READ_FIFO DATA_INB ADDRESSB DATA_OUT DATA_OUTB Dual-port RAM FIFO_STATE FIFO_EMPTY FIFO_FULL Hình 2.30 Sơ đồ khối FIFO sử dụng Dual-port RAM Để FIFO làm việc đúng như yêu cầu cần thêm 3 khối điều khiển sau: - Khối xác định trạng thái FIFO (FIFO_STATE) tạo ra hai tín hiệu FIFO_FULL, và FIFO_EMPTY để thông báo về tình trạng dầy hoặc rỗng tương ứng của bộ nhớ. Để tạo ra các tín hiệu này sử dụng một bộ đếm, ban đầu bộ đếm được khởi tạo bằng 0. Bộ đếm này thay đổi như sau: - Nếu có thao tác đọc mà không ghi thì giá trị bộ đếm giảm xuống 1.
- Nếu có thao tác ghi mà không đọc thì giá trị bộ đếm tăng lên 1. - Nếu có thao tác đọc và ghi thì giá trị bộ đếm không thay đổi. Bằng cách đó - FIFO_EMPTY = 1 nếu giá trị bộ đếm bằng 0 - FIFO_FULL = 1 nếu giá trị bộ đếm bằng giá trị tổng số ô nhớ của RAM là 2addr_width – 1 - Khối điều khiển ghi vào FIFO (WRITE_FIFO) thực hiện tiền xử lý cho thao tác ghi dữ liệu trên một kênh cố định trong khối RAM. Địa chỉ của kênh này được khởi tạo bằng 0 và được tăng thêm 1 sau mỗi lần ghi dữ liệu. Khi giá trị địa chỉ đạt tới giá trị cao nhất bằng 2addr_width – 1 thì được trả lại bằng 0. Thao tác ghi dữ liệu được thực hiện chỉ khi FIFO chưa đầy (FIFO_FULL = 0) - Khối điều khiển đọc vào FIFO (READ_FIFO) thực hiện tiền xử l{ cho thao tác đọc dữ liệu theo kênh còn lại của khối RAM. Địa chỉ của kênh này được khởi tạo bằng 0 và được tăng thêm 1 sau mỗi lần đọc dữ liệu. Khi giá trị địa chỉ đạt tới giá trị cao nhất bằng 2addr_width – 1 thì được trả lại bằng 0. Thao tác đọc dữ liệu được thực hiện chỉ khi FIFO chưa đầy (FIFO_EMPTY = 0). 9.4. Bộ nhớ LIFO LIFO (Last-In-First-Out) hay còn được gọi là STACK cũng là một khối nhớ tưong tự như FIFO nhưng yêu cầu là dữ liệu nào vào sau cùng thì khi đọc sẽ ra trước. LIFO cũng có thể được thiết kế sử dụng khối RAM đồng bộ hai cổng đọc ghi độc lập. Điều khiển của LIFO khá đơn giản vì nếu có N ô nhớ được lưu trong LIFO thì các ô này sẽ lần lượt được lưu ở các ô từ 0 đến N-1, do đó khi thiết kế ta chỉ cần một bộ đếm duy nhất trỏ tới vị trí giá trị N. - Nếu có thao tác ghi dữ liệu mà không đọc thì dữ liệu được lưu vào ô có địa chỉ N và N tăng thêm 1. - Nếu có thao tác đọc dữ liệu mà không ghi thì dữ liệu được đọc ở ô có địa chỉ N-11 và N giảm đi 1. - Nếu có thao tác đọc, ghi dữ liệu đồng thời thì N không thay đổi và dữ liệu đọc chính là dữ liệu ghi.
Trạng thái của LIFO cũng được xác định thông qua giá trị của N, nếu N=0 thì LIFO_EMPTY = 1 và nếu N = 2addr_width – 1 thì LIFO_FULL = 1. 10. Máy trạng thái hữu hạn FSM (Finish-state machine) máy trạng thái hữu hạn là mạch có hữu hạn các trạng thái và hoạt động của mạch là sự chuyển đổi có điều kiện giữa các trạng thái đó. FSM rất hay được sử dụng trong các bài toán số phức tạp, để thực hiện mô tả này đầu tiên người thiết kế phải phân tích thống kê các trạng thái cần có thể của mạch, tối giản và tìm điều kiện chuyển đổi giữa các trạng thái, vẽ giản đồ chuyển trạng thái có dạng như sau. IDLE CNT = 8 and RX = 1 CNT_BIT = 8 RX = 0 START FRAME RECEIVE DETECT DATA CNT = 8 and RX = 0 Hình 2.31: Sơ đồ trạng thái bộ thu UART đơn giản Sơ đồ thể hiện cách chuyển trạng thái của một khối nhận dữ liệu từ đường truyền UART một cách đơn giản nhất.
Hình 2.32: Tín hiệu vào Rx của khối thu UART Ví dụ dữ liệu đầu vào của một đường truyền UART như hình vẽ, khi ở trạng thái không truyền dữ liệu thì khối tín hiệu RX ở mức cao và khối nhận nằm ở trạng thái chờ IDLE. Khi RX chuyển từ mức cao xuống mức thấp thì khối nhận chuyển sang trạng thái thứ hai gọi là trạng thái dò tín hiệu start, START_FRAME_DETEC. Bít START được xem là hợp lệ nếu như mức 0 của RX được giữ trong một khoảng thời gian đủ lâu xác định, khối nhận sẽ dùng một bộ đếm để xác nhận sự kiện này, nếu bộ đếm đếm CNT đến 8 mà RX bằng 0 thì sẽ chuyển sang trạng thái tiếp theo là trạng thái nhận dữ liệu RECEIVE DATA. Nếu CNT = 8 mà RX = 1 thì đây không phải bit START, khối nhận sẽ quay về trạng thái chờ IDLE. Ở trạng thái nhận dữ liệu thì khối này nhận liên tiếp một số lượng bit nhất định, thường là 8 bit, khi đó CNT_BIT = 8, sau đó sẽ trở về trạng thái chờ. IDLE. Mô tả VHDL của khối FSM trên như sau: Simply UART FSM library IEEE; use IEEE.STD_LOGIC_1164.ALL; entity fsm_receiver is generic (n: positive := 8); port( cnt_bit : in std_logic_vector (3 downto 0); cnt8 : in std_logic_vector (2 downto 0); Rx : in std_logic; CLK : in std_logic; reset : in std_logic; receiver_state : inout std_logic_vector (1 downto 0) ); end fsm_receiver; architecture behavioral of fsm_receiver is
constant Idle : std_logic_vector (1 downto 0) := "00"; constant start_frame_detect : std_logic_vector (1 downto 0) := "01"; constant receive_data :std_logic_vector (1 downto 0) := "11"; begin receiving: process (CLK, RESET) begin if RESET = '1' then receiver_state if Rx = '0' then receiver_state if cnt8 = "111" then if Rx = '0' then receiver_state if cnt_bit = "0111" then receiver_state receiver_state <= Idle; end case; end if; end process receiving; end behavioral; Với mô tả như trên trạng thái của mạch được lưu bằng hai bít của thanh ghi receiver_state, trạng thái của mạch sẽ thay đổi đồng bộ với xung nhịp hệ thống CLK. (*) Code trên dùng để minh họa cách viết FSM, trên thực tế khối điều khiển trạng thái bộ nhận UART phức tạp hơn do còn phần điều khiển trạng thái các bộ đếm, thanh ghi
Bài tập chương III Bài tập 1. Thiết kế và kiểm tra bộ cộng 32 bit nối tiếp dùng thanh ghi dịch và một FULL_ADDER. 2. Thiết kế và kiểm tra bộ cộng 32 bit dùng thuật toán Carry look ahead adder, so sánh với các thuật toán khác. 3. Thiết kế và kiểm tra khối nhân không dấu 4x4 = 8bit dùng thuật toán cộng dịch trái. 4. Thiết kế và kiểm tra khối nhân không dấu 4x4 = 8bit dùng thuật toán cộng dịch phải. 5. Thiết kế và kiểm tra khối nhân có dấu 4x4 = 8bit dùng mã hóa Booth cơ số 2. 6. Thiết kế và kiểm tra khối nhân có dấu 4x4 = 8bit dùng thuật toán mã hóa Booth cơ số 4. 7. Thiết kế và kiểm tra khối chia 8 bit / 4bit = 4 bit dùng thuật toán phục hồi phần dư. 8. Thiết kế và kiểm tra khối chia 8 bit / 4bit = 4 bit dùng thuật toán không phục hồi phần dư. 9. Thiết kế và mô phỏng khối FIFO 16x16bit. 10. Thiết kế và mô phỏng khối RAM 32x8bit. một cổng đọc ghi đồng bộ. 11. Thiết kế và mô phỏng khối RAM 16x16bit. một cổng đọc không đồng bộ, ghi đồng bộ. 12. Thiết kế và mô phỏng khối RAM 16x16bit. hai cổng đọc ghi đồng bộ. 13. Thiết kế và mô phỏng khối RAM 16x16bit. hai cổng cổng đọc không đồng bộ, ghi đồng bộ. 14. Thiết kế và mô phỏng khối LIFO 16x16bit. 15. Thiết kế và mô phỏng khối ROM 64x8 bit lưu trữ giá trị rời rạc hóa của một chu kz hình SIN. 16. Thiết kế khối ROM đồng bộ 64x8 bit lưu trữ giá trị rời rạc hóa của một chu kz hình COSIN. 17. Thiết kế khối ROM đồng bộ 64x8 bit lưu trữ giá trị rời rạc hóa của một chu kz hình sóng tam giác /\/
18. Thiết kế và kiểm tra bộ cộng hỗ trợ thao tác trừ 32 bit, khối cộng sử dụng cấu trúc Generate. 19. Thiết kế và kiểm tra thanh ghi dịch hỗ trợ thao tác ghi dữ liệu song song điều khiển bởi tín hiệu LOAD và các lệnh dịch logic và arithmetich trái không sử dụng toán tử dịch, giá trị dịch là một số 5 bit, dữ liệu dịch là chuỗi 32 bit. Tín hiệu điều khiển LOG = 1 nếu như phép dịch logic, LOG = 0 nếu dịch số học. 20. Thiết kế và kiểm tra thanh ghi dịch hỗ trợ thao tác ghi dữ liệu song song điều khiển bởi tín hiệu LOAD và các lệnh dịch logic và arithmetich phải không sử dụng toán tử dịch, giá trị dịch là một số 5 bit, dữ liệu dịch là chuỗi 32 bit. Tín hiệu điều khiển LOG = 1 nếu như phép dịch logic, LOG = 0 nếu dịch số học. 21. Thiết kế và kiểm tra thanh ghi dịch hỗ trợ thao tác ghi dữ liệu song song điều khiển bởi tín hiệu LOAD và phép dịch vòng trái, phải không sử dụng toán tử dịch, giá trị dịch là một số 5 bit, dữ liệu dịch là chuỗi 32 bit. Tín hiệu điều khiển LEFT = 1 nếu dịch trái và LEFT = 0 nếu dịch phải. 22. Thiết kế và kiểm tra bộ so sánh hai số 8 bit có dấu và không dấu. 23. Thiết kế và kiểm tra bộ cộng tích lũy 32 bit. 24. Thiết kế bộ đếm thập phân đồng bộ, hỗ trợ RESET không đồng bộ và hỗ trợ tín hiệu Enable. 25. Sử dụng bộ đếm thiết kế bộ chia tần từ tần số 1,5MhzHz thành 1Hz, tần số xung nhịp thu được có dạng đối xứng. Câu hỏi ôn tập lý thuyết 1. Trình bày thuật toán cộng Carry look ahead adder, so sánh với thuật toán cộng nối tiếp. 2. Trình bày thuật toán cộng dùng 1 full_adder, ưu nhược điểm của thuật toán này. 3. Trình bày cấu trúc thanh ghi dịch, thuật toán dịch không dùng toán tử dịch, ví dụ ứng dụng thanh ghi dịch. 4. Trình bày cấu trúc bộ đếm.
5. Trình bày thuật toán và cấu trúc khối nhân số không dấu thông thường dùng mạch tổ hợp. 6. Trình bày thuật toán và cấu trúc khối nhân cộng dịch trái cho số không dấu. 7. Trình bày thuật toán và cấu trúc khối nhân cộng dịch phải cho số không dấu, so sánh với khối nhân cộng dịch trái. 8. Trình bày thuật toán và cấu trúc khối nhân số có dấu dùng mã hóa BOOTH cơ số 2. 9. Trình bày thuật toán và cấu trúc khối nhân số có dấu dùng mã hóa BOOTH cơ số 4, so sánh với các thuật toán nhân thông thường. 10. Trình bày thuật toán và cấu trúc khối chia số không dấu phục hồi phần dư. 11. Trình bày thuật toán và cấu trúc khối chia số không dấu không phục hồi phần dư. 12. Trình bày thuật toán và cấu trúc khối chia số có dấu. 13. Các loại khối nhớ RAM, ROM. 13. Trình bày thuật toán xây dựng FIFO và LIFO trên cơ sở Dual-port RAM. 14. Máy trạng thái, cấu trúc máy trạng thái mô tả bằng VHDL, ứng dụng.