[nastava:2003] - Re: Racunarske telekomunikacije - Hemingovi kodovi - hitnoooo :)) by "Aleksandar Milosevic" <m.aleks@sezampro.yu>

Bilo je davno ali da pokusam.
  Kad se stavlja bit parnosti (on bi trebalo
  da ima veze sa detekcijom dve greske)?

  Evo dva primera koji me bune:
  a) naci heming kodnu rec za sledece informacione
  bite 111111, ako je primenjen kod za detekciju jedne
  i korekciju jedne greske.

  -- Ovde mora da se stave bar 4 zastitna bita. Posto je
  onda kodirana rec 10 bita, greska moze da pokazuje i
  na nepostojece pozicije ( >10). Da li to govori o postojanju
  dve greske? Ali trazeno je da se detektuje samo jedna...

Ovo je iz knjige "Uvod u teoriju informacija i kodovanje". 

Postavlja se pitanje sta treba raditi ako nije moguce, iz razlicitih razloga, koristiti kodne reci duzine 2^j - 1. Neka, recimo, kodne reci moraju da budu duzine 12, ili neka je potrebno da kodna rec sadrzi 9 informacionih bita. U prvom slucaju (n=12) bice na isti nacin kao i ranije formiran kod (12, 8). Posto je 7<n<15, moraju se dodati 4 provere na parnost, te ostaje mesta za 12-4=8 informacionih bita. Pri formiranju provera moze se smatrati da se na pozicijama 13, 14 i 15 nalaze nule, a ako se na prijemu (na 12 primljenih bita) dobije vrednost sindroma koja pokazuje da su se upravo na ovim pozicijam dogodile greske, to znaci da se desio veci broj gresaka koje su na ovaj nacin otkrivene. U kod je uneta veca redundansa nego sto je potrebno, sto omogucava otkrivanje nekih visestrukih gresaka.... U drugom slucaju (k=9), kod ce biti oblika (13,9), a komentari su analogni prethodnim...Naravno, i na svaki od ovih kodova se jos moze dodati opsta provera na parnost koja omogucava otkrivanje svih dvostrukih gresaka.


  b) dekodovati kodnu rec 111111111110, ako je primenjen
  kod za korekciju jedne i detekciju dve greske.

  -- Posto imamo 12 karaktera isto mora bar 4 zastitna bita
  i dolazimo u stiuaciju slicnu kao pod a). Ako stavimo i bit 
  parnosti onda gde on ide, na kraj, to mi je malo nelogicno...

Malo je bilo davno od kada sam ovo polagao ali prema onome sto vidim u knjizi, ovo je analogno onome sto sam ti pekucao samo ovde imas kod(12, 7). Jedan bit opste parnosti za detekciju greske, ostaje ti 11. 4 je najmanji broj kontrolnih bita, pa ti ostaje sedam informacionih i 4 su uvek 0 (i8... i11) pa ne uticu na opsti bit parnosti. Ovo ti je skraceni (15, 11) odnosno  "skracen pa prosiren" ,  jer imas detekciju dve greske i jos ponesto viska kao u slucaju pod a).

Opet iz knjige:

Kodovi dobijeni dodavanjem novih provera na parnost cesto se zovu prosireni (expanded), dok su skraceni (shortened) oni kodovi gde se izostavljaju pojedini informacioni simboli. Prema tome, (8,4) je prosireni (7,4), a (13,9) je skraceni (15,11).