Dekodowanie korekcyjne kodów dwukrotnie iterowanych na bazie kodów Hamminga

• Autorzy: Baran R. , Fijałkowski M.

Warianty tytułu

EN

Correction decoding of double-iterated hamming based codes

• Języki publikacji: PL

Abstrakty

PL

W pracy analizowano metodę dekodowania korekcyjnego kodów dwukrotnie iterowanych na bazie kodów Hamminga. Podano reguły kodowania oraz algorytm dekodowania korekcyjnego umożliwiający poprawną korekcję błędów o krotności mniejszej od pięciu. Opracowany algorytm dekodowania bazuje na trzech rodzajach korekcji: korekcja na podstawie syndromów kolumn KOR_SK, korekcja na podstawie syndromów wierszy KOR_SW, i korekcja na podstawie liczby syndromów różnych od zera KOR_LS_22. W dwóch pierwszych przypadkach są to klasyczne korekcje błędów dla kodów Hamminga, w których syndrom ciągu wskazuje w NKB korygowaną pozycję. W trzecim przypadku korekcja jest przeprowadzana na czterech pozycjach wyznaczonych przez numery wierszy i kolumn, w których syndromy są różne od zera. W algorytmie dekodowania występują dwie fazy: w pierwszej wyznacza się wszystkie syndromy wierszy i kolumn oraz oblicza się liczbę wierszy LSw i kolumn LSk z syndromami różnymi od zera. W zależności od wartości LSw i LSk wykonywana jest odpowiednia korekcja błędów. W drugiej fazie dekodowania ponownie wyznacza się wszystkie syndromy wierszy i kolumn i przeprowadza się korekcję KOR_SW lub KOR_SK w zależności od tego jaki rodzaj korekcji był przeprowadzony w fazie pierwszej. Przedstawiono analizę działania dekodera korekcyjnego dla wszystkich możliwych błędów o krotności mniejszej od pięciu, wyznaczono takie położenia błędów o krotności pięć, które prowadzą do błędnej decyzji dekodera.

EN

Method for error correction decoding of double-iterated Hamming based codes is examined in the paper. Encoding rules as well as algorithm for error correction decoding which enables reliable correction of errors with multiplicity less than 5 are presented. The presented algorithm refers to three different types of error correction methods which are as follows: column syndrome correction (KOR_SK), row syndrome correction (KOR_SW) and correction based on a number of nonzero syndromes (KOR_LS_22). KOR_SK and KOR_SW are typical error corrections schemes as for Hamming codes, where the syndrome polynomial determines NBC position of the corrected bit. In the case of KOR_LS_22, error correction is carried out at the positions of four bits determined by these rows and columns for which their syndromes are nonzero. The presented decoding algorithm is as follows. Syndromes of all rows and columns and then the number of rows (LSw) as well as columns (LSk) with nonzero syndromes are calculated first. Next, an appropriate error correction is carried out depending on LSw and LSk values. After that, syndromes of all rows and columns are calculated again. Corrections KOR_SW or KOR_SK is carried out then, depending on kind of correction performed previously. Analysis of correction decoder operation, for all probable errors with multiplicity less than 5, is also presented in the paper. In addition, locations of such an errors, but with multiplicity equal to 5, which lead to wrong decoder decision, have been determined as a part of this presentation.

Słowa kluczowe

PL

dekodowanie korekcyjne; kod Hamminga; algorytm dekodowania

EN

correction decoding; Hamming code; decoding algorithm

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2014
• Tom: nr 6
• Strony: 1644--1652
• Opis fizyczny: Bibliogr. 8 poz., rys., tab., pełny tekst na płycie CD

Twórcy

autor

Baran R.

• Politechnika Świętokrzyska w Kielcach, Wydział Elektrotechniki Automatyki i Informatyki, 25-314 Kielce; al. 1000-lecia PP 7

autor

Fijałkowski M.

• Politechnika Świętokrzyska w Kielcach, Wydział Elektrotechniki Automatyki i Informatyki, 25-314 Kielce; al. 1000-lecia PP 7

Bibliografia

• 1. Baran Z., Podstawy transmisji danych, WKiŁ, Warszawa 1982.
• 2. Dróżdż J., Podstawy kodowania nadmiarowego. Wydawnictwa Politechniki Warszawskiej, Warszawa 1980.
• 3. Fijałkowski M., Dekodowanie detekcyjno-korekcyjne kodów dwukrotnie łączonych na bazie kodu z kontrolą parzystości i rozszerzonego kodu Hamminga. PAK, vol. 56, nr 12/2010, 2010.
• 4. Gorzałczany MB, Interval-valued fuzzy inference involving uncertain (inconsistent) conditional propositions. Fuzzy Sets and Systems, tom 29, 1989.
• 5. Gorzałczany MB, A method of inference in approximate reasoning based on interval-valued fuzzy sets, Fuzzy Sets and Systems, tom 21, 1987.
• 6. Haykin S., Systemy telekomunikacyjne. WKiŁ, Warszawa 2004.
• 7. Li FW., Yue Q., Li CJ., The Minimum Hamming Distances of Irreducible Cyclic Codes. Finite Fields and Their Applications, Vol. 29, 2014.
• 8. Wen GZ., (7,4) Binary Hamming Code For Data Transition Of Spread Spectrum Communications. Information Technology Applications in Industry II, PTS 1-4, 2013.