Binaire overloop

Een waarschuwing met ondertekende binaire getallen is die van overloop, waarbij het antwoord op een optellen of aftrekken groter is dan de grootte die kan worden weergegeven met het toegewezen aantal bits. Onthoud dat de plaats van het tekenbit vanaf het begin van het probleem vastligt.

Bij het laatste voorbeeldprobleem gebruikten we vijf binaire bits om de grootte van het getal weer te geven, en het meest linkse (zesde) bit als het negatieve gewicht, of teken, bit. Met vijf bits om de grootte weer te geven, hebben we een weergavebereik van 2 ⁵ , of tweeëndertig gehele stappen van 0 tot maximum.

Dit betekent dat we een getal tot +31₁₀ . kunnen vertegenwoordigen (011111₂ ), of zo laag als -32₁₀ (100000₂ ).

Beperkingen van het zes-bit-nummerveld

Als we een optellingsprobleem instellen met twee binaire getallen, de zesde bit die wordt gebruikt voor teken, en het resultaat is ofwel groter dan +31₁₀ of kleiner is dan -32₁₀ , zal ons antwoord onjuist zijn. Laten we proberen 17₁₀ toe te voegen en 19₁₀ om te zien hoe deze overloopconditie werkt voor buitensporige positieve getallen:

Het antwoord (100100₂ ), geïnterpreteerd met het zesde bit als de -32₁₀ plaats, is eigenlijk gelijk aan -28₁₀ , niet +36₁₀ zoals we zouden moeten krijgen met +17₁₀ en +19₁₀ opgeteld! Het is duidelijk dat dit niet correct is. Wat ging er mis?

Het antwoord ligt in de beperkingen van het zes-bits getalveld waarbinnen we werken. Sinds de grootte van de ware en juiste som (36₁₀ ) de toegestane limiet voor ons aangewezen bitveld overschrijdt, hebben we een overloopfout .

Simpel gezegd, zes plaatsen geven niet genoeg bits om de juiste som weer te geven, dus welk getal we ook verkrijgen met de strategie om het meest linkse 'carry'-bit weg te gooien, is onjuist.

Een soortgelijke fout zal optreden als we twee negatieve getallen bij elkaar optellen om een ​​som te produceren die te laag is voor ons zes-bits binaire veld. Laten we proberen -17₁₀ . toe te voegen en -19₁₀ samen om te zien hoe dit werkt (of niet werkt, al naar gelang het geval!):

Het (onjuiste) antwoord is positief achtentwintig. Het feit dat de werkelijke som van min zeventien en min negentien te laag was om goed te worden weergegeven met een veld met een magnitude van vijf bits en een bit met een zesde teken, is de hoofdoorzaak van deze moeilijkheid.

Het zevende bit gebruiken voor een tekenbit

Laten we deze twee problemen opnieuw proberen, maar deze keer gebruiken we de zevende bit voor een tekenbit, en laten we het gebruik van 6 bits toe om de grootte weer te geven:

Door bitvelden te gebruiken die voldoende groot zijn om de grootte van de sommen aan te kunnen, komen we tot de juiste antwoorden. In deze voorbeeldproblemen hebben we overloopfouten kunnen detecteren door de optelproblemen in decimale vorm uit te voeren en de resultaten te vergelijken met de binaire antwoorden.

Bijvoorbeeld bij het toevoegen van +17₁₀ en +19₁₀ samen wisten we dat het antwoord was verondersteld om +36₁₀ . te zijn , dus toen de binaire som uitcheckte als -28₁₀ , wisten we dat er iets mis moest zijn. Hoewel dit een geldige manier is om overflow te detecteren, is het niet erg efficiënt.

Het hele idee van complementatie is immers om op betrouwbare wijze binaire getallen bij elkaar te kunnen optellen en het resultaat niet dubbel te hoeven controleren door dezelfde getallen in decimale vorm bij elkaar op te tellen! Dit geldt met name voor het bouwen van elektronische schakelingen om binaire grootheden bij elkaar op te tellen:de schakeling moet zichzelf kunnen controleren op overloop zonder toezicht van een mens die al weet wat het juiste antwoord is.

Wat we nodig hebben, is een eenvoudige foutdetectiemethode die geen extra rekenkunde vereist. Misschien is de meest elegante oplossing om te controleren op het teken van de som en vergelijk deze met de tekens van de toegevoegde getallen.

Het is duidelijk dat twee positieve getallen bij elkaar opgeteld een positief resultaat moeten geven, en twee negatieve getallen bij elkaar opgeteld een negatief resultaat. Merk op dat wanneer we een toestand van overloop hadden in de voorbeeldproblemen, het teken van de som altijd tegengesteld was van de twee toegevoegde nummers:+17₁₀ plus +19₁₀ geven -28₁₀ , of -17₁₀ plus -19₁₀ geven van +28₁₀ .

Door alleen de borden te controleren, kunnen we zien dat er iets mis is. Maar hoe zit het met gevallen waarin een positief getal wordt toegevoegd aan een negatief getal? Welk teken moet de som zijn om correct te zijn. Of, meer precies, welk teken van de som zou noodzakelijkerwijs wijzen op een overloopfout?

Het antwoord hierop is even elegant:er zal nooit een overloopfout zijn wanneer twee getallen van tegengestelde tekens bij elkaar worden opgeteld! De reden hiervoor wordt duidelijk wanneer de aard van de overloop in aanmerking wordt genomen. Overloop treedt op wanneer de grootte van een getal het bereik overschrijdt dat is toegestaan ​​door de grootte van het bitveld.

De som van twee identiek ondertekende getallen kan heel goed het bereik van het bitveld van die twee getallen overschrijden, en dus is in dit geval overloop een mogelijkheid. Als een positief getal echter wordt opgeteld bij een negatief getal, zal de som altijd dichter bij nul liggen dan een van de twee toegevoegde getallen:de grootte ervan moet kleiner zijn dan de grootte van een van beide oorspronkelijke getallen, en dus is overlopen onmogelijk.

Gelukkig is deze techniek van overloopdetectie gemakkelijk te implementeren in elektronische schakelingen, en het is een standaardkenmerk in digitale optelschakelingen:een onderwerp voor een later hoofdstuk.

GERELATEERDE WERKBLAD:

• Werkblad binaire wiskunde