InfoNu.nl > Wetenschap > Techniek > Binair vermenigvuldigen

Binair vermenigvuldigen

Binair vermenigvuldigen Het vermenigvuldigen van twee binaire getallen is een operatie die veelvuldig wordt toegepast in de digitale techniek. Uiteindelijk is het niet de software, maar de hardware die de berekeningen uitvoert. Binaire vermenigvuldiging moet volgens bepaalde rekenregels worden uitgevoerd. De rekeneenheid die deze bewerking uitvoert, noemt men een ALU, of Arithmetic Logic Unit. Een vermenigvuldiging kan eenvoudig in hardware worden opgelost.

Getalrepresentatie's

Voor het representeren van een getal is het de standaard methode om het getal uit te drukken in machten van het grondgetal. Stel het grondgetal is g, dan:
  • getal = z (g)n + y (g)n-1 + … + d (g)3 + c (g)2 + b (g)1 + a (g)0
  • de schrijfwijze van dit getal = 'z y x … e d c b a'

De cijfers (of digits) a, b, c, … z die gebruikt mogen worden zijn allen lager dan g. In ons gebruikelijke decimale stelsel (digits lager dan 10) betekent het getal 365 het volgende:
  • 365 = 300 + 60 + 5 = 3(10)2 + 6(10)1 + 5(10)0

Binair representatie

Men gebruikt in het binaire talstelsel het getal 2 als grondgetal, het getal g moeten we dan schrijven als:
  • getal = z (2)n + y (2)n-1 + … + d(2)3 + c(2)2 + b(2)1 + a(g)0
  • alleen digits 0 en 1 mogen gebruikt worden (allen lager dan 2)
  • 365 = 256 + 64 + 32 + 8 + 4 + 1 = 1(2)8 + 0(2)7 + 1(2)6 + 1(2)5 + 0(2)4 +1(2)3 +1(2)2 + 0(2)1 + 1(2)0, dus binair genoteerd als: 1 0110 1101

Decimale vermenigvuldiging

Een vermenigvuldiging -of product- in het decimale talstelsel, kan worden opgevat als een optelsom van kleinere vermenigvuldigingen. De vermenigvuldiging van bijvoorbeeld 306 en 15 wordt uitgevoerd door eerst het getal 15 als machten van 10 te ontleden. Daarna delen we de vermenigvuldiging op in twee kleinere producten:
  • Het product van de tientallen (101)
  • Het product van de eenheden (100)
  • Vervolgens tellen we de twee deelproducten op

Wanneer de waarde van een som ≥ 10, laten we de eenheden staan en geven we het tweede digit door naar de volgende som ('carry').

306
15
---------- x
10 x 306
5 x 306
---------- +
3060
1530
---------- +
4590

Binaire vermenigvuldiging

De plaats die de waarde '0' of '1' aangeeft, noemt men een bit. Voor het product van twee bits gelden de volgende rekenregels:
  • 0 x 0 = 0
  • 0 x 1 = 0
  • 1 x 1 = 1

Ook in de binaire vermenigvuldiging wordt een product verdeeld over kleinere producten. Stel we willen twee 4 bits getallen vermenigvuldigen, het getal 5 en het getal 2. Het getal 2 als 4 bits binair getal is te ontleden als 0 x 23 + 0 x 22 +1 x 21 + 0 x 20. Het product moeten we weer schrijven als deelproducten en daarna optellen.

Het product 5 x 2 = 0101 x 0010 is dus:

0101
0010
---------------- x
0101 x 0 x 23
0101 x 0 x 22
0101 x 1 x 21
0101 x 0 x 20
---------------- +

Voor de som van twee bits gelden de volgende rekenregels:

  • 0 + 0 = 0
  • 0 + 1 = 1
  • 1 + 1 = 10 ('0' laten staan, '1' doorgeven aan de volgende som, 'carry')

Schuiven

Vermenigvuldiging met het getal 21 is hetzelfde als: alle bits een positie naar links verschuiven en helemaal rechts een '0' toevoegen. Dit wordt ook wel een 'Logic Shift Left' (LSL) genoemd.

Dit levert op voor 0101 x 0010:

0101 x 0 x 23
0101 x 0 x 22
0101 x 1 x 21 = LSL(1)
0101 x 0 x 20
---------------- +
0000
0000
1010
0000
------------ +
1010 (decimaal '5 x 2 =10')

Omdat 4 = 22, komt vermenigvuldigen met het getal 4 neer op een verschuiving naar links van 2 positie's (LSL2), en vermenigvuldigen met 8 = 23 op een verschuiving van 3 positie's (LSL3).

