Các phép tính số học với số nguyên
Các phép tính số học với số nguyên
Bây giờ gọi 
là số mà các bit đã được đảo và coi chúng như một số nguyên không có dấu ta có: 
được gọi là số bù 1 của A.
Bây giờ, lấy cộng với 1 ta được một số nguyên B như sau : 
B được gọi là số bù 2 của A (số bù 2 bằng số bù 1 cộng với 1). Lấy A+B ta có :
Như vậy, về mặt toán học, số bù 2 của một số chính là số đối của nó và do đó, một số dương sẽ có số bù 2 là một số âm cùng giá trị tuyệt đối và ngược lại. Với phép biến đổi trên, chúng ta cần chú ý một số đặc điểm sau đây :- Nếu A = 0 và với số 8 bit ta có :
- Số lượng các mẫu bit khác nhau ở trong một từ n bit là 2n, mà nó lại phải là số chẵn. Chúng ta luôn muốn biểu diễn được các số nguyên dương và nguyên âm và 0. Nếu số lượng số nguyên âm và dương được biểu diễn là bằng nhau (dấu – độ lớn) thì có hai cách biểu diễn cho 0. Nếu 0 chỉ có một cách biểu diễn (số bù hai) thì các số âm và dương được biểu diễn là không bằng nhau. Đối với trường hợp của số bù hai thì ta chỉ có cách biểu diễn n bit cho -2n mà không có cách biểu diễn cho 2n. Điều này được minh hoạ như bảng sau. 
Như vậy, trong cách biểu diễn dấu – độ lớn thì quy tắc để tính phần bù của số nguyên là đơn giản, chỉ cần đảo bit dấu. Trong kiểu số bù hai thì phần bù của số nguyên được thực hiện theo quy tắc sau: - Đảo dấu tất cả các bit của số nguyên (kể cả bit dấu).- Kết quả như là số nguyên nhị phân không dấu cộng 1.Ví dụ:
Như đã biết đảo của đảo của một số sẽ là chính nó: 
Phép cộng : Phép cộng các số hệ 2 thực hiện giống như đối với các số hệ mười. Quy tắc cộng như sau:
Phép cộng số bù hai được minh hoạ bởi các ví dụ sau. Nếu kết quả của phép toán là dương thì chúng ta có được một số dương trong ký hiệu thập phân bình thường. Còn nếu kết quả là một số âm thì chúng ta có được một số âm ở dạng mã bù hai. Chú ý rằng, trong một vài ví dụ có một vài bit nhớ vượt quá giới hạn của từ thì nó sẽ bị lờ đi. Ở phép cộng bất kỳ thì kết quả có thể lớn hơn độ lớn của từ được sử dụng. Trạng thái này được gọi là tràn trên (overflow). Nếu hai số được cộng đều là dương hoặc cả hai đều là âm thì có thể có hiện tưọng tràn trên và kết quả là ngược dấu. Khi có hiện tượng tràn trên thì ALU phải báo sự việc này ra ngoài để không sử dụng kết quả này. Chú ý rằng tràn trên có thể xuất hiện có nhớ hoặc là không.Phép trừ:Phép trừ các số hệ 2 được thực hiện theo quy tắc sau :
Để trừ một số (số bị trừ) cho một số khác (số trừ) có thể thực hiện bằng cách tạo số bù hai của số trừ và cộng với số bị trừ để được kết quả. Vì vậy, phép trừ được thực hiện thực chất là nhờ phép cộng.Các ví dụ sau đây sẽ minh hoạ cho điều nói trên (hai ví dụ sau có áp dụng nguyên tắc tràn trên). 
Hình sau đưa ra đường đi của dữ liệu và yếu tố phần cứng để thực hiện phép cộng và phép trừ. Phần tử chính là một bộ cộng nhị phân, nó nhận hai số vào và đưa ra là tổng và tín hiệu báo nếu tràn. Bộ cộng nhị phân coi hai số như là các số nguyên không dấu. Đối với phép cộng thì hai số được đưa ra để cộng là từ hai thanh ghi, như trên hình vẽ là thanh ghi A và B. Kết quả được lưu vào một trong các thanh ghi này chứ không phải là thanh ghi thứ ba. Tín hiệu báo tràn được lưu vào trong 1 bit cờ tràn (nếu không tràn thì bit này bằng 0, nếu tràn thì bằng 1). Đối với phép trừ, số bị trừ (thanh ghi B) được gửi đến một bộ tạo mã bù hai và gửi tiếp đến bộ cộng.
Hình 1 – Sơ đồ khối phần cứng của bộ cộng và trừPhép nhân hệ hai của các số nguyên không dấu: Phép nhân trong hệ 2 được thực hiện theo quy tắc sau :
Theo quy tắc trên ta thấy, phép nhân hệ hai của các số nguyên nhị phân không dấu có thể thực hiện theo thuật toán cộng và dịch như sau : - Thành phần đầu tiên của tổng tích luỹ thu được là tích của số LSB trong số nhân với số bị nhân. Nếu LSB = 0 thì thành phần này cũng bằng 0, còn nếu LSB =1 thì thành phần này chính bằng số bị nhân.- Mỗi thành phần thứ i tiếp theo của tổng tích luỹ sẽ được tính bằng cách tương tự nhưng phải dịch trái i bit ( có thể bỏ qua các thành phần bằng 0 )- Tổng của các thành phần là tích cần tìm.- Kết quả phép nhân hai số nguyên nhị phân n bit có độ dài 2n bit.Tuy nhiên, chúng ta có thể thực hiện phép nhân một cách có hiệu quả hơn. Đầu tiên, ta thực hiện cộng liên tiếp các tích từng phần cho đến khi kết thúc. Điều này sẽ làm triệt tiêu sự lưu lại của tất cả các tích thành phần, dẫn đến việc sử dụng các thanh ghi ít hơn để lưu giữ các kết quả. Mặt khác, chúng ta có thể loại ra các phân tử phát sinh của tích thành phần. Đối với bit 1 trong số nhân thì thực hiện phép cộng và một phép dịch, nhưng đối với bit 0, thì chỉ có phép dịch là được thực hiện.Hình 2 – Phần cứng thực hiện phép nhân hai số nhị phân không dấuSố nhân và số bị nhân được tải vào hai thanh ghi (Q và M), còn thanh ghi thứ ba là thanh ghi A, ban đầu nó được thiết lập ở mức 0. Thanh ghi 1 bit C được khởi đầu bằng 0 được dùng để lưu bit nhớ của phép cộng.Các bit của số nhân được đọc lần lượt một cách logic. Nếu Qo là 1 thì số bị nhân được cộng với thanh ghi A và kết quả được lưu trong thanh ghi A. Sau đó tất cả các bit của các thanh ghi C, A và Q được dịch sang phải một bit, các bit C dịch tới An-1, A0 tới Qn-1và Q0thì thôi.Nếu Q0 là 0 thì phép cộng không được thực hiện, chỉ thực hiện phép dịch. Quá trình này được thực hiện lặp lại với mỗi bit của số nhân. Kết quả của tích 2n bit được chứa trong các thanh ghi A và Q. Chú ý rằng trong chu kỳ thứ hai, khi một bit của số nhân là 0 thì phép cộng không được thực hiện.Phép nhân số bù hai:Chúng ta biết rằng phép cộng và phép trừ được số nguyên không dấu được tính như ví dụ sau:
Nếu các số trên được xem như là các số nguyên bù 2, chúng ta thấy phép cộng 1001 (-710) với 0011 (310) sẽ được 1100 (-410). Từ đó ta nhận thấy rằng các phép tính đơn giản này sẽ không áp dụng được cho phép nhân. Để thấy rõ điều này ta lấy ví dụ nhân 1011 (1110) với 1101 (1310) và được 10001111 (14310). Nếu xem các số này như các số bù hai thì ta có 1011 (-510) nhân với 1101 (-310) sẽ được kết quả là 1000 1111 (-11310). Quá trình thực hiện phép nhân này theo sơ đồ khối trên hình 2 được diễn giải như sau:
Ví dụ này chứng minh rõ phép nhân sẽ không thực hiện được nếu cả hai số nhân và số bị nhân là âm. Trong thực tế nó sẽ không thực hiện được nếu một trong hai số nhân hoặc số bị nhân là âm. Ta biết rằng, phép nhân một số nhị phân 2n bit được thực hiện nhờ sự dịch chuyển các số đó tới n bit bên trái. Vì lý do do này ta có thể tạo ra tích từng phần bằng cách thực hiện phép nhân theo cách khác. Tích từng phần sẽ được coi như số 2n bit được tạo ra từ số bị nhân n bit. Vì vậy, cũng như số nguyên không dấu, số bị nhân 4 bit 1011 sẽ được lưu ở trong 1 từ 8 bit là 0000 1011. Mỗi tích từng phần (khác 20) có được từ số đó đã được dịch sang trái, các bít ở vị trí bên phải sẽ được điền bằng các số 0.
Hình 3 – Sơ đồ khối phép nhân hai số nhị phân không dấu
Giờ đây chúng ta có thể làm sáng tỏ được rằng phép nhân sẽ không làm việc nếu số bị nhân là âm. Vấn đề là mỗi lần số bị nhân là âm thì tích từng phần phải là số âm trên vùng 2n bit. Bit dấu của tích từng phần phải sắp xếp lại. Ta chứng minh điều này dựa vào ví dụ trên bảng 1-9, biểu diễn phép nhân số 1001 (910) với 0011 (310). Nếu được coi như là số nguyên không dấu thì phép nhân 9×3=27 được thực hiện đơn giản. Tuy nhiên nếu 1001 thì được coi như là số bù hai thì giá trị của nó là -7. Sau đó mỗi tích từng phần phải được như là số bù hai âm của các bít 2n (8 bit), được biểu diễn như hình 1-9b. Chú ý rằng phép tính phải được thực hiện bằng cách kéo dài mỗi tích từng phần sang bên trái với số bit nhị phân bằng 1.
Một trong số những thuật toán được sử dụng để thực hiện phép nhân các số nguyên bù hai là thuật toán Booth. Thuật toán này rất có lợi để tăng tốc độ thực hiện các phép nhân, nó có liên quan đến việc tính toán gần đúng. Thuật toán Booth được miêu tả trong hình 1-10 và được mô tả như sau : Giống như phần trên, số nhân và số bị nhân được đặt riêng rẽ trong các thanh ghi Q và M. Ở đây thanh ghi 1 bít được đặt một cách lôgic vào bên phải của bít có nghĩa nhỏ nhất của thanh ghi Q và được định nghĩa là Q-1.Kết của phép nhân sẽ xuất hiện trong các thanh ghi A và Q. A và Q được khởi tạo bằng 0. Giống như trước thì các bít của phép nhân sẽ kiểm tra một cách có hệ thống theo thời gian. Bây giờ, mỗi bít đã được kiểm tra và bít của bên phải của nó cũng được kiểm tra. Nếu hai bít giống nhau (11 hay 0 0 ) thì tất cả các bít của thanh ghi A và Q và Q1 được dịch sang bên phải 1 bít. Nếu hai bít này khác nhau thì số bị nhân được cộng hay trừ từ thanh ghi A, tuỳ theo hai bít là 01 hay 10. Khi thực hiện phép cộng hay phép trừ thì đều được dịch sang phải. Trong mỗi trường hợp, sự dịch phải là ta thực hiện dịch bít ở phía bên trái nhất của A đó là An-1, không những được dịch vào An-2 mà còn vào An-1. Đây là yêu cầu để giữ nguyên dấu của các số trong A và Q. Đây được hiểu như là phép dịch số học, từ đó sẽ giữ nguyên bit dấu.Ví dụ sau mô tả trình tự phép nhân của số 7 với 3 của thuật toán Booth.
Hình 4 – Thuật toán Booth cho phép nhân số bù haiĐể rõ hơn ta mô tả phép toán trong các ví dụ sau. Ở các ví dụ này ta có thể thấy nó thực hiện phép nhân với bất kỳ các số dương và số âm. Khối của các số 1 và 0 được đưa ra ngoài, với trung bình chỉ là một phép cộng hoặc trừ cho mỗi khối. 
Tại sao thuật toán Both laị làm việc được ? Coi trường hợp đầu tiên của một số nhân dương trong trường hợp đặc biệt thì xem một số nhân dương gồm có một khối của 1 được bao quanh bởi 0, ví dụ 000 1110. Như ta đã biết, phép nhân có thể được thực hiện bằng cách cộng dịch dần của các số bị nhân: 
Số của các phép toán có thể được rút gọn đến hai nếu như chúng ta để ý: 
Vì vậy: 
Phần tích thể được tạo ra nhờ một phép cộng và một phép trừ của số bị nhân. Sơ đồ này có thể mở rộng tới bất kỳ số nào của các khối của các số 1 trong số nhân kể cả trường hợp trong đó số (đơn lẻ) 1 được xem như là một khối, thật vậy:
Thuật toán Booth phù hợp với sơ đồ này bằng cách thực hiện phép trừ khi số đầu tiên của khối gặp (1-0) và thực hiện phép cộng khi ở cuối khối gặp (0-1). Để diễn giải sơ đồ khi thực hiện việc nhân số âm, chúng ta cần htực hiện theo cách sau:Cho X là một số âm trong số bù 2. Biểu diễn 
Khi đó giá trị của X có thể được biểu diễn như sau:
Bây giờ chúng ta biết rằng bit trái nhất của X là 1, lúc đó X là số âm. Coi bit 0 bên trái nhất có vị trí Kth thì dạng của X sẽ là: 
Giá trị của X là: 
Từ công thức (1) ta có : 
Sắp xếp lại : 
Thay (5) vào công thức (4) ta có : 
Sau cùng, chúng ta cần quay trở lại với thuật toán của Booth. Ta nhớ lại biểu diễn của X (công thức (3)), nó có thể xoá tất cả các bit từ X0 đến bit 0 bên trái nhất được xử lý một cách thích hợp nhất, từ đó chúng đưa ra tất cả các dạng trong công thức (6) trừ (-2K+1) và đó là dạng thích hợp nhất. Như quá trình kiểm tra thuật toán ở số O bên trái nhất và khi nào gặp số kế tiếp (2k+1) thì xảy ra quá trình chuyển tiếp 1-0 và thực hiện phép trừ ở (-2K+1). Đây là số hạng còn lại trong công thức (6). Chúng ta xem xét phép nhân một vài số bị nhân với (-6). Trong cách biểu diện số bù 2, sử dụng từ 8 bít, (-6) được biểu diễn là 1111010 theo công thức (4), ta thấy rằng:
Vì vậy : 
Sử dụng công thức (6). 
Ta có thể kiểm tra tính đúng dắn của kết quả Mx(-6). Sau cùng chúng ta cũng có kết quả sau: 
Bây giờ ta đã có thể thấy công dụng của thuật toán Booth. Nó cho phép thực hiện một phép trừ khi số 1 đầu tiên là phép đếm ngược (1-0), một phép cộng nếu số đểm là (0-1) và cuối cùng có một phép trừ khác số 1 đầu tiên của khối tiếp theo của các số 1 được đếm. Do đó thuật toán Booth thực hiện ít hơn các phép cộng và phép trừ so với các thuật toán đơn giản. Phép chia hệ hai của các số nguyên không dấu:Phép chia là một phép tính phức tạp hơn so với các phép tính khác nhưng về cơ bản thì nó vẫn được dựa trên những nguyên tắc chung. Đầu tiên là việc xây dựng thuật toán và các phép dịch các bit, phép cộng hoặc trừ. Phép chia có thể được thực hiện bằng các phép trừ và phép dịch liên tiếp cho đến khi không còn gì để trừ hoặc số bị trừ nhỏ hơn số chia.Ví dụ : 215 / 22 = 9 dư 17 . Thực hiện phép chia này trong hệ 2.
Ví dụ trên được diễn giải chi tiết như sau: đầu tiên kiểm tra từng bít của số bị chia từ trái qua phải cho đến khi nào nhóm các bit đó biểu diễn một số lớn hơn hoặc bằng số chia, có nghĩa là số bị chia có thể chia được cho số chia. Nếu còn chưa chia được cho số chi thì ta thêm các số 0 vào thương số từ trái sang phải. Khi chia được cho số chia thì ta thêm 1 vào thương số và lấy số đó trừ đi số chia. Kết quả của phép trừ được gọi là số dư thành phần (partial remainder). Từ đây, phép chia lặp lại các bước như trên. Mỗi lần lặp như vậy ta bổ xung một bit từ số bị chia vào số dư thành phần cho đến khi nào nó lớn hơn số bị chia. Giống như trên, ta lại trừ đi số chia để dược một số dư thành phần mới. Quá trình cứ lặp đi lặp lại như trên cho đến khi tất cả các bit của số bị chia đã hết. Tuy nhiên, phép chia thực hiện theo cách trên rất khó khăn cho các VXL vốn chỉ gồm các phần tử để thực hiện phép cộng và dịch. Để khắc phục các khó khăn này người ta dùng thuật toán sau:- Đổi số chia ra số bù 2 của nó.- Lấy số bị chia cộng với số bù 2 của số chia ( trừ đi số chia ).Nếu kết quả này có bit dấu bằng 0 ( nghĩa là phần này của số bị chia chia được cho số chia ) thì bit tương ứng của thương bằng 1.Nếu kết quả này có bit dấu bằng 1 (nghĩa là phần này của số bị chia không chia được cho số chia ) thì bit tương ứng của thương bằng 0 và buộc phải khôi phục lại giá trị ban đầu của số bị chia bằng cách cộng kết quả với số chia ở mã hệ 2.- Dịch trái kết quả thu được ở trên và làm lại bước 2 cho đến khi nhận được kết quả là 0 ( chia hết) hoặc nhỏ hơn số chia (chia còn dư).Bây giờ ta thực hiện lại ví dụ trên theo thuật toán này.Số bị chia 215 = 0 1 1 0 1 0 1 1 1Số chia 22 = 0 1 0 1 1 0Số bù 2 của số chia = 1 0 1 0 1 0Các bước thực hiện như sau :
Ta cũng có kết quả tương tự. Hình 5 là thuật toán tương ứng để thực hiện phép chia dài. Số chia được đặt trong thanh ghi M, số bị chia thì đặt trong thanh ghi Q. Ở mỗi bước, cùng một lúc thanh ghi A và Q đều được dịch trái một bit. M được trừ A để xác định là có chia phần số dư A hay không. Nếu có thì thì Q0 nhận được một bit 1, nếu không thì Q0 nhận được một bit 0 và M phải được cộng ngược trở lại A để trở lại giá trị trước. Bộ đếm sẽ giảm xuống và tiếp tục thực hiện cho đến bước thứ n. Để kết thúc thì thương số phải nằm trong thanh ghi Q và phần dư phải nằm trong thanh ghi A.Hình 5 – Lưu đồ thuật toán phép chia số nhị phân không dấuPhép chia số bù 2: Phép chia như trên có thể thực hiện được, nhưng gặp một số khó khăn khi mở rộng tới các số âm. Điều này được giải thích như một số ví dụ sau đây.Thuật toán có thể tổng quát thành một số bước như sau:1. Tải số chia vào thanh ghi M và số bị chia vào thanh ghi A, Q. Số bị chia phải nằm trong giới hạn như một số bù hai 2n bit. Vì vậy trong ví dụ này, 4 bít 0111 sẽ trở thành 0000 0111 và 1001 sẽ trở thành 1111 1001.2. Di chuyển A, Q một bit về phía trái.3. Nếu M và A cùng dấu thì thực hiện A ← A – M, ngược lại thì A ← A + M.4. Các phép toán ở trên được gọi là thành công nếu dấu của A trước và sau khi thực hiện không thay đổi.* Nếu các phép toán thành công hoặc (A = 0 AND Q = 0 ), thì thiết lập Q0 ← 1.* Nếu các phép toán không thành công và (A ≠ 0 OR Q ≠ 0), thì Q0 ← 0 và lưu lại giá trị trước đó của A.5. Lặp lại bước 2 tới bước 4 một số lần bằng số bit trong Q.6. Phần dư nằm trong thanh ghi A. Nếu số chia và số bị chia là cùng dấu, thì thương số nằm trong Q. Ngược lại, kết quả đúng là số bù hai của Q.Ta cần chú ý ở ví dụ trên, các phép chia (-7) ÷ (3) và (7) ÷ (-3) tạo ra các số dư khác nhau. Bởi vì số dư được định nghĩa như sau :D = Q*V + RTrong đó:D : Là số bị chia.Q : Là thương số.V : Là số chia.R : là số dư.Các ví dụ trên được thực hiện theo công thức này.
B được gọi là số bù 2 của A (số bù 2 bằng số bù 1 cộng với 1). Lấy A+B ta có :Như vậy, về mặt toán học, số bù 2 của một số chính là số đối của nó và do đó, một số dương sẽ có số bù 2 là một số âm cùng giá trị tuyệt đối và ngược lại. Với phép biến đổi trên, chúng ta cần chú ý một số đặc điểm sau đây :- Nếu A = 0 và với số 8 bit ta có :- Số lượng các mẫu bit khác nhau ở trong một từ n bit là 2n, mà nó lại phải là số chẵn. Chúng ta luôn muốn biểu diễn được các số nguyên dương và nguyên âm và 0. Nếu số lượng số nguyên âm và dương được biểu diễn là bằng nhau (dấu – độ lớn) thì có hai cách biểu diễn cho 0. Nếu 0 chỉ có một cách biểu diễn (số bù hai) thì các số âm và dương được biểu diễn là không bằng nhau. Đối với trường hợp của số bù hai thì ta chỉ có cách biểu diễn n bit cho -2n mà không có cách biểu diễn cho 2n. Điều này được minh hoạ như bảng sau. Như vậy, trong cách biểu diễn dấu – độ lớn thì quy tắc để tính phần bù của số nguyên là đơn giản, chỉ cần đảo bit dấu. Trong kiểu số bù hai thì phần bù của số nguyên được thực hiện theo quy tắc sau: - Đảo dấu tất cả các bit của số nguyên (kể cả bit dấu).- Kết quả như là số nguyên nhị phân không dấu cộng 1.Ví dụ:Như đã biết đảo của đảo của một số sẽ là chính nó: Phép cộng : Phép cộng các số hệ 2 thực hiện giống như đối với các số hệ mười. Quy tắc cộng như sau:Phép cộng số bù hai được minh hoạ bởi các ví dụ sau. Nếu kết quả của phép toán là dương thì chúng ta có được một số dương trong ký hiệu thập phân bình thường. Còn nếu kết quả là một số âm thì chúng ta có được một số âm ở dạng mã bù hai. Chú ý rằng, trong một vài ví dụ có một vài bit nhớ vượt quá giới hạn của từ thì nó sẽ bị lờ đi. Ở phép cộng bất kỳ thì kết quả có thể lớn hơn độ lớn của từ được sử dụng. Trạng thái này được gọi là tràn trên (overflow). Nếu hai số được cộng đều là dương hoặc cả hai đều là âm thì có thể có hiện tưọng tràn trên và kết quả là ngược dấu. Khi có hiện tượng tràn trên thì ALU phải báo sự việc này ra ngoài để không sử dụng kết quả này. Chú ý rằng tràn trên có thể xuất hiện có nhớ hoặc là không.Phép trừ:Phép trừ các số hệ 2 được thực hiện theo quy tắc sau :Để trừ một số (số bị trừ) cho một số khác (số trừ) có thể thực hiện bằng cách tạo số bù hai của số trừ và cộng với số bị trừ để được kết quả. Vì vậy, phép trừ được thực hiện thực chất là nhờ phép cộng.Các ví dụ sau đây sẽ minh hoạ cho điều nói trên (hai ví dụ sau có áp dụng nguyên tắc tràn trên). Hình sau đưa ra đường đi của dữ liệu và yếu tố phần cứng để thực hiện phép cộng và phép trừ. Phần tử chính là một bộ cộng nhị phân, nó nhận hai số vào và đưa ra là tổng và tín hiệu báo nếu tràn. Bộ cộng nhị phân coi hai số như là các số nguyên không dấu. Đối với phép cộng thì hai số được đưa ra để cộng là từ hai thanh ghi, như trên hình vẽ là thanh ghi A và B. Kết quả được lưu vào một trong các thanh ghi này chứ không phải là thanh ghi thứ ba. Tín hiệu báo tràn được lưu vào trong 1 bit cờ tràn (nếu không tràn thì bit này bằng 0, nếu tràn thì bằng 1). Đối với phép trừ, số bị trừ (thanh ghi B) được gửi đến một bộ tạo mã bù hai và gửi tiếp đến bộ cộng.Hình 1 – Sơ đồ khối phần cứng của bộ cộng và trừPhép nhân hệ hai của các số nguyên không dấu: Phép nhân trong hệ 2 được thực hiện theo quy tắc sau :Theo quy tắc trên ta thấy, phép nhân hệ hai của các số nguyên nhị phân không dấu có thể thực hiện theo thuật toán cộng và dịch như sau : - Thành phần đầu tiên của tổng tích luỹ thu được là tích của số LSB trong số nhân với số bị nhân. Nếu LSB = 0 thì thành phần này cũng bằng 0, còn nếu LSB =1 thì thành phần này chính bằng số bị nhân.- Mỗi thành phần thứ i tiếp theo của tổng tích luỹ sẽ được tính bằng cách tương tự nhưng phải dịch trái i bit ( có thể bỏ qua các thành phần bằng 0 )- Tổng của các thành phần là tích cần tìm.- Kết quả phép nhân hai số nguyên nhị phân n bit có độ dài 2n bit.Tuy nhiên, chúng ta có thể thực hiện phép nhân một cách có hiệu quả hơn. Đầu tiên, ta thực hiện cộng liên tiếp các tích từng phần cho đến khi kết thúc. Điều này sẽ làm triệt tiêu sự lưu lại của tất cả các tích thành phần, dẫn đến việc sử dụng các thanh ghi ít hơn để lưu giữ các kết quả. Mặt khác, chúng ta có thể loại ra các phân tử phát sinh của tích thành phần. Đối với bit 1 trong số nhân thì thực hiện phép cộng và một phép dịch, nhưng đối với bit 0, thì chỉ có phép dịch là được thực hiện.Hình 2 – Phần cứng thực hiện phép nhân hai số nhị phân không dấuSố nhân và số bị nhân được tải vào hai thanh ghi (Q và M), còn thanh ghi thứ ba là thanh ghi A, ban đầu nó được thiết lập ở mức 0. Thanh ghi 1 bit C được khởi đầu bằng 0 được dùng để lưu bit nhớ của phép cộng.Các bit của số nhân được đọc lần lượt một cách logic. Nếu Qo là 1 thì số bị nhân được cộng với thanh ghi A và kết quả được lưu trong thanh ghi A. Sau đó tất cả các bit của các thanh ghi C, A và Q được dịch sang phải một bit, các bit C dịch tới An-1, A0 tới Qn-1và Q0thì thôi.Nếu Q0 là 0 thì phép cộng không được thực hiện, chỉ thực hiện phép dịch. Quá trình này được thực hiện lặp lại với mỗi bit của số nhân. Kết quả của tích 2n bit được chứa trong các thanh ghi A và Q. Chú ý rằng trong chu kỳ thứ hai, khi một bit của số nhân là 0 thì phép cộng không được thực hiện.Phép nhân số bù hai:Chúng ta biết rằng phép cộng và phép trừ được số nguyên không dấu được tính như ví dụ sau:Nếu các số trên được xem như là các số nguyên bù 2, chúng ta thấy phép cộng 1001 (-710) với 0011 (310) sẽ được 1100 (-410). Từ đó ta nhận thấy rằng các phép tính đơn giản này sẽ không áp dụng được cho phép nhân. Để thấy rõ điều này ta lấy ví dụ nhân 1011 (1110) với 1101 (1310) và được 10001111 (14310). Nếu xem các số này như các số bù hai thì ta có 1011 (-510) nhân với 1101 (-310) sẽ được kết quả là 1000 1111 (-11310). Quá trình thực hiện phép nhân này theo sơ đồ khối trên hình 2 được diễn giải như sau:Ví dụ này chứng minh rõ phép nhân sẽ không thực hiện được nếu cả hai số nhân và số bị nhân là âm. Trong thực tế nó sẽ không thực hiện được nếu một trong hai số nhân hoặc số bị nhân là âm. Ta biết rằng, phép nhân một số nhị phân 2n bit được thực hiện nhờ sự dịch chuyển các số đó tới n bit bên trái. Vì lý do do này ta có thể tạo ra tích từng phần bằng cách thực hiện phép nhân theo cách khác. Tích từng phần sẽ được coi như số 2n bit được tạo ra từ số bị nhân n bit. Vì vậy, cũng như số nguyên không dấu, số bị nhân 4 bit 1011 sẽ được lưu ở trong 1 từ 8 bit là 0000 1011. Mỗi tích từng phần (khác 20) có được từ số đó đã được dịch sang trái, các bít ở vị trí bên phải sẽ được điền bằng các số 0.Hình 3 – Sơ đồ khối phép nhân hai số nhị phân không dấuGiờ đây chúng ta có thể làm sáng tỏ được rằng phép nhân sẽ không làm việc nếu số bị nhân là âm. Vấn đề là mỗi lần số bị nhân là âm thì tích từng phần phải là số âm trên vùng 2n bit. Bit dấu của tích từng phần phải sắp xếp lại. Ta chứng minh điều này dựa vào ví dụ trên bảng 1-9, biểu diễn phép nhân số 1001 (910) với 0011 (310). Nếu được coi như là số nguyên không dấu thì phép nhân 9×3=27 được thực hiện đơn giản. Tuy nhiên nếu 1001 thì được coi như là số bù hai thì giá trị của nó là -7. Sau đó mỗi tích từng phần phải được như là số bù hai âm của các bít 2n (8 bit), được biểu diễn như hình 1-9b. Chú ý rằng phép tính phải được thực hiện bằng cách kéo dài mỗi tích từng phần sang bên trái với số bit nhị phân bằng 1.Một trong số những thuật toán được sử dụng để thực hiện phép nhân các số nguyên bù hai là thuật toán Booth. Thuật toán này rất có lợi để tăng tốc độ thực hiện các phép nhân, nó có liên quan đến việc tính toán gần đúng. Thuật toán Booth được miêu tả trong hình 1-10 và được mô tả như sau : Giống như phần trên, số nhân và số bị nhân được đặt riêng rẽ trong các thanh ghi Q và M. Ở đây thanh ghi 1 bít được đặt một cách lôgic vào bên phải của bít có nghĩa nhỏ nhất của thanh ghi Q và được định nghĩa là Q-1.Kết của phép nhân sẽ xuất hiện trong các thanh ghi A và Q. A và Q được khởi tạo bằng 0. Giống như trước thì các bít của phép nhân sẽ kiểm tra một cách có hệ thống theo thời gian. Bây giờ, mỗi bít đã được kiểm tra và bít của bên phải của nó cũng được kiểm tra. Nếu hai bít giống nhau (11 hay 0 0 ) thì tất cả các bít của thanh ghi A và Q và Q1 được dịch sang bên phải 1 bít. Nếu hai bít này khác nhau thì số bị nhân được cộng hay trừ từ thanh ghi A, tuỳ theo hai bít là 01 hay 10. Khi thực hiện phép cộng hay phép trừ thì đều được dịch sang phải. Trong mỗi trường hợp, sự dịch phải là ta thực hiện dịch bít ở phía bên trái nhất của A đó là An-1, không những được dịch vào An-2 mà còn vào An-1. Đây là yêu cầu để giữ nguyên dấu của các số trong A và Q. Đây được hiểu như là phép dịch số học, từ đó sẽ giữ nguyên bit dấu.Ví dụ sau mô tả trình tự phép nhân của số 7 với 3 của thuật toán Booth.Hình 4 – Thuật toán Booth cho phép nhân số bù haiĐể rõ hơn ta mô tả phép toán trong các ví dụ sau. Ở các ví dụ này ta có thể thấy nó thực hiện phép nhân với bất kỳ các số dương và số âm. Khối của các số 1 và 0 được đưa ra ngoài, với trung bình chỉ là một phép cộng hoặc trừ cho mỗi khối. Tại sao thuật toán Both laị làm việc được ? Coi trường hợp đầu tiên của một số nhân dương trong trường hợp đặc biệt thì xem một số nhân dương gồm có một khối của 1 được bao quanh bởi 0, ví dụ 000 1110. Như ta đã biết, phép nhân có thể được thực hiện bằng cách cộng dịch dần của các số bị nhân: Số của các phép toán có thể được rút gọn đến hai nếu như chúng ta để ý: Vì vậy: Phần tích thể được tạo ra nhờ một phép cộng và một phép trừ của số bị nhân. Sơ đồ này có thể mở rộng tới bất kỳ số nào của các khối của các số 1 trong số nhân kể cả trường hợp trong đó số (đơn lẻ) 1 được xem như là một khối, thật vậy:Thuật toán Booth phù hợp với sơ đồ này bằng cách thực hiện phép trừ khi số đầu tiên của khối gặp (1-0) và thực hiện phép cộng khi ở cuối khối gặp (0-1). Để diễn giải sơ đồ khi thực hiện việc nhân số âm, chúng ta cần htực hiện theo cách sau:Cho X là một số âm trong số bù 2. Biểu diễn Khi đó giá trị của X có thể được biểu diễn như sau:Bây giờ chúng ta biết rằng bit trái nhất của X là 1, lúc đó X là số âm. Coi bit 0 bên trái nhất có vị trí Kth thì dạng của X sẽ là: Giá trị của X là: Từ công thức (1) ta có : Sắp xếp lại : Thay (5) vào công thức (4) ta có : Sau cùng, chúng ta cần quay trở lại với thuật toán của Booth. Ta nhớ lại biểu diễn của X (công thức (3)), nó có thể xoá tất cả các bit từ X0 đến bit 0 bên trái nhất được xử lý một cách thích hợp nhất, từ đó chúng đưa ra tất cả các dạng trong công thức (6) trừ (-2K+1) và đó là dạng thích hợp nhất. Như quá trình kiểm tra thuật toán ở số O bên trái nhất và khi nào gặp số kế tiếp (2k+1) thì xảy ra quá trình chuyển tiếp 1-0 và thực hiện phép trừ ở (-2K+1). Đây là số hạng còn lại trong công thức (6). Chúng ta xem xét phép nhân một vài số bị nhân với (-6). Trong cách biểu diện số bù 2, sử dụng từ 8 bít, (-6) được biểu diễn là 1111010 theo công thức (4), ta thấy rằng:Vì vậy : Sử dụng công thức (6). Ta có thể kiểm tra tính đúng dắn của kết quả Mx(-6). Sau cùng chúng ta cũng có kết quả sau: Bây giờ ta đã có thể thấy công dụng của thuật toán Booth. Nó cho phép thực hiện một phép trừ khi số 1 đầu tiên là phép đếm ngược (1-0), một phép cộng nếu số đểm là (0-1) và cuối cùng có một phép trừ khác số 1 đầu tiên của khối tiếp theo của các số 1 được đếm. Do đó thuật toán Booth thực hiện ít hơn các phép cộng và phép trừ so với các thuật toán đơn giản. Phép chia hệ hai của các số nguyên không dấu:Phép chia là một phép tính phức tạp hơn so với các phép tính khác nhưng về cơ bản thì nó vẫn được dựa trên những nguyên tắc chung. Đầu tiên là việc xây dựng thuật toán và các phép dịch các bit, phép cộng hoặc trừ. Phép chia có thể được thực hiện bằng các phép trừ và phép dịch liên tiếp cho đến khi không còn gì để trừ hoặc số bị trừ nhỏ hơn số chia.Ví dụ : 215 / 22 = 9 dư 17 . Thực hiện phép chia này trong hệ 2.Ví dụ trên được diễn giải chi tiết như sau: đầu tiên kiểm tra từng bít của số bị chia từ trái qua phải cho đến khi nào nhóm các bit đó biểu diễn một số lớn hơn hoặc bằng số chia, có nghĩa là số bị chia có thể chia được cho số chia. Nếu còn chưa chia được cho số chi thì ta thêm các số 0 vào thương số từ trái sang phải. Khi chia được cho số chia thì ta thêm 1 vào thương số và lấy số đó trừ đi số chia. Kết quả của phép trừ được gọi là số dư thành phần (partial remainder). Từ đây, phép chia lặp lại các bước như trên. Mỗi lần lặp như vậy ta bổ xung một bit từ số bị chia vào số dư thành phần cho đến khi nào nó lớn hơn số bị chia. Giống như trên, ta lại trừ đi số chia để dược một số dư thành phần mới. Quá trình cứ lặp đi lặp lại như trên cho đến khi tất cả các bit của số bị chia đã hết. Tuy nhiên, phép chia thực hiện theo cách trên rất khó khăn cho các VXL vốn chỉ gồm các phần tử để thực hiện phép cộng và dịch. Để khắc phục các khó khăn này người ta dùng thuật toán sau:- Đổi số chia ra số bù 2 của nó.- Lấy số bị chia cộng với số bù 2 của số chia ( trừ đi số chia ).Nếu kết quả này có bit dấu bằng 0 ( nghĩa là phần này của số bị chia chia được cho số chia ) thì bit tương ứng của thương bằng 1.Nếu kết quả này có bit dấu bằng 1 (nghĩa là phần này của số bị chia không chia được cho số chia ) thì bit tương ứng của thương bằng 0 và buộc phải khôi phục lại giá trị ban đầu của số bị chia bằng cách cộng kết quả với số chia ở mã hệ 2.- Dịch trái kết quả thu được ở trên và làm lại bước 2 cho đến khi nhận được kết quả là 0 ( chia hết) hoặc nhỏ hơn số chia (chia còn dư).Bây giờ ta thực hiện lại ví dụ trên theo thuật toán này.Số bị chia 215 = 0 1 1 0 1 0 1 1 1Số chia 22 = 0 1 0 1 1 0Số bù 2 của số chia = 1 0 1 0 1 0Các bước thực hiện như sau :Ta cũng có kết quả tương tự. Hình 5 là thuật toán tương ứng để thực hiện phép chia dài. Số chia được đặt trong thanh ghi M, số bị chia thì đặt trong thanh ghi Q. Ở mỗi bước, cùng một lúc thanh ghi A và Q đều được dịch trái một bit. M được trừ A để xác định là có chia phần số dư A hay không. Nếu có thì thì Q0 nhận được một bit 1, nếu không thì Q0 nhận được một bit 0 và M phải được cộng ngược trở lại A để trở lại giá trị trước. Bộ đếm sẽ giảm xuống và tiếp tục thực hiện cho đến bước thứ n. Để kết thúc thì thương số phải nằm trong thanh ghi Q và phần dư phải nằm trong thanh ghi A.Hình 5 – Lưu đồ thuật toán phép chia số nhị phân không dấuPhép chia số bù 2: Phép chia như trên có thể thực hiện được, nhưng gặp một số khó khăn khi mở rộng tới các số âm. Điều này được giải thích như một số ví dụ sau đây.Thuật toán có thể tổng quát thành một số bước như sau:1. Tải số chia vào thanh ghi M và số bị chia vào thanh ghi A, Q. Số bị chia phải nằm trong giới hạn như một số bù hai 2n bit. Vì vậy trong ví dụ này, 4 bít 0111 sẽ trở thành 0000 0111 và 1001 sẽ trở thành 1111 1001.2. Di chuyển A, Q một bit về phía trái.3. Nếu M và A cùng dấu thì thực hiện A ← A – M, ngược lại thì A ← A + M.4. Các phép toán ở trên được gọi là thành công nếu dấu của A trước và sau khi thực hiện không thay đổi.* Nếu các phép toán thành công hoặc (A = 0 AND Q = 0 ), thì thiết lập Q0 ← 1.* Nếu các phép toán không thành công và (A ≠ 0 OR Q ≠ 0), thì Q0 ← 0 và lưu lại giá trị trước đó của A.5. Lặp lại bước 2 tới bước 4 một số lần bằng số bit trong Q.6. Phần dư nằm trong thanh ghi A. Nếu số chia và số bị chia là cùng dấu, thì thương số nằm trong Q. Ngược lại, kết quả đúng là số bù hai của Q.Ta cần chú ý ở ví dụ trên, các phép chia (-7) ÷ (3) và (7) ÷ (-3) tạo ra các số dư khác nhau. Bởi vì số dư được định nghĩa như sau :D = Q*V + RTrong đó:D : Là số bị chia.Q : Là thương số.V : Là số chia.R : là số dư.Các ví dụ trên được thực hiện theo công thức này.
Không có nhận xét nào:
Đăng nhận xét