AN-коды

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

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

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

Арифметический вес целого числа $x$ в базе $r$ определяется

w(x)=\min\{t|x=\sum _{i=1}^{t}a_{i}r^{n(i)}\}

^{[ нужна ссылка ]}

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

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

d(x,y)=w(x-y)

^{[ нужна ссылка ]}

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

AN-коды

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

C=\{AN|N\in \mathbb {Z} ,0\leq N

<

B\}

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

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

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

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

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

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

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

Используя модульный вес с $m=r^{n}-1$ , коды AN будут циклическими кодами .

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

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

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

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

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

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

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

Затем,

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

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

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

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

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

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

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

См. также

Ссылки

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

[1] Петерсон, В.В. и Уэлдон, Э.Дж.: Коды, исправляющие ошибки. Кембридж, Массачусетс: MIT Press, 1972.

[2] Мэсси, Дж.Л. и Гарсия, Онтарио: Коды с исправлением ошибок в компьютерной арифметике. В: Достижения в области науки об информационных системах, Vol. 4, гл. 5. (Под редакцией Дж. Т. Тона). Нью-Йорк: Пленум Пресс, 1972.

[3] Дж. Х. Ван Линт (1982). Введение в теорию кодирования. ГТМ. 86. Нью-Йорк: Спрингер-Верлаг.

[4] Кларк, В.Е. и Лян, Дж.Дж.: О модульном весе и циклических несмежных формах для арифметических кодов. IEEE Транс. Информация. Теория, 20 стр. 767-770 (1974).

[1]

[2]

[3]

[4]