Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Коды Боуза — Чоудхури — Хоквингема (БЧХ)

Коды Боуза — Чоудхури — Хоквингема (БЧХ) являются подклассом циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием d не меньше заданного. Это важно, потому что, вообще говоря, построение кода с расстоянием не меньше заданного это очень сложная задача.

В БЧХ-коде образующий полинома представляет собой произведение нескольких неприводимых полиномов – мы далее посмотрим каких.

БЧХ коды, вообще-то говоря, как и линейные циклические коды в целом не обязательно являются двоичными., то есть с символами, из которых состоит код =1 или 0.

Символами КС слова могут быть например числа вида qm представленные в виде полиномов с недвоичными коэффициентами. Мы же рассматриваем двоичные коды, что позволяет избежать значительных усилий на знакомство с теорией полей Галуа.

В БЧХ-кодах построение образующего полинома, в основном, зависит от двух параметров: от длины кодового слова n=k+r и от числа исправляемых ошибок S.

Особенностью кода является, то что для исправления числа ошибок S>=2 еще недостаточно условия, что между комбинациями кода минимальное кодовое расстояние dmin=2*S+1. Необходимо также, чтобы длина кода n удовлетворяла условию

 

n = 2h - 1, (1)

 

где h -любое целое число.

 

При этом длина кода n всегда будет нечетным числом и принимать значения: 1,3,7,15,31,63,127..и.т.д, т.е не все значения динымогут быть заданы пользователем.

 

Выбранная по формуле (1) величина n определяет число контрольных символов r.

 

r<=h*S<=log2(n+1)*S. (2)

 

При решении задачи выбора допустимого числа информационных символов при заданных корректирующих свойствах удобно пользоваться таблицей, в которой приведены соотношения корректирующих и информационных разрядов для БЧХ кодов.

 

Построение образующего полинома G(X) производится при помощи таблицы неприводимых полиномов M(X). Образующий полином представляет собой произведение неприводимых полиномов и является их наименьшим общим кратным (НОК). Максимальный номер неприводимого полинома в их произведении

 

p = 2*S - 1. (3)

 

Порядок полинома используется при определении числа сомножителей. Для построения G(X) используются только нечетные полиномы.

Например, при S=4 ими будут: M1(X); M3(X); M5(X); M7(X). Старший из них имеет номер p=2*S-1=7. Число их равно 4, т.е. равно числу исправляемых ошибок.

Число неприводимых полиномов, участвующих в построении образующего полинома

 

V = S, (4)

 

а старшая степень

 

v= h (5)

 

указывает строку в таблице неприводимых полиномов, из которой обычно выбирается полином для построения G(X). Для построения образующего полинома используются только нечетные полиномы степени v. Иногда допускается использование полиномов и меньшей степени. Степень образующего полинома, полученного в результате перемножения выбранных неприводимых полиномов,

 

b = r = v*S = h*S (6)

 

В общем виде G(X)=НОК[M1(X)M3(X)...Mp(X)].

 

Пример: Рассмотрим построение циклического кода длиной в 15 разрядов, исправляющего одну или две ошибки. Согласно (1),

 

n = 2h - 1, откуда h=log2(n+1) = log216 = 4

 

Число контрольных символов k, согласно (2),

 

r=log2(n+1)*S=4*2=8.

 

Номер старшего из неприводимых полиномов, cогласно (3)

 

p = 2*S-1 = 2*2 -1 = 3.

 

Количество неприводимых полиномов, участвующих в построении образующего полинома, согласно (4),

 

V= S = 2,

 

cтаршая степень, согласно (5),

 

v = h = 4.

 

Степень образующего полинома, согласно (6),

 

b = r = 8.

 

Из таблицы неприводимых полиномов выбираем полиномы степени v=4, из них выбираем два (V=2) неприводимых полинома, номер старшего из которых равен 3(p=3), т.е. выбираем неприводимые полиномы p1 и p3.

 

G(X)=M1(X)*M3(X) = 10011 * 11111 = 111010001 = X8+X7+X6+X4+1.

 

Число информационных разрядов

 

k = n - m = 15 - 8 = 7.

 

Первая строка образующей матрицы получается путем добавления слева от G(X) такого числа нулей, чтобы общая длина кодовой комбинации была равна n. Образующая матрица получается в результате m кратного циклического сдвига кодовой комбинации, соответствующей первой строке образующей матрицы.

 

0 0 0 0 0 0 1 1 1 0 1 0 0 0 1

0 0 0 0 0 1 1 1 0 1 0 0 0 1 0

0 0 0 0 1 1 1 0 1 0 0 0 1 0 0

||ОМ|| = 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0

0 0 1 1 1 0 1 0 0 0 1 0 0 0 0

0 1 1 1 0 1 0 0 0 1 0 0 0 0 0

1 1 1 0 1 0 0 0 1 0 0 0 0 0 0

 

Остальные комбинации кода получаются путем умножения 27=128 строк различных информационных слов на образующую матрицу. Таким образом, мы получили набор кодовых комбинаций для приведенного выше примера состоящего из 128 кодовых слов.

 

<== предыдущая лекция | следующая лекция ==>
Матричное описание циклических кодов | Систематический вид циклического кода.
Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 2295; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.