VericodeRTL · DV · QUIZTìm bài học, kiến thức…Ctrl K
Học để hiểu. Thực hành để vững.

Nhân binary: partial product, Booth và cây carry-save

Khoảng 65 phútMức 3/3Bản nháp: một số khẳng định chưa đối chiếu spec

Tiên quyết

Sau bài này bạn sẽ

  • Giữ đúng trọng số và độ rộng các partial product
  • Phân biệt cộng hàng với giảm cột theo carry-save/Wallace
  • Lần Booth bốn bước và giải thích guard bit cho số âm nhỏ nhất

Nhân tạo nhiều hàng cần cộng

Nhân binary vẫn là nhân theo từng chữ số, nhưng mỗi chữ số chỉ 0 hoặc 1. Một bit 1 của multiplier lấy một bản multiplicand dịch theo trọng số; bit 0 đóng góp hàng 0.

Hai số unsigned bốn bit có tích lớn nhất 15 nhân 15 bằng 225, cần tám bit. Với signed two’s complement bốn bit, tích nằm trong −56 tới +64 và cũng vừa tám bit signed. Cùng raw input nhưng cách đọc signed/unsigned có thể cho hai tích khác nhau.

AND tạo bit, vị trí quyết định trọng số

Ví dụ 13 nhân 3, tức binary 1101 nhân 0011:

Bit multiplier Hàng đóng góp, viết đủ tám bit Giá trị
Bit 0 bằng 1 00001101 13
Bit 1 bằng 1 00011010 26
Bit 2 bằng 0 00000000 0
Bit 3 bằng 0 00000000 0
Tổng 00100111 39

Mỗi partial bit là AND của một bit A và một bit B, mang trọng số 2^(i+j). Hàng thứ i phải dịch trái i vị trí sau khi đã giữ đủ độ rộng.

Không làm dịch trên một từ hẹp rồi mới mở rộng: phần bit rơi ra đã mất. Tích đầy đủ và tích chỉ giữ các bit thấp là hai hợp đồng khác nhau.

Cộng các hàng thành một mảng đều

Một cách dễ lần là cộng hàng 0 với hàng 1, cộng tiếp hàng 2, rồi hàng 3. Các ô AND và adder có thể sắp theo hàng/cột thành một cấu trúc array.

Ví dụ trong bài dùng bản cộng hàng tường minh để đối chiếu. Nếu mỗi bước dùng một carry-propagate adder, carry có thể phải chạy qua nhiều bit ở từng hàng. Những array multiplier tối ưu hơn bố trí full/half-adder để phân phối sum/carry theo trọng số; không mặc định mọi mạch có tên “array” đều là cùng một topology.

Điểm chung cần hiểu là các partial product được tạo theo vị trí cố định. Synthesis có thể đổi cấu trúc, chia sẻ hoặc map sang phần cứng nhân có sẵn; source không tự xác nhận timing thực.

Carry-save giảm ba bit cùng trọng số

Một full-adder nhận ba bit ở cùng trọng số, trả sum ở trọng số ấy và carry ở trọng số gấp đôi. Vì x+y+z=s+2c, giá trị được giữ dù số bit ở cột hiện tại giảm.

Với cả từ dữ liệu, XOR từng cột tạo một hàng sum; majority từng cột tạo carry chuyển sang cột cao hơn. Chưa cần carry chạy qua toàn bộ từ ở mỗi bước giảm. Đây là carry-save.

Độ rộng vẫn quan trọng. Ba số hai bit cùng bằng 3 có tổng 9. Hàng sum/carry trung gian cần giữ đủ bit; cắt carry cao rồi cộng cuối sẽ ra sai.

Sau khi chỉ còn hai hàng, vẫn cần một carry-propagate adder để tạo kết quả binary thông thường. Carry-save không làm carry biến mất; nó hoãn việc lan carry toàn từ tới bước cuối.

Cây giảm cột theo cách Wallace

Xếp mọi partial bit vào cột theo trọng số. Ở mỗi tầng, chọn các nhóm ba bit cùng cột, dùng full-adder tạo sum và carry cho tầng tiếp theo; các bit còn lại đi tiếp. Không dùng ngay carry vừa tạo như một input khác trong cùng tầng.

