8.4. Минимальное расстояние и корректирующая способность AN-кода

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

Пусть целое число, совпадающее с кодовым числом AN при отсутствии ошибок и, быть может, отличающееся от AN при наличии ошибок. Например, может быть выходом сумматора, суммы на выходе которого в отсутствие ошибок являются кодовыми числами -кода. В этом случае

где целое число, называемое ошибкой. Если то называется ошибкой веса

Минимальное расстояние кода — это по определению минимальное значение расстояния между различными кодовыми числами. Точнее, минимальное расстояние -кода, который

сопоставляет числам кодовые числа определяется следующим образом:

Теорема -код исправляет все ошибки веса и менее тогда и только тогда, когда его минимальное расстояние не меньше чем -код может обнаруживать все ошибки веса и менее тогда и только тогда, когда его минимальное расстояние не меньше чем

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

то по всегда можно однозначно восстановить Верно и обратное; в самом деле, из формул (8.54) и (8.40) имеем

Следовательно, условие является достаточным для того, чтобы мог исправлять все ошибки веса и менее. Наоборот, если допустить, что то число будет иметь минимальное представление веса 21 или менее. Пусть сумма ненулевых членов высших разрядов этого минимального представления, а сумма оставшихся членов этого представления. Вес определенных таким образом ошибок не превосходит удовлетворяют равенству (8.54). Следовательно, они не могут быть исправлены.

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

Вторая часть теоремы доказывается точно так же, как и первая.

Аналогично можно доказать, что -код может исправлять ошибки веса и менее и одновременно обнаруживать ошибки веса и менее тогда и только тогда, когда его минимальное расстояние не меньше чем

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

подтверждают сделанное в примере 8.4 и ранее утверждение о том, что арифметический вес, арифметическое расстояние и минимальное расстояние являются понятиями, которые играют в теории арифметических кодов очень важную роль.

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

Доказательство. Пусть и различные кодовые числа. Так как то число также удовлетворяет неравенству Следовательно, ненулевое кодовое число и

Наоборот, вес любого ненулевого кодового числа совпадает с расстоянием между и кодовым числом

Еще одной важной характеристикой -кодов является параметр который определяется следующим образом:

Непосредственным следствием теоремы 8.2 является следующее утверждение.

Утверждение -код для которого имеет минимальное расстояние

Пример 8.6. Если то Действительно,

Таким образом, минимальное расстояние AN-кода, описанного в примере равно 3, и, следовательно, согласно теореме 8.1, он может исправлять любые ошибки веса 1.

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

(см. скан)

арифметических кодов. Эта проблема полностью решена только при Соответствующее решение приводится в разд. 8.5. За исключением этого частного случая, общих методов вычисления которые требовали бы небольшого числа операций, нет. В табл. 8.9 приведено несколько примеров -кодов.