AN-коды

Коды AN ^[1] представляют собой коды с исправлением ошибок , которые используются в арифметических приложениях. Арифметические коды обычно использовались в компьютерных процессорах для обеспечения точности арифметических операций, когда электроника была более ненадежной. Арифметические коды помогают процессору обнаружить ошибку и исправить ее. Без этих кодов процессоры были бы ненадежны, поскольку любые ошибки остались бы незамеченными. Коды AN — это арифметические коды, названные в честь целых чисел и используемые для кодирования и декодирования кодовых слов. ${\displaystyle A}$ ${\displaystyle N}$

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

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

Арифметический вес целого числа по основанию определяется формулой ${\displaystyle x}$ ${\displaystyle r}$

${\displaystyle w(x)=\min\{t|x=\sum _{i=1}^{t}a_{i}r^{n(i)}\}}$^{[ нужна цитата ]}

где < , , и . Арифметическое расстояние слова ограничено сверху его весом Хэмминга, поскольку любое целое число может быть представлено в его стандартной полиномиальной форме, где - это цифры целого числа. Удаление всех условий, где будет моделироваться вес , равный его весу Хэмминга. Арифметический вес обычно будет меньше веса Хэмминга, поскольку он может быть отрицательным. Например, двоичное целое число имеет вес Хэмминга . Это быстрая верхняя граница арифметического веса, поскольку . Однако, поскольку может быть отрицательным, мы можем написать что делает арифметический вес равным . ${\displaystyle |{a_{i}}|}$ ${\displaystyle r}$ ${\displaystyle n(i)\geq 0}$ ${\displaystyle r,n(i)\in \mathbb {Z} }$ ${\displaystyle x=\sum _{i=1}^{n}b_{i}r^{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle b_{i}=0}$ ${\displaystyle t}$ ${\displaystyle a_{i}}$ ${\displaystyle x=29}$ ${\displaystyle 11101}$ ${\displaystyle 4}$ ${\displaystyle x=2^{0}+2^{2}+2^{3}+2^{4}}$ ${\displaystyle a_{i}}$ ${\displaystyle x=2^{5}-2^{1}-2^{0}}$ ${\displaystyle 3}$

Арифметическое расстояние между двумя целыми числами определяется выражением

${\displaystyle d(x,y)=w(x-y)}$^{[ нужна цитата ]}

Это одна из основных метрик, используемых при анализе арифметических кодов. ^{[ нужна цитата ]}

AN-коды

Коды AN определяются целыми числами и используются для кодирования целых чисел от до так, что ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle 0}$ ${\displaystyle B-1}$

${\displaystyle C=\{AN|N\in \mathbb {Z} ,0\leq N}$< ${\displaystyle B\}}$

Каждый выбор приведет к получению другого кода, но при этом служит ограничивающим фактором для обеспечения полезных свойств на расстоянии кода. Если оно слишком велико, в код может попасть кодовое слово с очень малым арифметическим весом, что ухудшит расстояние всего кода. Чтобы использовать эти коды, перед выполнением арифметической операции над двумя целыми числами каждое целое число умножается на . Пусть результатом операции над кодовыми словами будет . Обратите внимание, что для правильного декодирования он также должен находиться между to . Чтобы декодировать, просто разделите . Если не является фактором , то произошла по крайней мере одна ошибка и наиболее вероятным решением будет кодовое слово с наименьшим арифметическим расстоянием от . Как и в случае с кодами, использующими расстояние Хэмминга, коды AN могут исправлять ошибки вплоть до ошибок, где расстояние кода. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle 0}$ ${\displaystyle B-1}$ ${\displaystyle R/A}$ ${\displaystyle A}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle \lfloor {\frac {d-1}{2}}\rfloor }$ ${\displaystyle d}$