Một cấu trúc bốn-bit trong ví dụ có chiều cao từng cột, từ trọng số thấp tới cao, như sau:

Tầng Số bit ở các cột trọng số 0 tới 7
Partial product ban đầu 1,2,3,4,3,2,1,0
Sau lần giảm 1 1,2,1,3,2,3,1,0
Sau lần giảm 2 1,2,1,1,3,1,2,0
Sau lần giảm 3 1,2,1,1,1,2,2,0

Còn tối đa hai bit mỗi cột thì ghép thành hai hàng và cộng cuối. Cấu trúc minh họa này dùng sáu full-adder giảm cột; đó là đếm sơ đồ đã viết, không phải chứng nhận số cell tối thiểu sau mapping.

So với cộng lần lượt cả hàng, tree thay cách tổ chức phần giảm partial product. Lợi ích timing/area thực còn phụ thuộc cách nhóm, cell, wire và phần cộng cuối; không dùng tên Wallace để khẳng định mọi implementation nhanh hơn.

Booth dùng các chuyển tiếp của multiplier có dấu

Một dãy bit 1 liên tiếp có thể biểu diễn bằng hiệu hai lũy thừa của 2. Booth radix-2 khai thác chuyển tiếp giữa bit multiplier hiện tại và bit ngay phía phải nó.

Giữ accumulator A, multiplier Q và một bit trước q_prev ban đầu bằng 0. Gọi M là multiplicand:

Cặp Q0 / q_prev Việc trước khi dịch
00 Không cộng/trừ
01 A cộng M
10 A trừ M
11 Không cộng/trừ

Sau đó dịch phải số học toàn bộ trạng thái ghép A/Q/q_prev để giữ dấu. Lặp bốn lần cho multiplier bốn bit trong ví dụ. Không dịch riêng Q rồi bỏ bit từ A chuyển sang; như vậy sẽ phá trạng thái của thuật toán.

Booth có thể giảm công việc với các dãy 1 dài, nhưng không phải mọi pattern đều lợi như nhau. Kiểu iterative hay unrolled, số chu kỳ và pipeline là lựa chọn kiến trúc riêng.

Lần bốn bước với −3 nhân 5

M bằng −3, Q ban đầu 0101; A dùng năm bit và bắt đầu 0. Bảng ghi giá trị ngay sau mỗi phép dịch:

Bước Cặp trước dịch Thao tác trên A A sau dịch Q sau dịch q_prev
1 10 Trừ M: A thành +3 +1 1010 1
2 01 Cộng M: A thành −2 −1 0101 0
3 10 Trừ M: A thành +2 +1 0010 1
4 01 Cộng M: A thành −2 −1 0001 0

Ghép A/Q cuối rồi lấy tám bit kết quả cho 11110001, tức −15. Bit dấu dư của A phải nhất quán với dấu kết quả.

Đây là bốn bước thuật toán, không phải waveform bốn chu kỳ clock. Ví dụ HDL unroll vòng lặp trong logic tổ hợp; testbench đợi ổn định để kiểm. Một mạch iterative có thanh ghi và handshake sẽ có hợp đồng thời gian khác.

Guard bit bảo vệ ca số âm nhỏ nhất

Bốn bit signed chứa −8 nhưng không chứa +8. Nếu M bằng −8 và một bước yêu cầu trừ M, giá trị trung gian +8 cần nhiều hơn bốn bit signed.

Ví dụ giữ A và M đã sign-extend ở năm bit; trạng thái ghép A/Q/q_prev rộng mười bit. Kết quả ghép A/Q có chín bit, sau đó kiểm sign extension trước khi lấy tám bit cuối.

Array và cây partial product trong bài nhận cách đọc unsigned; Booth nhận cách đọc signed. Với raw A bằng 1111 và B bằng 0010, hai nhánh unsigned cho 30 còn Booth cho −2. Không gọi sự khác ấy là bug khi hai hợp đồng diễn giải khác nhau.

