Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Если сферически упакованный код, исправляющий е ошибок, удовлетворяет более сильному условию, состоящему в том, что любая последовательность удалена от некоторого кодового слова на расстояние, не большее е, то он называется совершенным кодом. В этом случае рассмотренный выше декодер исправляет все конфигурации е ошибок и не исправляет ни одной конфигурации большего числа ошибок.
N — 2N~L— 1.
(6.1.16)
N = 7, L = 4.
219
Единственными найденными двоичными совершенными кодами являются: коды Хэмминга (исправляющие единичные ошибки), все коды из двух кодовых слов с нечетной длиной блока, у которых кодовые слова отличаются во всех позициях, и код с проверкой на четность, исправляющий тройные ошибки с N = 23 и L — 12, открытый Голеем (1949). Как показал Элайс*), для любой скорости R, О <С R <1, выраженной в битах, не существуют двоичные сферически упакованные коды с длиной блока, большей N, где N зависит от R.
“gl ~ gl
Si g i
ё] Uj й;
8l
Рис. 6.1.6.
Проблема отыскания сферически упакованных кодов является, к сожалению, проблемой отыскания оптимальных (обладающих минимальной вероятностью ошибки) кодов среди кодов с проверкой на четность и среди произвольных кодов. Питерсон (1961) для двоичного симметричного канала составил таблицу известных оптимальных кодов с проверкой на четность, но ее расширение на большие длины блоков при произвольных скоростях не представляется возможным. Вместе с тем с практической точки зрения решение этой проблемы нельзя считать настоятельно необходимым. Известно, что вероятность ошибки при заданной скорости может быть сделана произвольно малой с помощью увеличения длины блока. Более важной чем проблема отыскания наилучшего кода при заданной длине блока является проблема отыскания наиболее легко практически реализуемого кода с какой-либо длиной блока, дающего требуемую вероятность ошибки.
Далее изучим здесь связь между различными кодами с проверкой на четность и, в частности, связь между систематическими и несистематическими кодами. Если две порождающие матрицы имеют одно и то же пространство строк, то они порождают одно и то же множество кодовых слов, хотя и с различными отображениями информационных последовательностей на кодовые слова. Назовем такие порождающие матрицы эквивалентными. Отметим, что если две строки g; и g; порождающей матрицы переставить местами, то результирующая матрица будет эквивалентна первоначальной. Аналогично, если строку g;
Доказательство результата Элайса приведено в работе Шеннона, Галла-гера и Берлекэмпа (1967).
220
прибавить к gj, как показано на рис. 6.1.6, то результирующая матрица также будет эквивалентна первоначальной.
Произвольная порождающая матрица G может быть приведена к эквивалентной матрице в «приведенно-ступенчатой форме» следующим образом. Выбирается первый ненулевой столбец, затем строки переставляются таким образом, чтобы первая строка имела в этом столбце 1, и, наконец, эта строка добавляется ко всем другим строкам, имеющим единицы в этом столбце, после чего единица остается лишь в первой строке рассматриваемого столбца. Аналогичная процедура может быть проделана со следующим столбцом, имеющим хотя бы одну единицу в оставшихся L—1 строках, после чего в этом столбце единица остается лишь во второй строке, и т. д. Процесс заканчивается либо тем, что в каждом из L столбцов останется по одной единице в различных строках, либо тем, что в нижней части матрицы останутся одна или несколько строк, целиком состоящих из нулей. Последний случай, который произойдет, если строки G линейно зависимы, неинтересен, так как означает, что имеются меньше чем 2L различных кодовых слов и для каждого сообщения существует по крайней мере одно другое сообщение с тем же кодовым словом (см. задачу
6.10). В первом же случае каждый из столбцов, содержащих одну единицу, можно интерпретировать как столбец, соответствующий информационным символам, а остальные N—L столбцов — как соответствующие проверочным символам.
Таким образом, для любой порождающей матрицы G существует эквивалентная матрица G', которая, если не принимать во внимание расположение информационных символов, соответствует систематическому коду. Проверочная матрица Н для эквивалентного систематического кода имеет вид, аналогичный представленному на рис. 6.1.3, с той разницей, что единичная подматрица занимает те'(М—L) строк, которые соответствуют положению проверочных символов, и эти строки не обязательно являются последними N—L строками. Так как первоначальный код имеет то же самое множество кодовых слов, что и эквивалентный систематический код, кодовые слова в обоих случаях удовлетворяют соотношению хН = 0. Синдром принятой последовательности у, как и прежде, определяется равенством S = уН и можно, как и прежде, проводить декодирование на основе синдромной таблицы декодирования.