Например, код AN с , операция сложения и начнется с кодирования обоих операндов. Это приводит к операции . Затем, чтобы найти решение, мы делим . Пока > , это будет возможная операция в коде. Предположим, ошибка возникает в каждом из двоичных представлений операндов, таких, что и , то . Обратите внимание, что, поскольку , вес Хэмминга между полученным словом и правильным решением определяется только после ошибок. Для вычисления арифметического веса возьмем который можно представить как или . В любом случае арифметическое расстояние соответствует ожидаемому, поскольку оно представляет собой количество допущенных ошибок. Чтобы исправить эту ошибку, будет использоваться алгоритм вычисления ближайшего к полученному слову кодового слова с точки зрения арифметического расстояния. Подробно алгоритмы описывать не будем. ${\displaystyle A=3}$ ${\displaystyle 15}$ ${\displaystyle 16}$ ${\displaystyle R=45+48=93}$ ${\displaystyle 93/3=31}$ ${\displaystyle B}$ ${\displaystyle 31}$ ${\displaystyle 45=101101\rightarrow 101111}$ ${\displaystyle 48=110000\rightarrow 110001}$ ${\displaystyle R=101111+110001=1100000}$ ${\displaystyle 93=1011101}$ ${\displaystyle 5}$ ${\displaystyle 2}$ ${\displaystyle 1100000-1011101=11}$ ${\displaystyle 11=2^{0}+2^{1}}$ ${\displaystyle 11=2^{2}-2^{0}}$ ${\displaystyle 2}$

Чтобы гарантировать, что расстояние кода не будет слишком маленьким, мы определим модульные AN-коды. Модульный AN-код является подгруппой , где . Коды измеряются в терминах модульного расстояния, которое определяется в терминах графа, вершины которого являются элементами . Две вершины и соединены тогда и только тогда, когда ${\displaystyle C}$ ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ ${\displaystyle m=AB}$ ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ ${\displaystyle x{\pmod {m}}}$ ${\displaystyle x'{\pmod {m}}}$

${\displaystyle x-x'\equiv \pm c\cdot r^{j}{\pmod {m}}}$

где и < < , . Тогда модульное расстояние между двумя словами — это длина кратчайшего пути между их узлами в графе. Модульный вес слова – это его расстояние от которого равно ${\displaystyle c,j\in \mathbb {Z} }$ ${\displaystyle 0}$ ${\displaystyle c}$ ${\displaystyle r}$ ${\displaystyle j\geq 0}$ ${\displaystyle 0}$

${\displaystyle w_{m}(x)=min\{w(y)|y\in \mathbb {Z} ,y\equiv x{\pmod {m}}\}}$

На практике значение обычно выбирается таким образом, чтобы, поскольку большая часть компьютерной арифметики выполняется , не было дополнительных потерь данных из-за выхода кода за пределы границ, поскольку компьютер также будет за пределами границ. Выбор также имеет тенденцию приводить к получению кодов с большими расстояниями, чем у других кодов. ${\displaystyle m}$ ${\displaystyle m=r^{n}-1}$ ${\displaystyle \mod 2^{n}-1}$ ${\displaystyle m=r^{n}-1}$

При использовании модульного веса коды AN будут циклическими кодами . ${\displaystyle m=r^{n}-1}$

определение : Циклический код AN — это код , который является подгруппой , где . ${\displaystyle C}$ ${\displaystyle [r^{n}-1]}$ ${\displaystyle [r^{n}-1]=\{0,1,2,\dots ,r^{n}-1\}}$

Циклический AN-код является главным идеалом кольца . Есть целые числа и где и удовлетворяют определению кода AN. Циклические AN-коды представляют собой подмножество циклических кодов и обладают теми же свойствами. ${\displaystyle [r^{n}-1]}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle AB=r^{n}-1}$ ${\displaystyle A,B}$

Коды Мандельбаума-Бэрроуза

Коды Мандельбаума-Бэрроуза представляют собой тип циклических AN-кодов, введенных Д. Мандельбаумом и Дж. Т. Барроузом. ^{[2] [3]} Эти коды создаются путем выбора простого числа, которое не делится, например , и , и . Пусть будет положительным целым числом, где и . Например, выбрав , и результатом будет код Мандельбаума-Бэрроуза, такой, что < в base . ${\displaystyle B}$ ${\displaystyle r}$ ${\displaystyle \mathbb {Z} /B\mathbb {Z} }$ ${\displaystyle r}$ ${\displaystyle -1}$ ${\displaystyle m=r^{n}-1}$ ${\displaystyle n}$ ${\displaystyle r^{n}\equiv 1{\pmod {B}}}$ ${\displaystyle A=(r^{n}-1)/B}$ ${\displaystyle r=2,B=5,n=4}$ ${\displaystyle A=(r^{n}-1)/B=3}$ ${\displaystyle C=\{3N|N\in \mathbb {Z} ,0\leq N}$ ${\displaystyle 5\}}$ ${\displaystyle 2}$

Для анализа расстояния кодов Мандельбаума-Бэрроуза нам понадобится следующая теорема.

Теорема : Пусть циклический AN-код с генератором и ${\displaystyle C\subset [r^{n}-1]}$ ${\displaystyle A}$

${\displaystyle B=|C|=(r^{n}-1)/A}$

Затем,

${\displaystyle \sum _{x\in C}w_{m}(x)=n(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )}$

Доказательство : предположим, что каждый из них имеет уникальное циклическое представление NAF ^[4] , которое ${\displaystyle x\in C}$

${\displaystyle x\equiv \sum _{i=0}^{n-1}c_{i,x}r^{i}{\pmod {r^{n}-1}}}$

Мы определяем матрицу с элементами где и . Эта матрица по сути представляет собой список всех кодовых слов, в котором каждый столбец является кодовым словом. Поскольку матрица циклична, каждый столбец матрицы имеет одинаковое количество нулей. Теперь мы должны вычислить , что в разы превышает количество кодовых слов, которые не заканчиваются на . Как свойство находиться в циклическом NAF, если существует с < . Поскольку при < , то < . Тогда число целых чисел, последним битом которых является ноль, равно . Умножение этого значения на символы в кодовых словах дает нам сумму весов кодовых слов по желанию. ${\displaystyle n\times B}$ ${\displaystyle c_{i,x}}$ ${\displaystyle 0\leq i\leq n-1}$ ${\displaystyle x\in C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle n|\{x\in C|c_{n-1,x}\neq 0\}|}$ ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle c_{n-1,x}\neq 0}$ ${\displaystyle y\in \mathbb {Z} }$ ${\displaystyle y\equiv x{\pmod {r^{n}-1}},{\frac {m}{r+1}}}$ ${\displaystyle y\leq {\frac {mr}{r+1}}}$ ${\displaystyle x=AN{\pmod {r^{n}-1}}}$ ${\displaystyle 0\leq N}$ ${\displaystyle B}$ ${\displaystyle {\frac {B}{r+1}}}$ ${\displaystyle N\leq {\frac {Br}{r+1}}}$ ${\displaystyle \lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor }$ ${\displaystyle n}$ ${\displaystyle n(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )}$