Những lỗi thường gặp ở bộ nhân

  • Dịch partial product khi độ rộng chưa đủ.
  • Đối chiếu signed với unsigned mà không giải mã input.
  • Quên dịch carry sang trọng số kế trong compressor.
  • Dùng carry của tầng vừa tạo ngay trong cùng tầng rồi tưởng vẫn là cấu trúc song song đã mô tả.
  • Giữ accumulator Booth quá hẹp nên hỏng ca M bằng số âm nhỏ nhất.
  • Gọi số bước thuật toán là số chu kỳ hoặc timing silicon dù mạch hiện tại là unrolled.

Khi review, ghi rõ miền số, độ rộng đầu ra và có giữ tích đầy đủ không. Sau đó mới bàn cấu trúc cộng, số tầng và pipeline.

Tính trọng số trước khi tối ưu cấu trúc

  1. Viết các partial product tám bit của unsigned 11 nhân 5.
  2. Vì sao ba bit 1 ở cùng một cột tương đương sum 1 và carry 1 ở cột kế?
  3. Với Booth, cặp 10 yêu cầu cộng hay trừ M? Bước nào làm thay đổi q_prev?
  4. Giải thích tại sao M bằng −8 cần guard bit trong ví dụ.
  5. Raw 1000 nhân 0010 có kết quả unsigned và signed nào?
  6. Nếu muốn bốn chu kỳ xử lý thay vì unrolled, cần thêm trạng thái và tín hiệu nào vào hợp đồng?

Kiểm tra

Tự kiểm tra: Nhân binary: partial product, Booth và cây carry-save

  1. Trong unsigned 13 nhân 3, partial product từ bit 1 của multiplier bằng bao nhiêu?
  2. Ba bit 1 ở cùng trọng số qua full-adder cho sum/carry nào?
  3. Vì sao accumulator Booth cần năm bit trong ví dụ bốn bit?
  4. Booth xét cặp Q0/q_prev=10 thì làm gì trước dịch?
  5. Raw 1111 nhân 0010 cho unsigned và signed lần lượt bằng gì?
  6. Bảng bốn bước Booth của mạch unrolled có tự chứng minh latency bốn clock không?

Bằng chứng kiểm chứng

Expected tính trước chạy: MULTIPLY CHECK vectors=256 unsigned=256 signed=256 negative=112 zero=31 unsigned_max=225 signed_min=-56 signed_max=64 booth_steps=4 time_ns=256.

Partial products, cây compressor và Booth có guard bit

Kỳ vọng tính trước chạy: MULTIPLY CHECK vectors=256 unsigned=256 signed=256 negative=112 zero=31 unsigned_max=225 signed_min=-56 signed_max=64 booth_steps=4 time_ns=256