Zo zal het product 13 x 5 = 65, binair te schrijven zijn als:

1101
0101
------------ x
000 1101 -- (getal x 1)
000 0000 -- LSL1 (getal x 0)
011 0100 -- LSL2 (getal x 1)
000 0000 -- LSL3 (getal x 0)
----------- +
100 0001 (decimaal '13 x 5 = 65')

Hardware

De binaire vermenigvuldiging wordt in hardware uitgevoerd door logische circuits (Arithmetic Logic Unit of ALU). Zo'n circuit heeft 2 input-signalen van een zekere bitbreedte, en een output-signaal (Y = A * B). Uit bovenstaande berekeningen is af te leiden dat een vermenigvuldiger in principe twee operaties uitvoert:
-fig 1- 3 bits-vermeningvuldiging-fig 1- 3 bits-vermeningvuldiging
  • Verschuiven
  • Optellen

In figuur 1 zijn de bewerkingstappen voor een 3 bits-vermenigvuldiging afgebeeld. Stel we willen de vermeningvuldiging y(5:0) = a(2:0) * b(2:0) uitvoeren.

De eerste stap die moet worden uitgevoerd is de 'bitwise-AND' (&&): elk afzonderlijk bit in a(2:0) voert een logische AND uit met bit b0. Is bit b0 0 dan wordt het getal 000 opgeteld bij de volgende trap, is bit b0 1 dan wordt het getal a(2:0) opgeteld bij de volgende trap. De volgende trap voert een bitwise-AND op b1 en a(2:0) uit, voegt een '0' toe aan a(2:0), en telt vervolgens het getal (a(2:0), '0') op bij de vorige trap. In laatste de trap wordt dit tussenresultaat opgeteld bij het getal (b(1) && a(2:0), '00').

-fig 2- Hardware 3 bits vermenigvuldiger-fig 2- Hardware 3 bits vermenigvuldiger
De hardware voor de 3 bits vermenigvuldiger is in figuur 2 afgebeeld (klik voor vergroting). In dit voorbeeld zijn 9 2-input AND poorten en 9 full-adders gebruikt.

Meestal wordt een vermeningvuldiger in hardware ontworpen door gebruik te maken van een Hardware Description Language (HDL). In zo'n hardware beschrijvingstaal kan eenvoudig het gedrag van een vermeningvuldiger worden beschreven. Vervolgens kan men een aantal randvoorwaarden opgeven (zoals de gewenste snelheid, het te gebruiken oppervlak in silicium, de te gebruiken poorten etc.) en de computer het meest optimale circuit laten berekenen. Deze methode van ontwerpen wordt ook wel synthese genoemd.
© 2018 Tronic, het auteursrecht (tenzij anders vermeld) van dit artikel ligt bij de infoteur. Zonder toestemming van de infoteur is vermenigvuldiging verboden.
Gerelateerde artikelen
Binaire, octale en hexadecimale getallenstelselsBinaire, octale en hexadecimale getallenstelselsIn het gewone leven gebruiken wij het decimale stelsel voor de getallen. Een voor ons ‘gewoon’ getal bestaat uit cijfers…
Wat is binair: Over bits, bytes, nullen en enenWat is binair: Over bits, bytes, nullen en enenWe hebben allemaal gehoord over de bits en bytes waar een computer mee werkt. En dat een computer eigenlijk alleen nulle…
Hoe werken computers?Hoe werken computers?Computers zijn niet weg te denken uit onze huidige maatschappij. Toch is er maar een selecte hoeveelheid mensen die wete…
Computeronderdeel: De processorComputeronderdeel: De processorDe Processor is net zoals het moederbord één van de belangrijkste onderdelen van een computer. In dit klein stukje elekt…
Van analoog naar digitaalBijna alle machines werken met signalen. Een binair signaal of een digitaal signaal, maar hoe weet een machine nu wannee…
Bronnen en referenties
  • CMOS VLSI design, third edition, Weste/Harris

Reageer op het artikel "Binair vermenigvuldigen"

Plaats als eerste een reactie, vraag of opmerking bij dit artikel. Reacties moeten voldoen aan de huisregels van InfoNu.
Meld mij aan voor de tweewekelijkse InfoNu nieuwsbrief
Ik ga akkoord met de privacyverklaring en ben bekend met de inhoud hiervan
Infoteur: Tronic
Gepubliceerd: 07-12-2018
Rubriek: Wetenschap
Subrubriek: Techniek
Bronnen en referenties: 1
Schrijf mee!