Теперь мы будем использовать предыдущую теорему, чтобы показать, что коды Мандельбаума-Бэрроуза эквидистантны (что означает, что каждая пара кодовых слов имеет одинаковое расстояние) с расстоянием

${\displaystyle {\frac {n}{B-1}}(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )}$

Доказательство : Пусть , то и не делится на . Это подразумевается там . Затем . Это доказывает, что оно равноудалено, поскольку все кодовые слова имеют тот же вес, что и . Поскольку все кодовые слова имеют одинаковый вес и по предыдущей теореме мы знаем общий вес всех кодовых слов, расстояние кода находится путем деления общего веса на количество кодовых слов (исключая 0). ${\displaystyle x\in C,x\neq 0}$ ${\displaystyle x=AN{\pmod {r^{n}-1}}}$ ${\displaystyle N}$ ${\displaystyle B}$ ${\displaystyle \exists j(N\equiv \pm r^{j}{\pmod {B}})}$ ${\displaystyle w_{m}(x)=w_{m}(\pm r^{j}A)=w_{m}(A)}$ ${\displaystyle C}$ ${\displaystyle A}$

Смотрите также

• Обнаружение и исправление ошибок
• Прямое исправление ошибок

Рекомендации

1. Петерсон, В.В. и Уэлдон, Э.Дж.: Коды, исправляющие ошибки. Кембридж, Массачусетс: MIT Press, 1972.
2. Мэсси, Дж.Л. и Гарсия, Онтарио: Коды с исправлением ошибок в компьютерной арифметике. В: Достижения в области науки об информационных системах, Vol. 4, гл. 5. (Под редакцией Дж. Т. Тона). Нью-Йорк: Пленум Пресс, 1972.
3. Дж. Х. Ван Линт (1982). Введение в теорию кодирования. ГТМ. 86. Нью-Йорк: Спрингер-Верлаг.
4. Кларк, В.Е. и Лян, Дж.Дж.: О модульном весе и циклических несмежных формах для арифметических кодов. IEEE Транс. Информация. Теория, 20 стр. 767-770 (1974).