Wyniki wyszukiwania - BazTech

1

Dekodowanie detekcyjno - korekcyjne kodów dwukrotnie iterowanych na bazie rozszerzonego kodu Hamminga i kodu z kontrolą parzystości

Fijałkowski M., Baran R.

TTS Technika Transportu Szynowego

|

2016

|

R. 23, nr 12

417--424

PL

W pracy analizowano dwie metody dekodowania detekcyjno-korekcyjnego kodów dwukrotnie iterowanych na bazie rozszerzonego kodu Hamminga dla kodowania wierszyi kodu z kontrolą parzystości dla kodowania kolumn różniące się ilością korygowanych i wykrywanych błędów. Podano algorytmy dekodowania detekcyjno-korekcyjnego umożliwiające poprawną korekcję i detekcję odpowiedniej ilości błędów. Opracowane algorytmy dekodowania bazują na dwóch rodzajach korekcji: korekcji na podstawie syndromów wierszy i korekcji na podstawie liczby syndromów różnych od zera. W pierwszym przypadkujest to klasyczna korekcja błędów dla kodów Hamminga, w których syndrom ciągu odebranego wskazuje korygowaną pozycję. W drugim przypadku korekcja jest przeprowadzana na pozycjach wyznaczonych przez numer wiersza i numery kolumn, w których syndromy są różne od zera.W pierwszym algorytmie dekodowania występuje jedna faza dekodowania, w której przeprowadza się korekcję na podstawie syndromów wierszy w sytuacji,gdy tylko w jednym wierszu i jednej kolumniewystępują syndromy różne od zera. W pozostałych przypadkach podejmowana jest decyzja o wykryciu błędu.Algorytm ten umożliwia poprawną korekcję błędów pojedynczych i wykrycie błędów o krotnościach mniejszych od siedmiu. W drugim algorytmie dekodowania występują dwie fazydekodowania i w obu przeprowadzanesą korekcje błędów. Algorytm ten umożliwia poprawną korekcję wszystkich błędów o krotnościach jeden, dwa, trzy i część błędów o krotności cztery, pozostała cześć błędów o tej krotności będzie wykrywana.Z dokładnych analiz pracy dekoderówprzedstawionych w tabelachmożna wywnioskować, że działają one poprawnie, to znaczy korygują i wykrywają właściwąliczbę błędów wynikającą z własności detekcyjno-korekcyjnych zastosowanego kodu.

EN

Results of comparative analysis of two different methods for detection-correction decoding of double iterated codes are presented in the paper. Analyzed methods are to decode the codes which, in particular, are based on the extended Hamming codes - in the case of rows coding, and on the parity-check codes – in the case of columns coding. A number of detected and corrected codes is the main difference between them. The detection-correction decoding algorithms, implemented by these methods to ensure an accurate detection and correction of a proper number of errors, are also presented. The row syndrome error correction scheme, typically applied for Hamming codes in which syndrome computed on a received word is the binary representation of the error location, is the base error correction scheme for the first method. In turn, an error correction based on a number of nonzero syndromes is incorporated in the second method. In this case however, error locations are identified by intersection of rows and columns with non-zero syndromes. There is only one decoding phase in the case of the first method. The row syndrome error correc-tion scheme is carried out during this phase when only one row and only one column with nonzero syndromes exist. Otherwise, an error detection is signaled. Thus, all the single-errors are accurately corrected as well as all the multiple-errors – with multiplicity less than seven - are identified. The second algorithm, in turn, has two decoding phases. Corrections of errors are carried out in both of them. An accurate correction of all the single-, double- and triple-errors is ensured in this way. In addi-tion, some quadruple-errors are also properly corrected while the remaining errors of this multiplicity are correctly identified. Results presented in the paper show that analyzed detection-correction decoding methods are optimal regarding the applied codes. For these codes, they identify and correct an appropriate number of errors.

2

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

Fijałkowski M., Baran R.

TTS Technika Transportu Szynowego

|

2015

|

R. 22, nr 12

2518--2524, CD

PL

