13.2. AN-коды

Рассмотрим теперь код, в котором число представляется в виде AN, где постоянная величина. Заметим, что

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

Если основание входит в число А в качестве множителя, то входит в качестве множителя также в каждое закодированное число AN. В этом случае в представлении чисел по основанию цифра, соответствующая низшему разряду, будет всегда равна 0 и поэтому будет бесполезной. Аналогично если не являются взаимно простыми, то в младших разрядах некоторые цифры никогда не появятся. Это не желательно, и поэтому будет предполагаться, что взаимно просты,

Интересна аналогия с циклическими кодами. В AN-коде некоторое число является кодовым, т. е. закодированной формой некоторого другого числа, тогда и только тогда, когда оно делится на А и не выходит из рассматриваемой области чисел. Многочлен определяет кодовый вектор циклического кода, порожденного многочленом тогда и только тогда, когда он делится на и степень его меньше, чем

Число знаков, требуемое для представления в системе исчисления по основанию равно наименьшему целому числу, превосходящему Число знаков, требуемых для представления равно наименьшему целому числу, не меньшему, чем

Величина будет называться избыточностью кода; число избыточных символов, требуемых для представления числа AN, отличается от величины меньше, чем на 1.

Пример. В -коде при избыточность равна бит. Все числа меньшие, чем могут быть записаны при помощи 9 двоичных знаков. Для того чтобы записать числа при всех меньших 29, в двоичной форме требуется 14 знаков. Таким образом, действительно, необходимо 5 избыточных знаков.

В 3N-коде при избыточность равна бит. Если -код используется для двоичного представления десятичных цифр, то Чтобы представить в двоичной форме все числа, меньшие 10, требуется 4 двоичных знака. Только 5 двоичных знаков требуется для того, чтобы представить в двоичной форме числа вида 37V, и, таким образом, здесь действительно необходим только один избыточный вэичный знак.

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

где Для того чтобы добиться выполнения этого условия, в качестве А следует выбрать взаимно простое с число, превосходящее В частности, всегда можно положить -код будет обнаруживать любую одиночную ошибку в двоичном представлении, а -код—любую одиночную ошибку в десятичном представлении чисел. Следовательно, для обнаружения одной

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

Коды с минимальным расстоянием, большим 2, удобнее всего характеризовать величиной определяемой как наименьшее число, вес произведения которого на А меньше, чем в представлении по основанию

Теорема 13.1. Если изменяется в области или в области — то при любых минимальное расстояние AN-кода равно по меньшей мере

Доказательство. Если числа А, и одновременно принадлежат одной из областей, указанных в условии теоремы, то и Следовательно, по определению величины вес разности больше, чем

За исключением результатов теоремы 13.3, излагаемой ниже, неизвестно никаких способов определения величины кроме непосредственного вычисления. Некоторые значения этой величины перечислены в табл. 13.1 для наиболее интересных случаев или

