Лабораторная работа №6. «Коды БЧХ».

 

Теоретическая часть.

 

Коды Боуза-Чоудхури-Хоквингема (БЧХ) относятся к циклическим кодам с , то есть позволяющим исправлять не менее двух ошибок. Методика их построения имеет отличительные особенности в выборе образующего многочлена. Выбор образующего многочлена в основном зависит от длины кода n и числа исправляемых ошибок s. Соотношения длины кода n, числа информационных символов k и количества корректирующих разрядов r приведены в таблице 2. Для, так называемых, примитивных двоичных кодов БЧХ необходимо, чтобы n удовлетворяло условию: для некоторого натурального числа h.

Если известна длина кода n, удовлетворяющая указанному выше условию, то . Тогда, чтобы построить многочлен g(х), порождающий БЧХ код с исправлением s ошибок, необходимо, выбрав произвольный примитивный многочлен P(z) степени h, построить поле Галуа GF(2h) (очевидно, при таком построении z будет примитивным элементом поля GF(2h)), найти минимальные многочлены Рi(х), (i = 1, 2, …, 2s) для всех нечётных степеней zi выбранного примитивного элемента и положить g(х)=НОК(Р1(х),Р3(х), …, Р2s-1(х)).

На практике, поскольку минимальные многочлены табулированы, можно обойтись без непосредственного построения поля Галуа, как это, например, показано ниже.

Число контрольных символов равно степени образующего многочлена g(х). Построение производится при помощи минимальных многочленов (таблица 3).

h указывает на колонку в таблице минимальных многочленов (таблица 3), из которой производится выбор многочлена Р(х).

Так как для построения g(х) используются только нечетные многочлены, то их количество равно числу исправляемых ошибок.

Обнаружение и исправление ошибок производится по той же методике, что и для циклических кодов.

ПРИМЕР

Задание. Закодировать информационную комбинацию α=10011, , построив порождающий многочлен для кода, исправляющего s=3 ошибок при минимальной длине n кодового слова. Внести m = 2 ошибки в кодовую комбинацию; проверить полученное сообщение; найти и исправить ошибки.

 

Очевидно, что число информационных разрядов k=5.

По таблице 2 находим наименьшее значение n=15 для k=5, s=3.

Тогда h = log16 = 4, следовательно, старшая степень минимального многочлена равна 4.

i=2s-1=5, следовательно из четвертой колонки таблицы 3 выбираем Р1(х),Р3(х),Р5(х).

g(х) = НОК(Р1(х),Р3(х),Р5(х)) = 10011∙11111∙111 = 10100110111 – образующий многочлен.

r=10, следовательно умножаем информационную комбинацию на х10, а затем делим на образующий многочлен,

 

                     
                             
                             
                             
                             
                               

 

β =100110111000010 – кодовая комбинация. Внесем ошибку во второй и третий разряды.

=111110111000010

 

                   
                             
                             
                             
                             
                               

 

Так как вес остатка больше 3, то произведем циклический сдвиг на один разряд влево, и снова найдем остаток от деления на образующий многочлен:

 

                   
                             
                             
                               

 

Вес остатка больше 3, следовательно сдвигаем на второй разряд влево с последующим делением на образующий многочлен:

 

                   
                             
                             
                             
                             
                             
                             
                               

 

 

Вес остатка снова больше 3, следовательно сдвигаем еще на разряд влево с последующим делением на образующий многочлен:

 

                       
                             
                             
                             
                             
                                               

 

Так как вес остатка не больше корректирующей способности кода, то производим суммирование по модулю 2, и для получения исправленной комбинации производим циклический сдвиг на 3 разряда вправо:

 

                         

 

Исправленная комбинация βисп =100110111000010.

 

практическая часть

 

Закодировать указанные информационные комбинации, построив порождающий многочлен для кода, исправляющего s ошибок при минимальной длине n кодового слова. Внести m ошибок (m ≤ s) в кодовую комбинацию; проверить полученное сообщение; найти и исправить ошибки.

 

Вариант Информационные комбинации
s = 3 1111101 s = 15 s = 2
s = 5 1001111000 s = 13 1111110 s = 2
1111001110110011 s = 3 01100 s = 3 0011110 s = 2
0001101 s = 15 11110100111 s = 5 0111010 s = 2
01010111111 s = 5 01010 s = 3 0011110 s = 2
Вариант Информационные комбинации
00001 s = 3 1000001000 s = 13 1110000 s = 2
1101001 s = 15 11111 s = 3 0001110 s = 2
0011001110110010 s = 3 01010100000 s = 5 0010011 s = 2
1110001 s = 15 10101 s = 3 1111111 s = 2
11110 s = 3 1000001110110001 s = 3 1111110 s = 2
01010110101 s = 5 1111111 s = 15 0101010 s = 2
0001101000 s = 13 01011111111 s = 5 1100111 s = 2
0010101 s = 15 1101001010110010 s = 3 1010000 s = 2
11001 s = 3 0000001 s = 15 1000000 s = 2
11010000111 s = 5 1111111000 s = 13 0000010 s = 2
           

 

 

Вопросы

10. Линейное кодирование. Основные понятия.

11. Порождающая и проверочная матрицы; синдром.

12. Помехоустойчивое кодирование. Основные понятия. Расстояние Хемминга; кодовое расстояние.

13. Коды, порождённые многочленами. Основные понятия.

14. Циклические коды. Основные понятия и свойства.

15. Неприводимые, примитивные и минимальные многочлены.

16. Коды Боуза-Чоудхури-Хоквингема.

 


Приложение.

Таблица 1.

Фрагменты таблицы образующих многочленов.

 

код[2] код код

 

Таблица 2.

Соотношение корректирующих и информационных разрядов для БЧХ кодов[3].

n K r s n k r s

 

Таблица 3.

Минимальные неприводимые многочлены в поле Галуа GF(2).

степень
 
   
   
     
     
         
           
           
         
         
           
           
           
             
               
               
             
           
             
             
           
           
               
               
           
             
             
               
               
                 
                 
                 
               
               

 

Таблица 3(продолжение).

 
             
             
             
                 
                 
                 
           
             
               
               
               
               
                 
                 
               

 


Список литературы

1. Димтриев В.И. Прикладная теория информации: Учеб. Для студ. Вузов по спец. “Автоматизированные системы обработки информации и управления”. - М.: Высш.шк., 1989. -320с.

2. Темников Ф.Е. и др. Теоретические основы информационной техники. -М.: Энергия, 1979

3. Куликовский Л.Ф. и др. Теоретические основы информационных процессов. -М.: Высш.шк., 1987

4. Цымбал В.П. Теория информации и кодирование. -Киев: Вища школа, 1977

5. Ризаев И.С. Сборник задач по курсу “Теория информации и кодирование”, Казань, КАИ, 1976

6. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. -М.:

 


[1] – округление в большую сторону.

[2] Под заголовком код понимается вектор коэффициентов многочлена, например, коду 11 соответствует многочлен х+1, коду 1001 сопоставляется многочлен х3+1.

[3] В таблице приняты следующие обозначения: n – длина кода, k – число информационных символов, r – число корректирующих символов, s – число исправляемых ошибок.