W pracy analizowano dwie metody dekodowania detekcyjno - korekcyjnego (t=1, γ =7) i (t=2, γ =6) kodów dwukrotnie iterowanych na bazie kodów Hamminga lub skróconego kodu Hamminga. Podano algorytmy dekodowania detekcyjno-korekcyjnego umożliwiające poprawną korekcję i detekcję odpowiedniej ilości błędów. Opracowane algorytmy dekodowania bazują na trzech rodzajach korekcji: korekcji na podstawie syndromów kolumn KOR_SK, korekcji na podstawie syndromów wierszy KOR_SW, i korekcji na podstawie liczby syndromów różnych od zera KOR_LS_11. 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 pozycji wyznaczonej przez numer wiersza i kolumny, w których syndromy są różne od zera. W algorytmie dekodowania (t=1, γ =7) występuje jedna faza dekodowania. Po wyznaczeniu wszystkich syndromów wierszy i kolumn przeprowadza się korekcję KOR_LS_11 w sytuacji, jeżeli tylko jeden wiersz i jedna kolumna mają syndromy różne od zera, w pozostałych sytuacjach podejmowana jest decyzja o wykryciu błędu za wyjątkiem przypadku gdy wszystkie syndromy są równe zeru, oznaczającego bezbłędny odbiór lub błędną decyzję dekodera. W algorytmie dekodowania (t=2, γ =6) 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 lub detekcja błędów. W drugiej fazie dekodowania ponownie wyznacza się wszystkie syndromy wierszy lub kolumn i w przypadku, gdy co najmniej jeden syndrom jest różny od zera podejmuje się decyzję o wykryciu błędu.

EN

Two methods for detection-correction decoding, respectively denoted as (t=1, γ=7) and (t=2, γ=6), are presented in the paper. Both presented algorithms ensure an accurate detection and correction of a proper number of errors. They have been founded on Hamming-based double iterated codes and on three different schemes of error correction. Above-mentioned schemes of error correction are as follows: the column syndrome correction (KOR_SK), the row syndrome correction (KOR_SW) and the correction based on a number of nonzero syndromes (KOR_LS_11). The two former schemes are typically applied for Hamming codes. They use the syndrome polynomial to determine position of the bit to correct. In turn, bit at the position given by these row’s and column’s numbers for which the respective syndromes are nonzero is corrected in the third scheme. There is one decoding phase in the case of (t=1, γ=7) method. The KOR_LS_11 correction is carried out when there is only one row and only one column withnonzero syndromes. Otherwise, decision of error detection is made. An exception to above rules is when all the syndromes are zero. In that case either wrong decoder decision was made or there were no errors received. As opposed to the (t=1, γ=7) one, there are two decoding phases in the case of (t=2, γ=6) algorithm. All the column and row syndromes as well as amounts of rows (LSw) and columns (LSk) with nonzero syndromes are determined during the first above phase. Depending on LSw and LSk amounts, an appropriate error correction or error detection is performed. All the column and row syndromes are determined once again during the second phase. Decision of error detection is made when there is at least one nonzero syndrome.

3

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

Baran R., Fijałkowski M.

Logistyka

|

2014

|

nr 6

1644-1652

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.

4

Ocena jakości systemu przesyłania informacji z kodem dwukrotnie łączonym na bazie kodu Hamminga i rozszerzonego kodu Hamminga

Fijałkowski M.

Pomiary Automatyka Kontrola

|

2012

|

R. 58, nr 3

294-297

PL

W pracy analizowano metodę dekodowania detekcyjno-korekcyjnego kodów dwukrotnie łączonych na bazie kodu Hamminga i rozszerzonego kodu Hamminga. Podano reguły dekodowania dla czterech możliwych wariantów dekodowania detekcyjno-korekcyjnego. Przedstawiono schemat blokowy układu dekodera. Opracowano charakterystyki probabilistyczne pozwalające ocenić i porównać jakość systemu przesyłania infor-macji z kodem łączonym na bazie kodu Hamminga i rozszerzonego kodu Hamminga oraz z analizowanymi metodami dekodowania.

EN

Methods for detection-correction decoding of a twice merged code of the parameters (15,4) based on the Hamming code and extended Hamming code are analysed in the paper. The coding rule (2) has been determined. The rules for decoding have been given for four types of decoding: "pure" correction type (6), two detection-correction types (7) and (8) and "pure" detection type (9). The correctness of the rules has been confirmed by the coefficients shown in Tab.1. The presented decoding rules can also be applied to a code of any length of the information sequence. A block diagram of the decoder is presented in Fig. 2. Fig. 3 shows basic probabilistic characteristics which allow evaluating the quality of the data trans-mission system for one selected method of detection-correction decoding. Comparison of the probabilistic characteristics for the analysed methods of decoding is presented in Figs. 4-6. When analysing the most important characteristic - the probability of the decoder faulty decision versus the probability of an elementary fault - it can be noted that increase in the number of corrected faults t results in increase in the probability of the decoder faulty decision. For small interference intensities the probabilistic characteristics of particular occurrences as a function of the probability of an elementary fault have an exponential character (for the logarithmic scale of both axes the relation is seen as linear).