mul_core.sv RTL
`timescale 1ns/1psmodule mul_core(input logic [3:0] a,b,output wire [7:0] array_product,wallace_product, output logic signed [7:0] booth,output logic signed [8:0] booth_wide,output logic [39:0] booth_trace); wire [7:0] row0=a[0]?{4'b0000,b}:8'b0; wire [7:0] row1=a[1]?{3'b000,b,1'b0}:8'b0; wire [7:0] row2=a[2]?{2'b00,b,2'b00}:8'b0; wire [7:0] row3=a[3]?{1'b0,b,3'b000}:8'b0; wire [7:0] row01=row0+row1,row012=row01+row2; assign array_product=row012+row3; wire pp_0_0=a[0]&b[0]; wire pp_0_1=a[0]&b[1]; wire pp_0_2=a[0]&b[2]; wire pp_0_3=a[0]&b[3]; wire pp_1_0=a[1]&b[0]; wire pp_1_1=a[1]&b[1]; wire pp_1_2=a[1]&b[2]; wire pp_1_3=a[1]&b[3]; wire pp_2_0=a[2]&b[0]; wire pp_2_1=a[2]&b[1]; wire pp_2_2=a[2]&b[2]; wire pp_2_3=a[2]&b[3]; wire pp_3_0=a[3]&b[0]; wire pp_3_1=a[3]&b[1]; wire pp_3_2=a[3]&b[2]; wire pp_3_3=a[3]&b[3]; wire cs_0_2_sum=pp_0_2^pp_1_1^pp_2_0; wire cs_0_2_carry=(pp_0_2&pp_1_1)|(pp_0_2&pp_2_0)|(pp_1_1&pp_2_0); wire cs_0_3_sum=pp_0_3^pp_1_2^pp_2_1; wire cs_0_3_carry=(pp_0_3&pp_1_2)|(pp_0_3&pp_2_1)|(pp_1_2&pp_2_1); wire cs_0_4_sum=pp_1_3^pp_2_2^pp_3_1; wire cs_0_4_carry=(pp_1_3&pp_2_2)|(pp_1_3&pp_3_1)|(pp_2_2&pp_3_1); wire cs_1_3_sum=cs_0_2_carry^cs_0_3_sum^pp_3_0; wire cs_1_3_carry=(cs_0_2_carry&cs_0_3_sum)|(cs_0_2_carry&pp_3_0)|(cs_0_3_sum&pp_3_0); wire cs_1_5_sum=cs_0_4_carry^pp_2_3^pp_3_2; wire cs_1_5_carry=(cs_0_4_carry&pp_2_3)|(cs_0_4_carry&pp_3_2)|(pp_2_3&pp_3_2); wire cs_2_4_sum=cs_1_3_carry^cs_0_3_carry^cs_0_4_sum; wire cs_2_4_carry=(cs_1_3_carry&cs_0_3_carry)|(cs_1_3_carry&cs_0_4_sum)|(cs_0_3_carry&cs_0_4_sum); wire [7:0] wallace_row0={1'b0,cs_1_5_carry,cs_2_4_carry,cs_2_4_sum,cs_1_3_sum,cs_0_2_sum,pp_0_1,pp_0_0},wallace_row1={1'b0,pp_3_3,cs_1_5_sum,1'b0,1'b0,1'b0,pp_1_0,1'b0}; assign wallace_product=wallace_row0+wallace_row1; logic signed [4:0] accumulator,multiplicand; logic [3:0] q; logic previous; logic signed [9:0] shifted; always_comb begin  accumulator=0;multiplicand={a[3],a};q=b;previous=0;shifted=0;booth_trace=0;  for(int k=0;k<4;k++)begin   case({q[0],previous})    2'b01:accumulator=accumulator+multiplicand;    2'b10:accumulator=accumulator-multiplicand;    default:accumulator=accumulator;   endcase   shifted=$signed({accumulator,q,previous})>>>1;   {accumulator,q,previous}=shifted;   booth_trace[10*k+:10]=shifted;  end  booth_wide=$signed({accumulator,q});  booth=booth_wide[7:0]; endendmodule
tb.sv testbench
`timescale 1ns/1psmodule tb_a3_mul; logic [3:0] a,b;wire [7:0] array_product,wallace_product; wire signed [7:0] booth;wire signed [8:0] booth_wide;wire [39:0] booth_trace; mul_core dut(.*); logic [9:0] expected_step[4]='{10'h035,10'h3ea,10'h025,10'h3e2}; int vectors=0,unsigned_count=0,signed_count=0,negatives=0,zeros=0,unsigned_max=0,signed_min=0,signed_max=0,booth_steps=0; int ai,bi,unsigned_product,signed_product; initial begin  for(int ia=0;ia<16;ia++)for(int ib=0;ib<16;ib++)begin   a=4'(ia);b=4'(ib);#1;vectors++;   unsigned_product=ia*ib;ai=ia<8?ia:ia-16;bi=ib<8?ib:ib-16;signed_product=ai*bi;   if(int'(array_product)!=unsigned_product||int'(wallace_product)!=unsigned_product)$fatal(1,"Unsigned array/compressor mismatch a=%0d b=%0d",ia,ib);   unsigned_count++;   if(int'(booth)!=signed_product||int'(booth_wide)!=signed_product||booth_wide[8]!=booth_wide[7])$fatal(1,"Booth width/sign mismatch a=%0d b=%0d",ia,ib);   signed_count++;   if(signed_product<0)negatives++;if(signed_product==0)zeros++;   if(unsigned_product>unsigned_max)unsigned_max=unsigned_product;   if(signed_product<signed_min)signed_min=signed_product;   if(signed_product>signed_max)signed_max=signed_product;   if(ia==13&&ib==5)for(int k=0;k<4;k++)begin    if(booth_trace[10*k+:10]!==expected_step[k])$fatal(1,"Booth worked-step mismatch step=%0d",k);    booth_steps++;   end  end  if(vectors!=256||unsigned_count!=256||signed_count!=256||negatives!=112||zeros!=31||unsigned_max!=225||signed_min != -56||signed_max!=64||booth_steps!=4||$time!=256)$fatal(1,"Multiplier experiment contract");  $display("MULTIPLY CHECK vectors=%0d unsigned=%0d signed=%0d negative=%0d zero=%0d unsigned_max=%0d signed_min=%0d signed_max=%0d booth_steps=%0d time_ns=%0d",vectors,unsigned_count,signed_count,negatives,zeros,unsigned_max,signed_min,signed_max,booth_steps,$time);  $finish; endendmodule

