165837. lajstromszámú szabadalom • Eljárás kódolással rövidített bináris jelsorozatok dekodolására
MAGYAR NÉPKÖZTÁRSASÁG ORSZÁGOS TALÁLMÁNYI HIVATAL SZABADALMI LEÍRÁS SZOLGÁLATI TALÁLMÁNY Bejelentés napja: 1970. IX. 30. (SA-2133) Közzététel napja: 1974. VI. 28. Megjelent: 1976. VII. 31. 165837 Nemzetközi osztályozás: G 06 f 5/02 H 03 k 13/24 ' ' i Feltalálók: Dr. DÉNES József matematikus 40% és Dr. SZOKOLAY Mihály villamosmérnök 60%, Budapest Tulajdonos: Számítástechnikai Koordinációs Intézet, Budapest Eljárás kódolással rövidített bináris jelsorozatok dekódolására 1 A találmány tárgya olyan redundanciacsökkentő dekódoló eljárás és berendezés, amelyben a binárisan kódolt jelsorozatból az eredeti jelsorozat egyértelműen visszaállítható. A számítástechnika, adatátvitel, vezérléstechnika 5 területén igen elterjedt az információnak bináris számrendszerben történő ábrázolása. A bináris számrendszerben mindössze két számjegy, a 0 (nulla) és 1 (egyes) fordul elő. A bináris számrendszer használata azért hasznos, mivel az adatok fizikai 10 megjelenítéséhez a technikailag egyszerű kétállapotú rendszerek használhatók. Az információ (pl. adatok, betűk, jelek stb.) bináris ábrázolása nulla és egyes számjegyekből álló sorozatot eredményez. Nevezzük ezt a sorozatot 15 elemi jelsorozatnak, vagy röviden jelsorozatnak. Az esetek többségében ezekben a jelsorozatokban a nullák és egyesek — vagyis az elemi jelek — véletlenszerűen követik egymást. A valóságos sorozatok egy részénél azonban megfigyelhető, hogy az 20 elemi jelek előfordulási gyakorisága nem azonos, sőt a gyakoriságok közötti különbség igen nagy. Más sorozatoknál nem az elemi jelek, hanem az elemi jelek valamilyen rövidebb-hosszabb sorozatainak — amely sorozatokat betűknek vagy blokkoknak nevezzük — 25 az előfordulási valószínűsége között mutatható ki különbség. A kódoláselméleti kutatások során számos eljárás alakult ki, amelyek segítségével az információs elemi jelsorozatok hossza csökkenthető, ha a fent említett 30 elemi jel-, vagy sorozatgyakoriságok különbözők. így pl. eredményesen csökkenthető — zsugorítható - az információs jelsorozat hosszúsága változó szóhosszúságú kódok segítségével. A változó szóhosszúságú kódok alkalmazásának bemutatására vegyük a következő elemi jelsorozatot: .... 000000000110001000000000000..... A sorozatban 27 elemi jeléből 24 nulla, 3 pedig egyes értékű. Képezzünk egy új elemi jelsorozatot a következő szabály szerint: A sorozat elejéről kezdve minden kettős nulla helyett az új sorozatban egy nullát, egy egyes helyett két egyes, egy nulla—egyes jegyekből álló kettős helyet pedig egyes—nulla jegyekből álló kettősét, azaz alkalmazzuk a következő szabályt: 00 • 0 1 >11 (a) 01 >10 Ezt a kódátalakítási szabályt Bloch ismertette először. A műveletet elvégezve: ....00001110011000000.... Ez már az eredeti sorozatnál kb. 63%-kal rövidebb. Az eljárást erre a sorozatra ismételten folytatva: ....0010101001010000.... ....01011110101100 Az eredeti 27 jegyből álló sorozat 14 jegy hosszúságúra sikerült csökkenteni. Az eljárás folytatása azonban most már nem hasznos, mivel ez 17 jegyű bináris számot eredményezne: ....11111010101111100.... 165837 1