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

Определение. Пусть ш - мультипликативный порядок числа д £ N по модулю п, т.е. дт = 1(тоо1п) и дг ^ 1(тоо1п) при 1 < г < га — 1. Далее, 6 € А* и {0} пае Г(/»»< такой, что (\" = \. (\' ф \. \ < 1 < п — \. Кодом Боуза-Чоудхури-Хоквингема (или БЧХ-кодом) длины п с конструктивнымрасстоянием о1}2 < о! < п, над полем Ря называется циклический код с порождающим многочленом, определяемым элементами

а , а

Ь+1

а

Ъ+й-2

Другими словами, порождающий многочлен д(х) этого кода совпадает с

НОК многочленов ///.(7у)(;/;).. .., т{Ь~'1 21 (;/;). где т{']{х) - минимальный мно-

гочлен о' (над полем FqJ

Замечание. Если п = д — 1, то БЧХ-код называется кодом Рида-Соломона. Если п = дт — 1, то БЧХ-код называется примитивным. Если 6 = 1, то БЧХ-код называется БЧХ-кодом в узком смысле.

Теорема. Минимальное расстояние Б ЧХ-кода с конструктивным рас­стоянием а7 не меньше, чем (I.

ДОКАЗАТЕЛЬСТВО. Согласно утверждениюя 4 из 3.8, наш код совпа­дает с нуль-пространством проверочной матрицы

Я /1

1

а

а

Ь+1

а

а2Ь

2(6+1)

а

Ъ(п-1)

\

а

(п-1)(Ь+1)

У 1 аь+^2 а2<уЬ+с1^  ...   aк'"'~1,кv~ru~'^', у Согласно предложению 2 из 3.7, для доказательства теоремы достаточ­но показать, что любые (а7 — 1) различных столбцов этой матрицы явля­ются линейно независимыми.  Действительно, рассмотрим определитель

,(п-1)(Ь+(*-2)

а

(Ь+1)»і

а

(Ь+1)»2

а

(Ъ+1)и.

у а(Ъ+<1-2)н а(Ь+гі-2)і2

(Ы-сг-г)^-!

/

= аь(гг+-+и-1) Л (п'> — п'г) ^ 0. Теорема доказана.

Эта теорема является важной, так как позволяет строить коды, испра­вляющие т; ошибок. Для этого нужно выбрать числа а7, п, д, т так, чтобы 21 + 1 < о1 < т^т - мультипликативный порядок числа д по модулю п (мы предполагаем, что (д. /у) = 1 и, следовательно, т\<р(п)). Так как группа

СР(дт)* является циклической, то в ней существует элемент а порядка п. Т.е. мы всегда можем построить такой код.

Перейдем к описанию схемы декодирования БЧХ-кодов. Пусть гп(х), у(х) и е(х) - соответственно передаваемый кодовый многочлен, принимаемый многочлен и многочлен ошибок (е = т — у). Пусть Н - проверочная матри­ца из теоремы. Тогда синдром принятого вектора у равен Б (у) = Н • ут = = (Бь, Бь+і,..., Бь+(і-2)Т, где Sj = у(а,з) = е(с^), Ь<і<Ь + оІ — 2.

Пусть при передаче произошло г ошибок, где г < Ї < ^-к Тогда е(х) = с\х'и + с->ж"- + • • • + с,.:>:"'■. где с/ )..... а,- - различные числа из множества {0,1,..., п — 1}. Элементы у,і = аа' Є і^т называются локаторами ошибки, а элементы с; Є значениями ошибки. В новых обозначениях коорди­наты синдрома вектора г равны Б у = с{(\') = сі//( + с->у!> + • • • + г,-у//. Ь<і<Ь + оІ — 2. В силу тождества (/? + 7)'' = /?9 + 79 в поле /уш и

так как г/ Є /\;. имеем равенства 5(/ = ^ г/У//(/ = 5;-(/. Ь < ] < 6 + г/ — 2.

Рассмотрим далее многочлен Х\(У1 ^ х) = стг — аг^\х + ••• + (—1)г<тожг,

где сто = 1, <71, (72,..., аг - элементарные симметрические многочлены от У1,... ,уг. Подставляя ^ вместо х, получаем систему равенств

аг - сгг„! • у{ Л-----1- (—1)гсг0 • у\ = 0,    1 < г < г.

Умножим г-ое равенство на оьу\ и сложим их все. Получим

(-1)г • аг ■ 5,- + (-І)^1^! • 5і+і + • • • + (-І)о-і • 5,-+г_і + 5І+Г = 0, (3.10)

і=1

г

г=1

где Ь < } < I) + Г

1. Матрица этой системы равна

Бь+г-і ^ ''    5ь+г     = V ■ В ■ У ' \

(     ^5 Бь+1

|+1где В

(сій  о "V

V

/

/і    і  ...   і \

у _ У1       У2     ■■■ Уг

О      Сгуг   I г—1      г—1 г—"

7 \ У\       У2       ■■■    Уг '

Ранг этой матрицы равен г тогда и только тогда, когда в векторе у имеет­ся г ошибок. Многочлен вида       = Д (1 — Уіх) = ^](—1)г<тг-жг называется

і=1 і=0

многочленом локаторов ошибки. Его корни равны у^1,..., у^1. Итак, при­ведем алгоритм декодирования БЧХ-кода с конструктивным расстоянием оі > 2^+1- Предположим, что передавалось слово гп, а получено слово у. Шаг 1. Находим синдром слова у

Б (у) = (5ь, 55+1,..., Бь+(і-2

т

Шаг 2. Находим максимальное число г < ^ такое, что система уравне-

нии

5ь+і+г  +    Бь+г^і    + ...  +   Бь+іХг   = О

Зь+2г-\   +   55+2г^2Жі   +   • • •    +   Бь+г-І^г   = О

имеет невырожденную матрицу коэффициентов (см. также (3.10)). Решая ее, мы найдем многочлен локаторов ошибки

г=1 г=0

где :/;,) = 1.

Шаг 3. Находим корни многочлена в(ж) = 0, подставляя вместо х степени а.

Шаг 4. Рассмотрим систему уравненийс\у\     +  ...   +     СгУІ     = Бь сіу\+1   + ...  +   сгуьг+1   = 5ь+і

сп/'Г^  + ...   + суу'Г^  = 5Ь+Г^і. Определитель этой матрицы равен (у\.. .уг)ь \\{уі — у і) ф 0. Следова­тельно, система имеет единственное решение сі,..., су. Итак, мы можем найти вектор ошибки е(х). Из уравнения гп(х) = у(х) — е(х) находим слово т. Примеры в 3.5 иллюстрируют применение БЧХ-кода.