Fouten verbeterende codes( deel 2)

In een vorig artikel bespraken we Hamming-codes. De Hamming (7,4) code codeert een 4-bits boodschap p_1p_2p_3p_4 naar een 7-bits codewoord p_1p_2p_3p_4p_5p_6p_7, door drie even pariteitsbits toe te voegen:

    \[p_5=p_1+p_2+p_4\]

    \[p_6=p_1+p_3+p_4\]

    \[p_7=p_2+p_3+p_4\]

De vergelijkingen dienen modulo 2 bekeken te worden.

Dit zijn de 16 mogelijke codewoorden. Om 0100 te zenden, stuur je het codewoord 0100101 door. Als er 1 transmissiefout op zit en je ontvangt 0101101, dan kan de ontvanger de fout vinden door het dichts bijzijnde codewoord te gebruiken. Inderdaad, 0100101 is het enige codewoord dat in slechts 1 positie verschilt van 0101101.

Neem nu even de eerste zes bits van een codewoord  en verdeel ze als p_1p_2,p_3p_4 en p_5p_6. Gebruik nu het eindige veld met 4 elementen, gedefinieerd door volgende bewerkingen:

Neem nu terug  het codewoord 0100101. De punten (1,p_1p_2)=(1,1), (2,p_3p_4)=(2,0) en (3,p_5p_6)=(3,2) blijken alle drie op de rechte y=2x+3 te  liggen. Reken na met bovenstaande bewerkingstabellen. Deze eigenschap kan gebruikt worden bij het decoderen. Veronderstel dat het ontvangen  codewoord 0101101 is. Met de zes eerste bits vormen we, zoals hierboven beschreven drie punten A(1,1),B(2,1) en C(3,1). De rechte door A en B bevat C niet.Omdat de Hamming code 1 fout kan detecteren, veronderstellen we dat 1 van de punten fout is. De oorspronkelijke rechte is dus ofwel AB:y=1, AC:y=2x+3 of BC:y=3x. Dan zouden de zes eerste bits van het originele codewoord 010101,010010 of 110110 moeten zijn. Onder deze drie mogelijkheden voldoet enkel 010010 aan p_7=p_2+p_3+p_4 mod 2. Bijgevolg decoderen we de ontvangen boodschap 0101101 als 0100101 en was de oorspronkelijke boodschap 0100.

Deze proceduren lijkt erg complex. Ze kan echter veralgemeend worden om meer fouten verbeterende codes te construeren, door gebruik te maken van veeltermen in plaats van rechten.

Het idee om dergelijke veetermen te gebruiken werd het eerst naar voren gebracht door Reed en Solomon in 1960.

Griekse wiskunde: deel 1

De intellectuele geschiedenis van Griekenland ontstaan is de Archaïsche periode ( 8 ste – 6 de eeuw voor Christus) in de stadstaten aan de boorden van de Egeïsche zee.

Deze steden zijn handelscentra die in contact komen met de Oosterse beschavingen. Zo wordt op het einde van de 7de eeuw v. C. , en ongetwijfeld uit Babylonische en Egyptische bronnen, de wiskunde, in het bijzonder de meetkunde, door Thales van Milete
( 624 v.C.-545 v.C.) geïntroduceerd.

Eerste van 7 wijzen, vader van de Griekse meetkunde, ziehier twee epitheta van Thales. De filosofen uit die tijd stelden zich tot doel orde te scheppen in de schijnbare wanorde van de ons omringende werkelijkheid. Ze probeerden een antwoord te vinden op de vraag naar het waarom der dingen. Geconfronteerd met de onbetrouwbare gegevens van de Babylonische en Egyptische wiskunde, probeerde Thales dan ook niet alleen de waarheid, maar ook het waarom van die resultaten te achterhalen en ze te ordenen. De Griekse meetkunde vertoont aldus van bij de geboorte haar karakter van deductieve wetenschap. 

Volgende stellingen worden aan Thales toegeschreven:

  • elke middellijn verdeelt de cirkel in twee congruente delen.
  • de basishoeken van een gelijkbenige driehoek zijn gelijk.
  • overstaande hoeken zijn gelijk.
  • het congruentiekenmerk HZH.

Onder druk van de Perzische veroveringen in Klein-Azië verplaatst het centrum van de culturele activiteiten zich halfweg de 6de eeuw v.C. naar Zuid-Italië en Sicilië: hier komt men in de school van Pythagoras tot intensieve beoefening van de wiskunde.

 

 

 

 

Spiraal Van Fermat

 

 

Bovenstaande figuur is een spiraal. Een spiraal is een kromme die rond een bepaald punt draait en steeds dichter dit punt nadert of zich er steeds verder van verwijdert. Ze wordt gegenereerd, in poolcöordinaten, door r^2=a\theta.  De twee takken : 

In zijn manuscript Ad loos planos et solidus lisagoge ging    Fermat dieper in op het analytische werk van Descartes en hij bestudeerde verschillende belangrijke krommen, zoals de Fermat-spiraal hierboven (1636). Voor elke waarde van \theta , bestaan er positieve en negatieve waarden voor r, wat leidt tot een kromme die symmetrisch rond de oorsprong draait.

 

Circulair priemgetal

Een  circulair priemgetal is een priemgetal dat een priemgetal blijft bij elke cyclische rotatie van de cijfers . Zo is 13 een circulair priemgetal, want het is priem en ook 31 is een priemgetal. 

Het is duidelijk dat een circulair priemgetal nooit het cijfer 0,2,4,5 of 8 kan bevatten, want door een cyclische permutatie komt dat cijfer ooit achteraan en dan is het getal deelbaar door 2 of 5 en dus niet priem.

De eerste circulaire priemen zijn 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197,…

Er is een stelling die zegt dat elk priemgetal dat enkel bestaat uit enen, altijd een circulair priemgetal is. Eveneens beweert men dat er oneindig veel priemgetallen bestaan met enkel enen. Dus zijn er ook oneindig veel circulaire priemgetallen. Waarschijnlijk zijn er, vanaf 1000000, geen andere dan die met enkel enen.

Verkiezingen

In deze tekst kan je wat meer lezen over verschillende kiesmechanismen .

Dit zijn procedures volgens dewelke de uitslag van een verkiezing bepaald wordt. Het lijkt zo vanzelfsprekend, dat bij verkiezingen de meeste stemmen gelden. We zullen echter zien dat aan dit kiesmechanisme toch nogal wat bezwaren kleven.