5. Равновесные коды

Равновесными принято называть коды, каждая комбинация которых содержит одно и то же число отличных от нуля символов. Простейшие из них, так называемые двоичные биортогональные коды, имеют вид

(VIII.5.1)

(к каждой комбинации безызбыточного кода дописывается комбинация, отличающаяся от нее точно в позициях). Легко видеть, что любая комбинация (VIII.5.1) содержит точно единиц, а . В биортогональных кодах обнаруживаются все ошибки, кроме ошибок, приводящих одновременно к трансформации одинакового числа нулей и единиц. Задача синтеза кодирующих и декодирующих устройств здесь не встречает трудностей.

Максимальное число -значных комбинаций веса равно

(VIII.5.2)

Такие множества также представляют собой равновесные (сочетательные) коды. (Эти коды, как правило, нелинейные). В бинарном случае их комбинации отличаются не менее чем в двух позициях, а для , кодовое расстояние 1.

Поставим перед собой задачу найти линейные преобразования комбинаций веса в -значные комбинации веса отличающиеся между собой не менее чем в d позициях.

Выделим из множества всевозможных линейных форм, определенных над данным полем относительно независимых переменных, подмножество форм таких, которые зависят только от независимых переменных:

(VIII.5.3)

где

(VIII.5.4)

Например, если ,,, то содержит 12 линейных форм:

(VIII.5.5)

Линейные формы множества имеют вид

(VIII.5.6)

Пусть -значная комбинация, содержащая г отличных от нуля символов, преобразована в -значную комбинацию с помощью линейных операций (VIII.5.3). Вес последней равен [57]

(VIII.5.7)

где

(VIII.5.8)

Вывод формул (VIII.5.7),(VIII.5.8) основывается на симметрии множества относительно номеров независимых переменных (если существует определенная линейная форма относительно каких-либо i независимых переменных, то существует точно такая же линейная форма относительно совокупности i любых других независимых переменных). В силу этого же обстоятельства выражение (VIII.5.7) при фиксированном i зависит только от , следовательно, после преобразований любой комбинации веса образуется комбинация веса .

Число комбинаций в таком равновесном коде определяется соотношением (VIII.5.2), а кодовое расстояние удовлетворяет условию

(VIII.5.9)

где

(VIII.5.10)

[комбинации веса являются лишь подмножеством комбинаций линейного кода (VIII.5.3) с кодовым расстоянием d, в нашем случае равным (VIII.5.10).

Пример. Пусть , и , тогда множество содержит десять линейных форм:

(VIII.5.11)

Для бинарных кодов

(VIII.5.12)

см. (VIII.5.8)

Поэтому в рассматриваемом случае

(VIII.5.13)

В табл. VIII.3 приведены значения и для =1, 2, 3, 4, 5, рассчитанные по (VIII.5.13).

Таблица VIII.3

Таким образом, если подвергнуть преобразованию (VIII.5.11) все пятизначные комбинации веса 1 и 2, то образуется 15 десятизначных комбинаций веса 5, отличающихся друг от друга не менее чем в четырех позициях. Если тем же преобразованиям подвергнуть комбинации веса 3 и 4, то вес комбинаций окажется равным четырем при .

Выделим из множества подмножество попарно линейно независимых форм:

(VIII.5.14)

где, как легко заметить,

(VIII.5.15)

Так, например, из множества (VIII.5.5) можно выделить подсистему попарно линейно независимых форм:

(VIII.5.16)

а из множества (VIII.5.6):

(VIII.5.17)

Для подмножество совпадает с . Из простых соображений ясно, что линейное преобразование (VIII.5.14) превращает -значную комбинацию веса в -значную комбинацию веса

(VIII.5.18)

см. (VIII.5.7)-(VIII.5.8)

Выражение (VIII.5.18), так же как и (VIII.5.7), при фиксированном i зависит лишь от . Следовательно, линейные формы (VIII.5.14) позволяют построить равновесный код с числом комбинаций (VIII.5.2) и кодовым расстоянием d, удовлетворяющим условию

(VIII.5.19)

где теперь

Пример. Определим величины для троичного кода

(VIII.5.17). Прежде всего вычислим значение . Из (VIII.5.8) при мы имеем

(VIII.5.20)

Выражение (VIII.5.18) теперь запишется так:

(VIII.5.21)

Из этой формулы следует, что если преобразованию (VIII.5.17) подвергаются трехзначные комбинации веса 1, 2, 3, то образуются четырехзначные комбинации веса 4, 2, 3 соответственно, причем .

Кстати отметим, что в случае, когда представляет собой подмножество попарно линейно независимых форм, каждая из которых зависит одновременно от всех независимых переменных ,

(VIII.5.22)

и

(VIII.5.23)

Выражение (VIII.5.23) имеет минимум при , так как его второе слагаемое уменьшается с ростом и принимает отрицательное значение, когда — число четное.

Таким образом,

(VIII.5.24)

В заключение отметим, что для построения равновесных линейных кодов успешно может применяться метод объединения. При этом следует руководствоваться следующим очевидным положением.

Теорема VIII.2. Если -значная комбинация веса преобразована в -значную комбинацию с помощью линейных форм, представляющих собой объединение подмножеств

(VIII.5.25)

(VIII.5.26)

наконец,

(VIII.5.27)

В этих соотношениях , когда совпадает с , см. (VIII.5.4) и (VIII.5.7)-(VIII.5.8);,а ,когда совпадает с см. (VIII.5.15) и (VIII.5.18)

Для бинарных кодов с от 5 до 10 величины (VIII.5.25)-(VIII.5.27) можно вычислить на основе табл. VIII.4, где приведены значения и (верхняя строка).

Таблица VIII.4

Таблица VIII.4 (продолжение)