А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 8
Текст из файла (страница 8)
Они позволяют исправлять любое фиксированноечисло ошибок над двухбуквенным алфавитом и примыкают к коду Хэмминга (который является их частным случаем).3618. ëÏÄÙ âþèРассмотрим поле F из = 2 элементов и многочлены степени меньше с коэффициентами в этом поле. Такой многочлен ( ) = + + . . . + − −определяется коэффициентами , . . . , − . С другой стороны, он однозначно определяется своими значениями в точках поля F (в поле как раз элементов). Значения многочлена в каждой точке поля можно выбратьпроизвольно: каковы бы ни были эти значения, мы сможем подобратьсоответствующий им многочлен степени − 1. Так что соответствиекоэффициенты ↔ значенияявляется изоморфизмом -мерных пространств над полем F.
(Этот изоморфизм является дискретным вариантом преобразования Фурье.)Наложим теперь на многочлен некоторые ограничения. Во-первых,потребуем, чтобы его степень была меньше − (для некоторого фиксированного ). Другими словами, потребуем, чтобы старшие коэффициентов равнялись нулю. (Таблицы значений таких многочленов образуют,как мы помним, код Рида { Соломона с расстоянием + 1.)Во-вторых, потребуем ещё, чтобы значения многочлена во всех точках поля равнялись нулю или единице (поля F).
В этом случае таблицазначений будет двоичным словом длины .Все такие таблицы и являются кодовыми словами кода БЧХ.Переформулировка: слово из нулей и единиц является кодовымсловом кода БЧХ, если соответствующий ему многочлен (принимающийуказанные значения в точках поля F) имеет степень меньше − .(Здесь и | параметры кода.)Кодовое расстояние этого кода не меньше +1 (поскольку он являетсячастью кода Рида { Соломона с таким кодовым расстоянием).
Сложнеепонять, сколько при этом образуется кодовых слов. Хотя оба ограниченияна многочлен просты, но одно из них формулируется в терминах егокоэффициентов, а другое | в терминах значений, и надо ещё понять,как они взаимодействуют друг с другом.Для этого нам понадобятся некоторые сведения из алгебры. В поле Fвыделим подполе F ⊂ F, состоящее из нуля и единицы. [Чтобы убедиться, что это действительно подполе, достаточно проверить, что 1 + 1 = 0в F, то есть что характеристика поля F равна 2.
Это доказывается так:если характеристика равна > 2, то в F есть подполе из элементов,и F есть векторное пространство над этим подполем, так что размер Fесть степень числа .]10110213718. ëÏÄÙ âþèКак мы уже говорили, многочлены степени меньше образуют векторное пространство над F; условие обращения старших коэффициентов в нуль задаёт подпространство этого пространства. Но второе нашеусловие (значения во всех точках нули и единицы) не является линейным над F. Однако оно является линейным над F (по тривиальным причинам).
Поэтому построенное нами множество кодовых слов кода БЧХ(обозначим его ) является векторным пространством над полем F , инадо только определить его F -размерность.Если бы не требование обращения в нуль старших коэффициентов,то F -размерность была бы равна . Обращение в нуль каждого из коэффициентов задаётся уравнениями: коэффициент принадлежит полю F, которое имеет размерность над F . (Говоря о уравнениях, мыимеем в виду F -линейные уравнения.) Эти уравнения могут быть (и будут, как мы увидим) зависимыми, но уже сейчас можно сформулироватьтакое. F -размерность не меньше − , то есть − log .Это уже кое-что: мы получаем код длины с log проверочнымисимволами (и − log значащими) и расстоянием +1.
Например, при = 2 получается код с расстоянием 3 (как и у кода Хэмминга) и 2 log проверочными символами (что вдвое больше, чем у Хэмминга).Однако на самом деле ситуация оказывается ещё немного лучше: условий, соответствующих обращению в нуль старших коэффициентовмногочлена , линейно зависимы над полем F . Чтобы понять это, нампонадобится вспомнить ещё кое-что из алгебры.Для начала заметим, что условие «все значения многочлена | нулиили единицы» можно переформулировать так: ( ) = ( ) для всех ∈ F. Другими словами, многочлен − должен обращаться в нульво всех точках поля F. Это не значит, что все его коэффициенты нулевые(ведь степень многочлена − может быть почти в два раза большечисла элементов в поле), а означает лишь, что делится на многочлен222222Следствие22222 ( ) = ∏ ( − ).∈FПоследний многочлен равен − . Действительно, по теореме Лагранжа порядок каждого элемента в мультипликативной группе поля делитпорядок группы, равный − 1 (на самом деле верно более сильное свойство: мультипликативная группа поля обязана быть циклической; но этосейчас нам не важно).
Поэтому − = 1 для любого ненулевого элемента поля, и = для любого элемента поля. Значит, многочлен − 13818. ëÏÄÙ âþèобращается в нуль во всех точках поля, поэтому он делится на ; остаётся заметить, что у этих двух многочленов совпадают степени и старшиекоэффициенты.Итак, условие «все значения | нули или единицы» можно переформулировать так: − делится на многочлен − без остатка.Как записать это условие в терминах коэффициентов многочлена ?Заметим, что делить с остатком на − очень просто. Надо понизитьстепени по правилам2+1→+2→→ −→...−22231(Дальше должна идти строка − → → , но до таких степеней в нашем случае дело не дойдёт.) Затем надо привести подобные члены. (Этапроцедура соответствует обычному делению многочленов «уголком».)Сделаем это для многочлена − , если212 ( ) = − − + − − + . .
. + + .121210Вычислить легко, если вспомнить, что в поле характеристики 2, где1 + 1 = 0, имеет место равенство ( + ) = + , поскольку член2 обращается в нуль. Поэтому квадрат суммы есть сумма квадратов, и22 ( ) = − 221−22+ − 22−2422+ ... + + .21220Делимость − на − означает, что после замен одночленов всоответствии с приведённой выше таблицей из должно получиться ,223918.
ëÏÄÙ âþèто есть − = − − = − − = −.../ = ... = = =211233522221224212200(в обоих столбцах каждый коэффициент встречается по одному разу; вправом столбце сначала идут все нечётные, а потом все чётные коэффициенты). Заметим, что несмотря на свой квадратичный вид, каждоеиз этих условий является F -линейным (поскольку возведение в квадрат,как мы уже говорили, линейно над полем характеристики 2).Итак, мы записали условие «все значения многочлена | нули илиединицы» в виде F -линейных уравнений на его коэффициенты. Как мызнаем, пространство решений этой системы линейных уравнений имеетразмерность .
Мы хотим выяснить, напомним, насколько уменьшитсяразмерность, если наложить дополнительные ограничения − = 0, . . . , − = 0.Про − мы и так уже знаем, что − = − , то есть что − равнонулю или единице. Поэтому условие − = 0 уменьшает размерностьпространства решений на 1 (а не на , как было в нашей прежней оценке).Дальнейшие уравнения системы выражают − , − ,.
. . , через сбольшими индексами. Поэтому условия обращения в нуль достаточнозаписывать лишь для − , − , . . . вплоть до − (для чётного ) и − (для нечётного ).Ограничимся для простоты случаем чётного (при этом кодовое расстояние будет не меньше + 1, и можно исправлять /2 ошибок). Тогдаполучится /2 условий коразмерности плюс ещё одно условие коразмерности 1 (на − ).
Отсюда получаем, что F -размерность пространства кодов БЧХ длины с расстоянием не меньше + 1 для чётного не меньше − 1 − /2 = − 1 − (/2) log .Словами: на каждую исправляемую ошибку нужно log контрольныхбитов, плюс ещё один контрольный бит на всех.221211111324+112514019. âþè É èÜÍÍÉÎÇИнтересно сравнить параметры БЧХ-кодов с границей Хэмминга. Шаррадиуса = /2 содержит примерно ≈ / ! элементов (мы считаем,что ≪ и потому заменяем ( − 1) . . . ( − + 1) на ). ГраницаХэмминга говорит, что логарифм числа кодовых слов не превосходитпримерно − log( / !) = − log + log( !);первые два слагаемых как раз соответствуют БЧХ-кодам, так что разницалишь на log( !).19. БЧХ и ХэммингПокажем, что код Хэмминга может быть получен как частный случайкода БЧХ.Пусть, например, = 3, = 8 и мы рассматриваем поле F .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
