У. Питерсон - Коды, исправляющие ошибки (1267328), страница 51
Текст из файла (страница 51)
Двоичный циклический (2'" — 1,2' — т — 2) -код с расстоянием 4 может быть порожден многочленом (Х+ 1) р(Х), где р(Х) — примитивный многочлен. Код Хэмминга, исправляющий одну ошибку и обнаруживающий две ошибки, является нулевым пространством матрицы нием, равным 3. В этой главе описано несколько подходов к обобщению понятия кода Хэмминга. Два из них представлены в данном разделе и один в задаче 8.6.
Наиболее естественным обобщением кода Хэмминга на случай поля 6Р(д) является код, совпадающий с нулевым пространством матрицы (8.16) Н=(р' ', р", ° ° ., Р 1) т. е. код, содержащий вектор (Г(Х)) тогда и только тогда, когда элемент Г( является корнем многочлена )(Х), где р = а» ', а ив примитивный элемент 6Р(ды). Тогда, так как а» -' = 1, то й(»м (1!(»- » и число и равно порядку элемента р, т. е. »Р~ и= Ю » — ! как это должно быть для совершенного обобщенного кода Хэмминга. (См. равд.
6.1.) Теорема 8.4. Нулевое пространство магрибы Н =(р" ', р" з, ... ..., (3, Ц, где и = (д — 1)/(у — 1), является кодом с минимальным расстоянием, равным 3, тогда и только тогда, когда числа т и д — 1 взаимно просты. Доказательство. Поскольку число д) — 1 делится на ч — 1 при любых значениях 1, то существует целое число зь такое, что у)= (д — 1) з)+ 1. Следовательно, м и — ут-) + дт-з + + 1 » †= (д — 1) (з, + з + ..; + з,) + и) (8.17) где а — элемент из 6г" (д). Тогда (Р-) = а. Ненулевые элементы поля по теореме 6.18 должны быть корнями многочлена К» ' — 1 и, следовательно, должны совпадать с одной из первых о — 1 степеней элемента а".
Таким образом, (» — » ()-н — (»)» и и взаимно просто с д — 1 тогда и только тогда, когда )и взаимно просто с д — 1. Предположим теперь, что оди( из столбцов матрицы Н кратен другому столбцу: ~) =аР', для некоторого целого з, такого, что з ~ д — 1 и (7 — 1) (! — /) = лз. (8.18) Но величина з не может делиться на д — 1, так как з (д — 1, и если числа д — 1 и и взаимно просты, то разность ! — / должна быть равна О и поэтому а = 1. Это значит, что не существует двух различных линейно зависимых столбцов матрицы Н. С другой стороны, если числа д — ! и п не взаимно просты, то существует нетривиальное решение уравнения (8.18), а следовательно, и (8. 17), Ч.
т. д. Другой формой модифицированного кода Хэмминга является нулевое пространство матрицы "-[.',---,";.", 1 Этот код можно определить также следуюгцим образом: вектор (/(Х)) принадлежит коду тогда и только тогда, когда элементы а и 1 являются корнями многочлена /(Х), где а — примитивный элемент поля ОР(д -'). Этот код исправляет одиночные ошибки, поскольку никакие два столбца матрицы Н не могут быть линейно зависимыми.
Он содержит т проверочных символов и всего д -' символов вместо максимально возможных (д — !)/(д — !) символов. Его длина примерно в (д — 1)/д раз меньше максимально возможной. Порождающий многочлен для этого кода равен произведению многочлена Х вЂ” 1 и примитивного многочлена р(Х) степени ш — 1. В равд. 8.7 описывается процесс кодирования для обобщенных кодов Хэмминга обоих типов, а в равд. 8.9 — декодирование.
8Л. Коды, задаваемые последовательностями максимальной длины Рассмотрим теперь наибольший возможный период для линейного регистра сдвига с обратной связью, имеющего т ячеек, или, что то же самое, наибольший возможный период решения разностного уравнения, соответствующего многочлену степени т. Выходная последовательность начнет повторяться, как только начнут повторяться векторы, содержащиеся в регистре сдвига, и, следовательно, содержимое регистра сдвига должно быть различным для Разных наборов символов на выходе в пределах одного периода. Кроме того, если регистр сдвига содержит только нули, то все выходные символы будут также нулями.
Последовательности длины, большей чем д"' — ! — числа ненулевых векторов длины ш, — следовательно, невозможны. Сушествование таких последовательностей может быть доказано алгебраически следующим образом. Пусть й(Х) — миогочлен степени т, соответствующий обратной связи в регистре сдвига. Тогда по теореме 7.1 период последовательности равен наименьшему значению п, для которого мнагочлен Х' ~ — 1 делится на й(Х), и, следовательно, я (д — 1. Но если й(Х) — примитивный многочлен, то Х" — 1 не делится на Ь(Х) ни при каких меньших значениях п, так что период последовательности в точности равен д — 1.
Примеры генераторов с регистром сдвига, порождающих двоичные последовательности максимальной длины„приведены на фиг. 7.15 и 7.20. Совокупность всех возможных выходов такого регистра сдвига, т. е. совокупность всех решений соответствующего разностного уравнения, имеет размерность, равную и, и,следовательно, существует д"' таких решений. Одним из них является последовательность, состоящая из нулей. Все д"' — ! циклических сдвигов для любой другой последовательности также должны быть решениями. Это число совпадает с общим числом ненулевых решений. Следовательно, любые два ненулевых решения отличаются друг ог друга только тем, что одно из них является циклическим сдвигом другого.
Множество векторов, которые являются первыми периодами всех решений, образует идеал и, следовательно, циклический код. Ненулевым решением, начинающимся с наибольшего числа нулей, должен быть порождающий многочлен кода Вектор, содержащийся в регистре сдвига, состоит из т следующих друг за другом элементов последовательности. Поскольку векторы, содержащиеся в регистре сдвига, должны быть различными для всех элементов в пределах одного периода, то каждый ненулевой вектор с т компонентами должен появиться в ог соседних разрядах последовательности максимальной длины в одном и только в одном месте. Наконец, в совокупности всех и-мерных векторов каждый элемент поля появляется в 1/у-й доле всех тд'" возможных разрядов, т.
е. в тд — ' разрядах. Если нулевой вектор не учитывать, то нуль появляется только т(д -' — 1) раз, Поскольку каждый т-мерный вектор появляется в последовательности максимальной длины один и только один раз и, таким образом, каждый элемент последовательности считается гп раз, то каждый ненулевой элемент появляется в пределах одного периода последовательности максимальной длины у — ' раз, а нуль появляется д -' — 1 раз. Этим полностью определяется структура по- парных расстояний таких кодов.
Проверочный многочлен для двоичного (2~ — !,т)-кода с наборами максимальной длины является примитивным многочленом. Таким образом, этот код является двойственным для рассмотренного в предыдущем разделе циклического кода Хэмминга, порождающим многочленом которого является этот примитивный многочлен. 8„6. Некоторые двоичные циклические коды В приложении Г дан список двоичных циклических кодов нечетной длины, меньшей или равной 65 [42) В таблице приведены значения п, й, минимального расстояния, а также значения мини.
мального расстояния, гарантируемого границей БЧХ нз равд. 9.1, и показателей корней порождающего многочлена. [В предполо. женин, что а' — корень многочлена п(Х), где о. — корень много- члена Х" — 1 порядка п, в этой таблице перечислены наименьшие целые числа из совокупности (й 2! по модулю п, 2з! по модулю и, ...)) Коды, для которых д(Х) = Х вЂ” 1, обладают минимальным расстоянием, равным 2, а коды, для которых д(Х) = (Х" — 1)/(Х— — 1), имеют минимальное расстояние, равное я.
Коды обоих этих типов существуют для всех значений п н поэтому не приводятся в таблице. Кроме того, не приводятся коды длины и, для которых Х'" — 1 делится на д(Х), и ~ и; для этих кодов д = 2. Преобразование Х' — Хо' переводит циклический код в эквивалентный циклический код прн условии, что (и, р) = 1, т.
е. при условии, что числа и и р взаимно просты. (См. задачу 8.19.) В таблице приводится только один член нз каждого такого класса эквивалентных кодов. Несколько кодов длины 63 содержат болыпе информационных символов, чем БЧХ-коды с тем же самым минимальным расстоянием; такие коды отмечены в таблице звездочкой. Все эти коды могут быть получены из (63,46)-кода с д = 7, построенного Пнтерсоном [2351, (63,28)-кода с И = 15, найденного Кисами и Токура [17Ц, (63,21)-кодов с 0=17 и И=18 и (63,19)-кода с д = 19.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
