Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
4. Утверждение, доказанное в дополнении 3, обобщается на случай линейного кода над произвольным полем из q элементов; неравенство (4) заменяется при этом на следующее неравенство:
d-2
2 Cin _1 (q-iy < qrn,
і= о
5. Можно указать еще одну простую оценку для кодового расстояния. Поскольку суммарный вес ненулевых кодовых слов ^-ичного линейного (п, &)-кода есть nqk_1(q—1) (см. § 11, дополнение 3), то средний вес ненулевых кодовых слов равен nqlt~1(q—1)/(<7А—1). Ясно, что он не может быть меньше минимального веса, совпадающего с кодовым расстоянием d. Таким образом,
d<fu,*-4<r-D (5)
q"— 1
Мы получили границу, называемую верхней границей Плоткина.
,81 Оценка (б) обобщается на случай произвольного g-ичного кода длины п, содержащего M кодовых слов. В этом случае
(6)
q (M-I) ' w
6. Из оценки Хемминга (1) также можно получить границу для кодового расстояния. Пусть код длины п, исправляющий t и меньшее число ошибок, содержит M кодовых слов. В силу определения М(п, 2Н-1) И оценки (1) М<.М (п, 2t+l)<.qn/Vt. Отсюда получаем:
1 + (7)
Неравенство (7) дает верхнюю границу для t, а значит, и для кодового расстояния d=2/+l.
Граница Хемминга точнее границы Плоткина для кодов, избыточность которых не слишком велика (отношение числа проверочных символов к общему числу символов не превосходит 0,6). В остальных случаях точнее граница Плоткина.
Например, для двоичного (16,5)-кода оценка (5) дает d<8, а из оценки (7) получается ^<4, т. е. d<9.
7. Имеются и нелинейные совершенные коды, но их также немного. Во всяком случае известно, что любой нетривиальный совершенный код над любым полем должен иметь те же самые параметры (длину, кодовое расстояние и число кодовых слов), что и один из кодов Хемминга или Голея. Все же полное описание нелинейных совершенных кодов, исправляющих одиночные ошибки, пока не получено (см. по этому поводу [12], задача 6.6).
16. КОДИРУЕТ И ДЕКОДИРУЕТ ЭВМ
Заголовок этого параграфа не следует понимать буквально. Вряд ли было бы целесообразно привлекать универсальные ЭВМ для кодирования и декодирования с помощью линейных и циклических кодов. Однако устройства или схемы, предназначенные для этих целей, состоят из тех же элементов, что и любая ЭВМ, так что такие схемы, если угодно, можно рассматривать как специализированные мини-ЭВМ. В случае двоичных кодов применяются элементы двух основных типов:
Ячейка памяти (или триггер), которая может находиться в двух состояниях: одно из них соответствует символу 0, другое — символу 1. Ячейка памяти имеет один вход и один выход.
Двоичный сумматор, осуществляющий сложение по модулю 2. Сумматор имеет два входа и один выход.
Устройства, составленные из этих элементов, позволяют легко перемножать и делить двоичные многочлены, а это как раз те операции, которые приходится выполнять при использовании циклических кодов.
,82 В качестве первого примера рассмотрим схему, осуществляющую умножение произвольного двоичного многочлена /(X) на многочлен 1+Ха-4-Х3. Эта схема представлена на рис. 14 и состоит всего из трех ячеек памяти и двух сумматоров. Поясним принцип ее работы.
т).
EhrEHJ
Рис. 14.
Первоначально все ячейки памяти содержат нули, а на вход поступают коэффициенты многочлена f(X)=anXn+ Jran_lXn~1Jr. . .+а0, начиная с коэффициентов при старших
-Hih^EHZh]
-4)—*
"п-1
On-;
fS-HZh
ап-2
6)
о '"i^Q7-
3)
a„+o2
ж)
0-rB-
Oo
e)
<±>
¦e
"t
- — Рис. 15,
степенях. Коэффициент ап без изменений передается на выход и запоминается в первой ячейке памяти (рис. 15, а) В следующем такте работы (рис. 15, б) в первую ячейку памяти попадет коэффициент а„_ъ а коэффициент ап
,83 сдвигается в следующую ячейку памяти. При этом на входах первого сумматора окажутся значения ап и ап_и а на выходе — их сумма по модулю 2.
В третьем такте (рис. 15, е) произойдет дальнейший сдвиг коэффициентов в ячейках памяти, а на выходе первого сумматора и всей схемы появится сумма а„_2+й„_1.
На рис. 15, г показано состояние схемы на і-м такте, когда на вход подан коэффициент ?n_,. (i^n).
Последние три такта отражены на рис. 15, д—ж.
Итак, на выходе схемы появится следующая последовательность из п+З коэффициентов:
«„-і+«*: ап-2+ "л-1> й„-з
^n-i+1 ^n-/+з! • • •Ct0а3\ ci0-\-a2', Cil', Ci0, Эта последовательность соответствует многочлену
a^+' + fa^ + aJX»+'+ (*„-, +aa-i)Xa+1 +
+ (an-s + an_2+an)Xn+ . .. + (ап_Ґ + ап_і+1 + + an_i+3)X»-; + s+ ...+(a0+ai + as)X° +
4-(00 + 0*2 + Ci1X + O0.
Непосредственно проверяется, что этот многочлен как раз и есть нужное нам произведение
(апХ* +Ci^1X"-1+ ... +ааХ* + а1Х + а0) (Xs+ X-+ 1).
Аналогично устроена схема умножения на произвольный многочлен
g(X) = gaX» + gn_,X«-1 +... +8lx +g0
над любым полем (рис. 16). В этой схеме ячейки памяти хранят элементы поля F, так что число различных состояний ячеек должно совпадать с числом элементов в F. Ячейки памяти, как это видно из предыдущего описания, не только
