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. De rekeneenheid die deze bewerking uitvoert, noemt men een ALU, of Arithmetic Logic Unit. Dit artikel legt uit hoe zo'n vermenigvuldiging in zijn werk gaat, en hoe dergelijke sommetjes in hardware worden opgelost.

Vermenigvuldigen

Een vermenigvuldiging (of product) in ons gebruikelijke talstelsel, het decimale talstelsel, kan worden opgevat als een optelsom van kleinere vermenigvuldigingen. Men dient eerst te beseffen dat alle getallen als machten van 10 te schrijven zijn:
356 = 3 x 10² + 5 x 10¹ + 6 x 10°
15 = 1 x 10¹ + 5 x 10°
De vermenigvuldiging van deze twee getallen komt neer op:

356
15
---------- x
10 x 356
5 x 356
---------- +
3560
1780
---------- +
5340

Door het getal 15 als machten van 10 te schrijven, delen we de vermenigvuldiging op in twee kleinere producten: het product van de tientallen (10¹) en het product van de eenheden (10°). Daarna tellen we de twee deelproducten op. Speciale aandacht vereist de som die boven de 10 uitkomt. In dat geval laten we de eenheden staan, en geven we een '1' door naar de volgende som. In het bovenstaande voorbeeld geldt bijvoorbeeld dat 6+8=14, dus '4' laten staan, en '1' doorgeven aan 5+7, levert 5+7+1=13. Deze '3' laten we weer staan, en de '1' geven we opniuew door.

Binair

Een binaire talstelsel heeft het getal 2 als grondtal. Dit betekent dat getallen als machten van het getal 2 worden geschreven. De representatie van het getal 13 wordt bijvoorbeeld:
13 = 1 x 8 + 1 x 4 + 0 x 2 + 1 x 1 = 1 x 2³ + 1 x 2² + 0 x 2¹ + 1 x 2° = 1101

De plaats die de waarde '0' of '1' aangeeft, noemt men een bit. Ook in de binaire vermenigvuldiging wordt een product verdeeld over kleinere producten. Voor het product van twee bits gelden de volgende rekenregels:
0 x 0 = 0
0 x 1 = 0
1 x 1 = 1

Een vermenigvuldiging met het getal 2 komt neer op het vermenigvuldigen met '10'. Verdelen levert: een product met 1x2¹ en een product met 0 x 2°. Het product 5 x 2 = 0101 x 0010 is dus:
0101
0010
---------------- x
0101 x 1 x 2¹
0101 x 0 x 2°

De vermenigvuldiging met het getal 2¹ is hetzelfde als: alle bits een positie naar links verschuiven en helemaal rechts een '0' toevoegen.

Dit levert op:
0101 x 1 x 2¹
0101 x 0 x 2°
---------------- +
1010
0000
------------ +
1010

Omdat 4 = 2², komt vermenigvuldigen met het getal 4 neer op een verschuiving naar links van 2 positie's, en vermenigvuldigen met 8 (= 2³) op een verschuiving van 3 positie's. Dit principe kan worden gebruikt voor alle getallen (die allemaal als machten van 2 te schrijven zijn). Zo zal het product 5 x 15 =75, binair hetzelfde zijn als:

0101
1111
------------ x
0000101
0001010
0010100
0101000
----------- +
1001011

Hardware

De binaire vermenigvuldiging wordt in hardware uitgevoerd door logische circuits. Zo'n circuit heeft 2 input-signalen van een zekere bitbreedte, en een output-signaal. Een vermenigvuldiger (Arithmetic Logic Unit of ALU) voert dus in principe twee operaties uit:

• Verschuiven
• Optellen

Daarnaast kan een ALU meestal nog andere logische operaties op bits en bitvectoren uitvoeren. De eenheden die verschuiven en optellen bestaan uit een configuratie van logische poorten zoals AND, NAND, OR, NOR, and XOR. Dit zijn standaard componenten die de logische operatie's op de nullen en enen uitvoeren. Op de afbeelding is de -sterk vergrote- layout van een chip te zien, met daarop een 8 bit-ALU. Het paarse gedeelte is de plaats waar alle logische poorten liggen. De kleine vierkantjes aan de randen zijn de connecties van de chip met de buitenwereld. Men noemt ze ook wel pads. Door (bijvoorbeeld) een gouden draad erop te solderen, kan men een verbinding maken met de pootjes van een chip, de zogenaamde pins. Dit proces wordt ook wel bonding genoemd.

Lees verder

• Binaire coderingen
• De werking van de Flip-Flop
• Logische poorten, de XOR
• Binair en hexadecimaal rekenen