8.3. Арифметический вес и арифметическое расстояние

Определим сначала арифметический вес произвольного целого числа Арифметический вес является одним из основных понятий в теории арифметических кодов и играет ту же роль, что и вес Хэмминга в теории алгебраических кодов.

Целое число в двоичной системе счисления всегда может быть представлено единственным образом в следующем виде:

Если разрешить коэффициентам в этом представлении принимать значения 0, 1 и —1, то целое число может быть также представлено в другом виде:

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

Число членов с ненулевыми коэффициентами в минимальном представлении числа называется арифметическим весом числа т. е.

Ниже в данной главе арифметический вес будем называть просто весом.

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

Кроме того, следует заметить, что минимальное представление не однозначно. Например,

где через обозначены символы —1. Имеет место следующая лемма.

Лемма 8.1. Если целое число удовлетворяет условию то во всех минимальных представлениях вида (8.37) числа

Доказательство. Предположим, что представление

числа является минимальным представлением. Если то

Кроме того, если то очевидно, что

Следовательно, в любом из этих случаев

Это означает, что т. е. При этом, если то

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

Из доказательства леммы 8.1 следует, что если в минимальном представлении произвольного числа два соседних коэффициента отличны от нуля, то

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

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

Пример 8.3. Так как 2°, то арифметический вес числа 15 равен 2. Кодовым словом, соответствующим этому числу, является последовательность 1111, вес Хэмминга которой равен 4.

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

Отсюда непосредственно следует, что

Равенство в (8.42) имеет место только при Заметим

Для введенного расстояния выполняется также неравенство треугольника

Действительно,

Как видно из формул (8.41) — (8.43), определяет расстояние в произвольном множестве целых чисел. В этой и следующей главах арифметическое расстояние будем называть просто расстоянием.

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

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

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

Эти причины хорошо иллюстрирует следующий пример.

Пример 8.4. Пусть Эти числа имеют следующие двоичные представления: Расстояние Хэмминга между этими последовательностями равно 6. Если в результате арифметической ошибки в разряде 2° к прибавляется 2° (конфигурация ошибки 000001), то перейдет в Поскольку и то, как следует из приведенных выше

определений арифметического веса и арифметического расстояния, и

что соответствует ошибке в одном разряде.

Если в результате арифметической ошибки в разряде 22 из вычитается 22 (конфигурация ошибки 000100), то переходит в Расстояние Хэмминга между двумя последними последовательностями равно 4, а арифметическое расстояние между 32 и 28 равно

Это соответствует ошибочному вычитанию 22.

Рассмотрим, далее, методы нахождения минимального представления числа Как уже указывалось выше, минимальное представление не единственно. Однако известно, что если в представлении (8.37) никакие два соседних коэффициента одновременно не являются ненулевыми, т. е.

(ниже это условие называется условием то представление (8.37) является минимальным и, более того, единственно [8].

Минимальность и единственность представления, удовлетворяющего условию может быть доказана следующим образом.

Предположим, что представление (8.37) целого числа

удовлетворяет условию а именно

Сначала докажем единственность представления вида (I) заданного целого числа Допустим, что существуют два различных представления числа в виде (1), т. е.

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

где или 1, и

Если равенство (3) не может выполняться. При из равенства (4) следует, что Но тогда, согласно формуле равенства (5) следует, что в этом случае

Очевидно, что при равенство (6) можно получить непосредственно из (5). Таким образом, при равенство (6) справедливо как при так и при При получаем противоречие с равенством (3). Рассмотрим случай Равенства (3) и (6) могут выполняться одновременно только в том случае, если

но это невозможно, поскольку левая часть последнего равенства является целым положительным кратным тогда как правая часть равна Таким образом, если представление, удовлетворяющее условию существует, то оно единственно.

Далее для произвольного целого числа докажем существование представления, удовлетворяющего условию а также минимальность числа

ненулевых коэффициентов в нем. Представим число в виде (1):

и положим

При существование и минимальность этого представления очевидны.

Рассмотрим случай Предположим, что совокупность коэффициентов которые удовлетворяют условию до разряда и найдем совокупность коэффициентов представления (9) числа которые удовлетворяют условию до разряда Совокупность удовлетворяет одному из следующих трех взаимоисключающих условий:

При выполнении равенств (11а) и (11 в) имеют место также следующие два соотношения:

Следовательно,

где индекс, значения которого лежат в области Для каждого из трех возможных случаев, определяемых равенствами (11а), (116) и (11в), соответственно по формулам (116), (13а) и (13в) находим

Очевидно, что при данном методе построения получающаяся совокупность удовлетворяет условию до разряда и при этом

Таким образом, произвольное заданное представ пение (9) при удовлетворяет условию до разряда 2°. Далее, взяв за основу множество и строя с помощью описанной выше процедуры последовательно множества можно найти При этом

меньше соответствующего параметра любого другого множества

Алгоритм нахождения представления, удовлетворяющего условию М

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

и

Так как то, сдвигая правую часть (8.46) на 1 разряд влево и прибавляя получаем

где

Далее, пользуясь тем, что и вычитая (8.46) поразрядно из (8.48), получаем

где

Лемма 8.2. Представление числа задаваемое формулами (8.50) и (8.51), удовлетворяет условию

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

Так как то Следовательно,

так что

Таким образом, как утверждается в лемме 8.2, представление числа удовлетворяет условию следовательно, является минимальным. Число ненулевых слагаемых в этом представлении является весом числа который равен весу числа Действительно, так как является результатом деления на 2, то последовательность, полученная сдвигом представления на один разряд вправо, будет представлением Поскольку то в результате этого преобразования вес не изменяется.

Из этой леммы, кроме всего прочего, непосредственно следует, что 1) число разрядов в минимальном представлении числа, обычное двоичное представление которого имеет разрядов, не превышает и 2) вес двоичного -разрядного числа не превышает

Пример 8.5. Используя лемму 8.2, найдем вес числа Так как то

, следовательно,