System binarny

System dwójkowy (z łac. binār , us , „podwójny”) to system liczbowy o podstawie 2 . Cyfry pozycyjnej liczby binarnej są powszechnie nazywane bit (od angielskiego binarnej cyfry lub „cyfra binarna”) . Bit może przyjmować dwie wartości, oznaczone konwencją 0 i 1 .

System binarny jest przydatny do reprezentowania działania elektroniki cyfrowej stosowanej w komputerach . Dlatego jest używany przez języki programowania niskiego poziomu .

Definicja

Najpopularniejszym systemem dwójkowym jest matematyczna podstawa numer dwa , pozwalająca na reprezentowanie liczb za pomocą numeracji miejsc z użyciem tylko dwóch cyfr: 0 i 1.

W tego typu kodowaniu każda liczba jest reprezentowana jednoznacznie przez uporządkowany ciąg cyfr . A każda pozycja m reprezentuje potęgę ( m -1) podstawy . Jeśli ograniczymy się początkowo do dodatnich liczb całkowitych , w bazie dziesiątej te potęgi to: jeden (1), dziesięć (reprezentowane przez 10), sto (dziesięć razy dziesięć, reprezentowane przez 100), tysiąc (dziesięć razy sto , reprezentowane przez 1000), dziesięć tysięcy itd. W systemie o podstawie 2 są to: jedna (1), dwie (również reprezentowane przez 10), cztery (dwa razy dwa, reprezentowane przez 100), osiem (dwa razy cztery, reprezentowane przez 1000), szesnaście (dwa razy osiem, reprezentowane przez do 10000 itd.

Widzimy, że znaczenie reprezentacji 10, 100, 1000 itd. zależy od zastosowanej podstawy: 10 jest zawsze równe podstawie, to znaczy dziesięć w podstawie dziesięć, ale dwa w podstawie dwa.

W bazie dziesiątej używa się dziesięciu cyfr, od zera do dziewięciu; w bazie n używamy n cyfr, od zera do n -1; dlatego w podstawie drugiej używamy dwóch cyfr „0” i „1”.

Liczbę wyrażoną w bazie B za pomocą czterech cyfr 1101 można analizować:

, co daje :

1101 w bazie B = 10:
1101 w bazie B = 8:
1101 w bazie B = 2:

Wyliczanie liczb pierwszych

Pierwsze liczby i cyfry o podstawie 10 są zapisywane:

dziesiętny dwójkowy Uwaga
0 0 zero
1 1 un = podstawowa potęga zero (ważna dla wszystkich podstaw, czyli dwóch i dziesięciu)
2 10 dwa = dwa do potęgi jeden (zero za 1)
3 11
4 100 cztery = dwa do potęgi dwójki (dwa zera za 1)
5 101
6 110
7 111
8 1000 osiem = dwa do potęgi trzeciej (trzy zera za 1)
9 1001

Każdemu bitowi nadajemy potęgę dwójki, tak jak ta sekwencja 1, 2, 4, 8, 16, 32, 64. Aby otrzymać liczbę 7, dodajemy pierwsze trzy bity; aby otrzymać 6, dodajemy tylko bit o wadze 4 i bit o wadze 2.

Operacje

Techniki czterech podstawowych operacji (dodawanie, odejmowanie, mnożenie i dzielenie) pozostają dokładnie takie same jak w zapisie dziesiętnym; są po prostu drastycznie uproszczone, ponieważ są tylko dwie cyfry 0 i 1. Na przykład dla mnożenia, niezależnie od podstawy, mnożenie przez 10 (tj. przez samą podstawę) jest wykonywane przez dodanie zera po prawej stronie.

Jedyne zmiany, które zmieniają z jednej strony postać ciągu cyfr wyrażającego wynik (zlicza on tylko zera i jeden), z drugiej strony znaczenie tego ciągu (10 oznacza „dwa”, a nie „dziesięć”, 100 oznacza „cztery”, a nie „sto” itd.).

Dodawanie i odejmowanie

Przechodzimy od jednej liczby binarnej do drugiej, dodając 1, jak w systemie dziesiętnym, nie zapominając o blokadach i używając zwykłej tabeli (ale zredukowanej do najprostszego wyrażenia):

0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0 avec 1 retenue 0 - 0 = 0 0 - 1 = 1 avec 1 retenue 1 - 0 = 1 1 - 1 = 0

Można zauważyć, że dodanie dwóch bitów A i B daje A XOR B z przeniesieniem równym A AND B.

Więc :

11 + 1 ____ 100

Szczegół :

1 + 1 = 10 => on pose 0 et on retient 1 1 + 1(retenue) = 10 => on pose 0 et on retient 1 0 + 1(retenue) = 1 => on pose 1 devant 00


Mnożenie i dzielenie

Mnożenie przez dwa odbywa się poprzez przesunięcie każdej cyfry o jeden krok w lewo i wstawienie zera na końcu.
Na przykład dwa razy jedenaście:

1011 onze //// décalage et insertion de 0 10110 vingt-deux

Cały podział przez dwa odbywa się poprzez przesunięcie każdej cyfry o jeden krok w prawo, przy czym prawa cyfra jest usuwana.
Na przykład jedenaście podzielone przez dwa:

1011 onze \\\ décalage et suppression du chiffre à droite 101 cinq reste un

Teoria komputerowa

Arytmetyka binarna (prościej obliczenia binarne) jest używana przez najpowszechniejsze systemy elektroniczne (kalkulatory, komputery itp.), ponieważ dwie cyfry 0 i 1 są tam odzwierciedlone przez napięcie lub przepływ prądu. Na przykład 0 może być reprezentowane przez stan niski (napięcie lub prąd zerowy), a 1 przez stan wysoki (istniejące napięcie, płynący prąd).

Reprezentacja ujemnych liczb całkowitych

Aby uzupełnić reprezentację liczb całkowitych, trzeba umieć pisać liczby całkowite ujemne . Istnieją dwie reprezentacje, dopełnienie jedynki i dopełnienie dwóch.

Uzupełnienie do

To kodowanie polega na odwróceniu wartości każdego bitu.
Na przykład, aby uzyskać -7:

0111 sept 1000 moins sept

Wadą tego systemu jest to, że zero ma dwie reprezentacje: 0000 i 1111 ("+0" i "-0"). Nie jest używany przez obecne komputery, ale był używany przez starsze komputery, takie jak Control Data 6600 . Dwie reprezentacje zera komplikują obwody testowe.

Uzupełnienie dla dwojga

Uzupełnienie do dwójki polega na wykonaniu uzupełnienia do jedynki, a następnie dodaniu 1.
Na przykład, aby uzyskać -7:

0111 sept 1000 complément à un 1001 complément à deux en ajoutant 1

To kodowanie ma tę zaletę, że nie wymaga specjalnego różnicowania liczb dodatnich i ujemnych, a w szczególności pozwala uniknąć problemu podwójnej reprezentacji zera.

Oto dodanie -7 i +9 wykonywane jako 4-bitowe uzupełnienie dwójkowe:

-7 1001 +9 1001 __ ____ 2 (1) 0010 (on « ignore » la retenue)

Z n bitami, ten system pozwala reprezentować liczby od -2 n -1 do 2 n -1 - 1.

Pomiędzy podstawami 2, 8 i 16

Od binarnego do ósemkowego lub szesnastkowego

Podstawy 8 (ósemkowe) i 16 (szesnastkowe) są podstawami potęgowymi o podstawie 2. Te dwie podstawy są powszechnie używane w przetwarzaniu danych i ze względów praktycznych; te zasady są silnie powiązane z podstawą 2, a liczby zapisane w tych podstawach są bardziej "manipulowalne" (z powodu krótszego zapisu) przez ludzki intelekt. Zapisywanie liczb w tych podstawach można łatwo osiągnąć, grupując cyfry od wpisywania liczby do podstawy 2.

  • Ósemkowy: podstawa 8 = 2 3 . Wystarczy przejrzeć liczbę binarną od prawej do lewej, grupując cyfry binarne 3 na 3: każda paczka 3 (ostatnia musi być czasem uzupełniona o 0 po lewej stronie) to binarne zapisanie liczby o podstawie 8 (0 8 = 000, 1 : 8 = 001, 2 8 = 010, 3 8 = 011 4 8 = 100, 5 8 = 101, 6 8 = 110, 7 8 = 111).
    • 10101101110 2 zapiszemy jako 10 101 101 110 i przeliczając wartość każdego z bloków na liczbę ósemkową otrzymamy liczbę ósemkową 2556 8 .
  • Szesnastkowy: podstawa 16 = 2 4 . Wystarczy przejrzeć liczbę binarną od prawej do lewej, grupując cyfry binarne 4 na 4: każdy pakiet 4 bitów jest binarną reprezentacją cyfry o podstawie 16. W podstawie 16 wymagane jest 16 symboli i konwencjonalnie używamy 10 cyfr dziesiętnych, po których następuje 6 pierwszych znaków alfabetu zgodnie z następującą zasadą: A 16 = 10 10 = 1010 2 , B 16 = 11 10 = 1011 2 , C 16 = 12 10 = 1100 2 , D 16 = 13 10 = 1101 2 , E 16 = 14 10 = 1110 2 i F 16 = 15 10 = 1111 2 .
    • 10101101110 2 zostanie zapisane 101 0110 1110 i przeliczając wartość każdego z bloków na dziesiętną otrzymamy: 5, 6, 14 czyli 56E 16 .

Moglibyśmy łatwo rozszerzyć tę zasadę na wszystkie podstawy, które są potęgami 2.

Do binarnego

Wystarczy przeliczyć wartość każdej z cyfr w postaci binarnej przy użyciu liczby cyfr odpowiadającej potędze podstawy: 16 = 2 4 , 8 = 2 3 , a więc 4 cyfry dla szesnastkowej i 3 dla ósemkowej:

  • 1A2F 16 zostanie zapisane 1 0001, A ⇒ 1010, 2 ⇒ 0010, F ⇒ 1111, lub 0001 1010 0010 1111 2 .
  • 156 8 zostanie zapisane jako 1 ⇒ 001, 5 ⇒ 101, 6 ⇒ 110 lub 001 101 110 2 .

Tabela wartości zgrupowań cyfr binarnych

Dwójkowy Dziesiętny ósemkowy Szesnastkowy
0000 0 0 0
0001 1 1 1
0010 2 2 2
0011 3 3 3
0100 4 4 4
0101 5 5 5
0110 6 6 6
0111 7 7 7
Dwójkowy Dziesiętny ósemkowy Szesnastkowy
1000 8 10 8
1001 9 11 9
1010 10 12 DO
1011 11 13 b
1100 12 14 VS
1101 13 15 D
1110 14 16 mi
1111 15 17 F

Szary kod lub odbity kod binarny

Kod Graya, zwany także binarnym odbitym, pozwala na zmianę tylko jednego bitu w czasie, gdy liczba jest zwiększana lub zmniejszana o jeden. Nazwa kodu pochodzi od amerykańskiego inżyniera Franka Graya , który w 1947 roku zgłosił patent na ten kod.

Aby bezpośrednio obliczyć kod Graya liczby całkowitej z jej poprzednika, możemy postępować w następujący sposób:

  • gdy jest parzysta liczba 1, ostatni bit jest odwracany;
  • jeśli jest nieparzysta liczba 1, odwróć bit bezpośrednio na lewo od 1 najbardziej na prawo.

dziesiętny kodowany binarnie (DCB lub BCD dla dziesiętnego kodowanego binarnie )

Aby pogodzić logikę binarną komputera z logiką człowieka, można przekształcić na binarne, a nie same liczby, każdą z cyfr, które tworzą je w dziesiętnym zapisie pozycyjnym. Każda z tych cyfr jest następnie kodowana na 4 bitach:

1994 = 0001 1001 1001 0100 1×1000 + 9×100 + 9×10 + 4×1

Przy n bitach (n wielokrotność 4), możliwe jest przedstawienie liczb od 0 do 10 n/4 -1. To znaczy w przybliżeniu między 0 a 1,778 n -1. DCB jest kodem nadmiarowym, w rzeczywistości niektóre kombinacje nie są używane (np. 1111).

Ta reprezentacja pozwala uniknąć przez konstrukcję wszystkich kłopotliwych problemów z akumulacją zaokrągleń, które występowałyby podczas manipulowania dużymi liczbami przekraczającymi rozmiar obwodów w arytmetyce liczb całkowitych i zmuszały do ​​uciekania się do zmienności zmiennoprzecinkowej. Można jednak manipulować liczbami z dowolną precyzją , używając kodowania wydajniejszego niż DCB.

Istnieją warianty kodowania DCB:

  • kod Aikena, gdzie 0, 1, 2, 3, 4 są kodowane jak w DCB, a 5, 6, 7, 8, 9 są kodowane od 1011 do 1111; ten kod umożliwia uzyskanie uzupełnienia do 9 przez permutację jedynek i zer;
  • kodowanie binarne powyżej 3, które polega na przedstawieniu cyfry do zakodowania + 3.

Aplikacje

Teoria informacji

W informacji teorii The entropia z źródło informacji jest wyrażona w bitach . Sama teoria jest obojętna na reprezentację wykorzystywanych przez nią wielkości.

Logika

Klasycznej logiki jest logika dwuwartościowy: propozycja jest albo prawdziwe, albo fałszywe. Możliwe jest zatem przedstawienie prawdziwości zdania za pomocą liczby binarnej. Na przykład możemy modelować działania arytmetyki binarnej za pomocą algebry Boole'a .

Algebra Boole'a reprezentuje bardzo szczególny przypadek użycia prawdopodobieństw obejmujących tylko wartości prawdy 0 i 1. Zobacz twierdzenie Coxa-Jaynesa .

Informatyka

Binarny jest używany w przetwarzaniu danych, ponieważ umożliwia modelowanie działania elementów przełączających , takich jak TTL lub CMOS . Obecność progu napięcia na tranzystorach, pomijając dokładną wartość tego napięcia, będzie reprezentować 0 lub 1. Na przykład liczba 0 będzie używana do oznaczenia braku napięcia z dokładnością do 0,5  V , a liczba 1 do wskazania jego obecność powyżej 0,5  V . Ten margines tolerancji umożliwia zepchnięcie szybkości mikroprocesorów do wartości sięgających kilku gigaherców .

W informatyce reprezentacja binarna umożliwia wyraźne manipulowanie bitami  : każda cyfra binarna odpowiada bitowi. Ponieważ jednak reprezentacja binarna wymaga użycia wielu cyfr (nawet w przypadku dość małych liczb), prowadzi to do znacznych problemów z czytelnością , a tym samym do ryzyka błędów transkrypcji dla programistów. Dlatego też preferowane są inne reprezentacje  : notacja szesnastkowa, która umożliwia manipulowanie informacjami w pakietach 4 bitowych, jest odpowiednia dla prawie wszystkich obecnych mikroprocesorów pracujących ze słowami 8, 16, 32 lub 64 bitowymi; rzadszy, punktowany ósemkowy , popularny czas pierwszych minikomputerów DEC do 12 lub 36 bitów, które mogą reprezentować informacje w paczkach po 3 bity.

  • 63 (10) = 111 111 (2) = 77 (8) = 3F (16)
  • 64 (10) = 1000000 (2) = 100 (8) = 40 (16)
  • 255 (10) = 11111111 (2) = 377 (8) = FF (16)
  • 256 (10) = 100 000 000 (2) = 400 (8) = 100 (16)

Fabuła

  • Chińskie heksagramy, później uznane za pierwsze wyrażenie liczby binarnej, pojawiły się w Yi Jing około 750 rpne ( okres zachodniego Zhou ), ale ich matematyczne znaczenie, jeśli było znane, zostało później zapomniane.
  • Indyjskiemu matematykowi Pingali przypisuje się tablicę przedstawiającą cyfry od 0 do 7 w numeracji binarnej, w jego Chandah-śāstra prawdopodobnie pochodzącym z III lub II wieku p.n.e.
  • Około 1600 r. angielski matematyk Thomas Harriot prowadził operacje na numeracji binarnej, o czym świadczą jego rękopisy opublikowane dopiero niedawno.
  • W tym samym czasie Francis Bacon użył dwuliterowego tajnego kodu (dwuliterowego) do ochrony swoich wiadomości (zastąpił litery wiadomości ich pozycją binarną, a następnie 0 i 1 przez A i B. Przykład: litera E → 5 → 00101 → kodowany AABAB.
  • John Napier , szkocki matematyk, wynalazca logarytmów, w swoim traktacie Rhabdology opublikowanym w 1617 roku opisuje trzy systemy ułatwiające obliczenia, z których jeden, zwany szachownicą , jest binarny.
  • Hiszpański Caramuel w swojej książce Mathesis biceps vetus et nova, opublikowanej w 1670 r., wydaje się pierwszym, który przedstawił zwięzłe badanie numeracji niedziesiętnej, w tym dwójkowej.
  • U Leibniza wrócił ze studiowania samego systemu binarnego, pokazał, jak ćwicząc cztery operacje („tak proste, że nigdy niczego nie potrzebowaliśmy ani nie próbujmy zgadywać, jak należy w zwykłym dzieleniu”), zauważył, że to wyliczenie” jest jak najbardziej fundamentalne dla nauki i daje nowe odkrycia”, a nawet przewidywało, że” tego typu obliczenia można by również przeprowadzić za pomocą maszyny (bez kół), w następujący sposób z pewnością bardzo łatwo i bez wysiłku. Z pudełkiem z otworami, które można otwierać i zamykać. „
    Ponadto, po zakomunikowaniu” RP Bouvetowi , słynnemu francuskiemu jezuicie, który mieszka w Pekinie, (jego) sposób liczenia od 0 do 1, nic więcej nie było potrzebne, aby rozpoznał, że jest to klucz do liczb. de Fohy ”, w 1601. W ten sposób rozszyfrowano zagadkę heksagramów przypisywanych Fuxi , a Leibniz miał wówczas swoją ekspozycję systemu binarnego opublikowaną przez Akademię Nauk w Paryżu w 1703 roku.
  • W 1847 roku George Boole opublikował pierwsze prace swojej algebry binarnej, zwanej Boolean , przyjmującej tylko dwie wartości liczbowe: 0 i 1.
  • 1872: publikacja aplikacji systemu binarnego do rozwiązania problemu baguenodier ( Luc-Agathon-Louis Gros , Théorie du baguenodier par un clerc de notaire lyonnais , Lyon, Aimé Vingtrinier ,1872( przeczytaj online ))
  • 1876: L.-V. Mimault zgłasza patent 3011 dotyczący:
    • wiele systemów telegraficznych, drukarek i pisarzy opartych na kombinacjach mechanicznych lub graficznych z „( X + 1) moc m  ”;
    • wiele systemów telegraficznych, drukujących i piszących opartych na kombinacjach progresji 1:2:4:8:16.

Uwagi i referencje

  1. Uwaga: 10, a nie dziesięć  ; w bazie dwa, 10 to dwa .
  2. (w) Frank Grey dla Bell Labs , patent USA 2 632 058: Pulse Code Communication , złożony 13 listopada 1947, opublikowany 17 marca 1953 Google Patents.
  3. (w) EL Shaughnessy, „I Ching (Chou I)”, w M. Loewe, (red.) Early Chinese Texts: A Bibliographical Guide , Berkeley, 1993, s. 216-228.
  4. Świadectwo Ojca Bouveta przekazane przez Leibniza ( na Wikiźródłach ).
  5. (w) Kim Plofker , Matematyka w Indiach , Princeton (NJ), Princeton University Press ,2009, 357  s. ( ISBN  978-0-691-12067-6 , czytaj online ) , rozdz.  3 („Ślady matematyczne we wczesnym okresie klasycznym”) , s.  55-57.
  6. (w) B. Van Nooten , „  Liczby binarne w starożytności Indii  ” , Journal of Indian Philosophy , tom.  21, n o  1,Marzec 1993, s.  31-50 ( ISSN  0022-1791 , DOI  10.1007 / BF01092744 ).
  7. Elektroniczne wydanie rękopisów Thomasa Harriota (1560-1621)  ; faks online .
  8. (w) szyfr Bacona .
  9. (w) John Napier, Rabdologić , przekład z łaciny przez Williama Franka Richardsona, „Wprowadzenie Robin E. Rider 1990, MIT Press (isbn 0-262-14046-2).
  10. Robert Ineichen, Leibniz, Caramuel, Harriot und das Dualsystem , Mitteilungen der deutschen Mathematiker-Vereinigung, tom. 16, 2008, nr 1, s. 14.
  11. Leibniz, Wyjaśnienie arytmetyki binarnej, która używa tylko znaków 0 i 1, z uwagami na temat jej użyteczności i tego, co nadaje znaczenie starożytnym chińskim figurom Fohy ( czytaj na Wikiźródłach i na Mémoires de l'Académie des sciences de Paris, 1703, s.  85-89 ).
  12. In progressione dyadica , rękopis z 1679 r., przekład Yves Serra, s. 5 ( czytaj online ); patrz także Yves Serra, Le rękopis „De Progressione Dyadica” Leibniza ( czytany online na Bibnum ).
  13. Opis uwag zawartych w patencie pod okładką.

Zobacz również

Powiązane artykuły

Linki zewnętrzne