Теорема 13.2. Минимальное расстояние двоичного AN-кода равно 3 для всех значений в области (или в области тогда и только тогда, когда вычеты чисел по модулю А различны и отличны от нуля для всех У, при которых

Доказательство. Если все вычеты различны, то вычет числа, вес которого равен 2, т. е. числа вида не может быть нулем, и поэтому это число не может быть разностью двух кодовых чисел. Аналогично вес разности не может быть единицей или нулем (если только не равно следовательно, минимальный вес должен быть равен по меньшей мере трем. Если, с другой стороны, при некотором выборе значений и знаков вычеты чисел совпадают, то вычет их разности D равен О, так что разность представима в виде AN. Вес ее равен 2. В указанной в условии теоремы области должны найтись два числа

Таблица 13.1 (см. скан) Некоторые двоичные AN-коды

и удовлетворяющих равенству следовательно, минимальный вес равен самое большее двум. Если вычет числа равен 0, то, как легко показать, минимальное расстояние равно 1. Ч. т. д.

Теорема 13.3. Если А — нечетное простое число и если 2 — примитивный элемент поля целых чисел по модулю А, то

Если элемент —2, но не 2, примитивен по модулю А, то

Наоборот, если выполняется равенство 13.5, то А—простое число, примитивный элемент по модулю А, а если выполняется равенство 13.6, то А — простое число и элемент —2, но не 2, примитивен. (Замечание: в первом случае оба элемента —2 и 2 могут быть примитивными. В последнем случае число А имеет вид

Доказательство. Если А — простое число, то

откуда

Если 2 — примитивный элемент по модулю А, то так как то или Тогда все вычеты по модулю А степеней числа 2 равны

или

Поэтому из теоремы 13.2 следует (13.5). Если 2 — примитивный элемент и А — простое число, то все вычеты по модулю А. При этом элементы

будут все различны, так как различны их квадраты

Кроме того, среди них не может быть числа, равного —1, так как если по модулю А для некоторого то по модулю А для некоторого удовлетворяющего неравенству Но это невозможно, потому что, по предположению, —-примитивный элемент. Снова по модулю А. Если четное число, то откуда Величина должна делиться на порядок элемента 2, и, кроме того, порядок элемента 2 должен быть больше, чем поскольку все вычеты чисел 2 при различны. Следовательно, порядок элемента 2 должен быть равен , и 2 — примитивный элемент. В этом случае выполняется соотношение (13.5).

Если, с другой стороны, —2 — примитивный элемент, непримитивный элемент, то число должно быть нечетным. Так как то и вычеты равны

Поэтому в соответствии с теоремой 13.2 справедливо соотношение (13.6),

Из теоремы 13.2 следует, что если выполняется соотношение (13.5), то все вычеты должны быть различными. Так как существует всего вычетов, то ненулевые вычеты должны все исчерпываться различными положительными целыми числами, не превосходящими А. Далее, так как число 2 и, следовательно, все степени этого числа взаимно просты с то вычеты также взаимно просты с А. Следовательно, А—простое число, а вычеты образуют поле из А элементов. В таком случае ненулевые вычеты образуют мультипликативную группу. Порядок числа 2 равен по меньшей мере

поскольку вычеты всех меньших степеней числа 2, по предположению. различны. Но порядок группы должен делиться нацело на порядок числа 2, и. следовательно, порядок элемента 2 должен быть равен либо , либо То же самое верно для числа —2. В соответствии с утверждением теоремы 6.20 группа является циклической. Предположим, что а — примитивный элемент. Если порядок элементов равен то оба они должны быть четными степенями а, поскольку только в том случае, когда делится на . Поэтому вычеты всех степеней элементов должны быть четными степенями а. Мы пришли к противоречию, так как половина вычетов является нечетными степенями а и все вычеты получаются как вычеты степеней элементов Следовательно, по крайней мере один из двух элементов должен быть примитивным. Ч. т. д.

Коды, описываемые теоремой 13.3, аналогичны совершенным кодам, исправляющим одну ошибку, Код, используемый для кодирования чисел из области (или — должен обладать способностью различать каждую из возможных ошибок и правильное кодовое число, т. е. всего возможностей. Утверждение теоремы 13.2 сводится к тому, что каждой из этих возможностей соответствует отличный от других вычет, откуда следует, что . В теореме 13.3 приводятся условия, необходимые и достаточные для того, чтобы выполнялось точное равенство. Отметим сходство найденных результатов и соответствующих результатов для циклических кодов. В -коде не только должно быть простым число но, кроме того, 2 должно быть примитивным элементом. В случае двоичного циклического кода Хэмминга порождающий многочлен кода не только должен быть неприводимым, но, кроме того, корни его должны быть примитивными элементами.

Все коды с расстоянием, равным 3, перечисленные в табл. 13.1, являются кодами, удовлетворяющими условиям теоремы 13.3.