Кодиране на канала. Линейни блокови кодове. Код на Хеминг. Циклични кодове. BCH кодове.

Кодиране на канала. Линейни блокови кодове. Код на Хеминг. Циклични кодове. BCH кодове.

Линейни блокови кодове




Код на Хеминг

Определение: Нека `h>=2` е цяло число. Тогава двоичният систематичен линеен код `(n, k)` с дължина на кодовата дума `n=2^k -1` бита, дължина на информационния блок `k=2^k -1-h` бита и минимално кодово разстояние `d_min = 3` с контролна матрица, чиито колони се състоят от всички ненулеви двоични думи с дължина `h`, се нарича код на Хеминг.

Пример.
Нека   и  , т.е. имаме двоичен линеен (7, 4) - код на Хеминг. Съгласно даденото определение, за този код на Хеминг контролната матрица   и генераторната матрица   ще имат вида:

 ,                                                    (1.66)        

  ,                                                 (1.67)
като генераторната матрица се получава непосредствено от контролната матрица. Кодираният вектор   се получава посредством следното матричното умножение:
 ,                                 (1.68)
където   е векторът на съобщението. В така образувания систематичен код на Хеминг информационните битове са разположени на първите  позиции във вектора  , а контролните битове заемат последните   позиции, т.е. векторът   има вида   .
В приемника двоичният вектор на входа на декодера   представлява оценка на кодирания вектор  . Наличието на шум в комуникационния канал е причина за възникването на грешки, при което е възможно кодираното съобщение и приетото съобщение да се отличават, т.е.  .  Основният метод за декодиране на линейни блокови кодове (и в частност за декодиране на кода на Хеминг) се заключава в изчисляване на т.нар. синдром на приетия вектор
  ,                                                                   (1.69)  
при което за разглеждания (7, 4) - код на Хеминг следва да се изчислят следните три контролни съотношения:
 ,                                                           (1.70)
откъдето  . Получаването на нулев синдром, т.е.  , указва отсъствието на грешки в приетия вектор или възникването на неоткриваема грешка. От друга страна, получаването на ненулев синдром указва наличие на грешка в приетия вектор, при което съществува еднозначно съответствие между синдрома и позицията на грешката, т.е. на точно определен синдром съответства точно  определена позиция на грешката. Именно наличието на еднозначно съответствие между синдромът и позицията на грешката позволява коригирането на възникналите грешки (в границите на коригиращата способност на кода). Така например за разглеждания (7, 4) - код на Хеминг получаването на синдром от вида    указва възникването на единична грешка на трета позиция (считано от старшия към младшия бит) в приетия вектор.