Đã kiểm chứng thế nào

  • Phân tích và elaborate theo LRM (pyslang 12.1.0)
  • Lint -Wall (Verilator 5.050)
  • Mô phỏng, exit 0 và output khớp kỳ vọng tính tay (Verilator 5.050, 2-state)
  • Tổng hợp, số cell khớp kỳ vọng (Yosys 0.70)

Output phải khớp: MULTIPLY CHECK vectors=256 unsigned=256 signed=256 negative=112 zero=31 unsigned_max=225 signed_min=-56 signed_max=64 booth_steps=4 time_ns=256

Kỳ vọng sau tổng hợp: mul_core: $_*DFF* = 0mul_core: $_*LATCH* = 0

Verilator 5.050 two-state and finite four-bit domains; no all-width/XZ conformance. Generic combinational synthesis, not physical timing/PPA or exact cell mapping.

Các kiểm tra chạy lúc xây dựng nội dung (2026-11-11), không chạy trong trình duyệt. Kỳ vọng được tính tay trước khi chạy.

Duyệt mọi 256 cặp raw bốn bit. Hai nhánh unsigned so với tích số nguyên không dấu; Booth so với hai số nguyên đã giải mã signed. Kiểm cả chín bit wide và sign extension trước cắt. Có 112 tích âm, 31 tích zero; cực trị unsigned 225, signed −56/+64.

Bảng M=−3,Q=5 đã tính trước thành bốn trạng thái mười bit 035/3ea/025/3e2 ở hex; testbench đối chiếu từng trạng thái packed, không chỉ kết quả cuối. Các ca M=−8 cũng nằm trong miền vét cạn.

Parser/lint/simulation/synthesis đạt. Sơ đồ cột có ba tầng giảm và sáu full-adder theo cách dựng; Yosys chỉ kiểm generic không có FF/latch, không buộc giữ đúng cell/topology ấy. Các output trace dùng cho học và kiểm, không phải phép đo PPA.

Nguồn binary arithmetic cung cấp nền shift-and-add. Phần cây cột và recoding là mô hình nguyên bản được giải thích bằng trọng số/recurrence và kiểm hữu hạn; không gắn cited cho tài liệu Wallace/Booth trực tuyến chưa truy cập được. LRM về signed/width/shift vẫn needs-spec-check.

[1] [2] [3]

Bài liên quan

Nguồn và mức độ đối chiếu

  1. Binary Arithmetic — bản chụp resources.zip, Binary Multiplication; Binary Multiplication Rules; Multiplication Algorithm. Trích dẫn; nguồn đã đọc các mục liên quan.
  2. Thí nghiệm nguyên bản A3.mul, All four-bit unsigned row/tree products, signed Booth products, guard-bit cases and four independently predicted recoding states. Trích dẫn; nguồn đã đọc toàn văn.
  3. IEEE 1800-2023 SystemVerilog LRM, Signed extension, arithmetic shifting of concatenated state, combinational loops and width-preserving compressor sums — chưa đối chiếu LRM. Chưa đối chiếu với văn bản nguồn (chưa mở).