Арифметические коды

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

Существуют два вида арифметических кодов.

Арифметическим кодом 1-го вида будем называть код А∙N, где А — контролируемое число, N — модуль. Для таких кодов несколько изменяются понятия «расстояния» и «веса».

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

Если расстояние между двумя числами A1, и А2 равно d, то это означает, что переход от одного числа к другому достигается прибавлением величины d. В этом случае все комбинации чисел, находящиеся между A1, и А2 являются запрещенными. Следовательно, для обнаружения d-кратной ошибки необходимо иметь расстояние не меньше d + 1. Если d = 1, то такой код не сможет обнаруживать ошибок. Величина расстояния для кодов А ∙ N -вида зависит от величин А и N.

Предполагается (и это доказано в теории кодирования), что для любого числа А в системе основания q = 2 существует единственное представление вида

Aq = a_n∙2ⁿ+a_n-1∙2^n-1+…+a₀,

где а_i=±1 или 0, и в котором нет двух соседних коэффициентов, отличных от нуля.

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

Количество разрядов для представления числа А∙N равно log2 (А∙N) = 1оg2 А + 1оg2N, где 1оg2 N — избыточность кода. Таким образом, выбор модуля определяет не только избыточность, но и расстояние. В качестве модуля целесообразно выбирать некоторое взаимно простое с основанием системы q число, превосходящее само основание. Можно положить, что для двоичной системы N = 3, и тогда любой код вида А∙3 будет обнаруживать все одиночные ошибки. Следовательно, минимальная избыточность при произвольном основании определяется как 1оg _q (q +1), т. е. всегда будет требоваться не менее одного, но и не более двух дополнительных разрядов.

Коды с минимальным расстоянием, большим двух, характеризуются величиной М_q (N,d). Величина М_q (N,d) — наименьшее число, дающее при умножении его на N число, вес которого меньше d в представлении по основанию q. Другими словами, если число N имело вес d в представлении по основанию q, то произведение NМ_q(N,d) будет иметь вес меньше d по этому же основанию q.

Если число А изменяется в пределах 0 ≤ А ≤ М_q(N,d), то при любых N и q минимальное расстояние А∙N -кода будет равно по меньшей мере d, что вытекает из определения числа Мq(N, d).

В теории кодирования доказано, что

M₂(N,3)=(2^(N-1)/2+1)/N

Основной способ для отыскания значения N_q — способ непосредственных вычислений.

Кроме А∙N -кодов существуют арифметические коды 2-го рода с большим минимальным расстоянием. Арифметическое расстояние между числами А1 и А2 есть вес их разности, а вес, в свою очередь, определяется количеством ненулевых символов в представлении числа по основанию q. Каждое число имеет каноническую форму представления по основанию 2, т. е. минимальное количество равно 1.

Если N простое число, то 2^N-1 делится на N. Пусть B = (2^N-1-1)/N.

Рассмотрим В∙N -код.

Число знаков в кодовом слове п = N - 1. Возьмем некоторое число l(0≤l<A). Тогда

l∙B=b_n-1∙2^n-1+ b_n-2∙2^n-2+…+b₀

где b_i≡(l∙2^n-1mod A) mod 2.

И действительно: N = 11, В = (1024 - 1)/11 = 93. Если l = 10, то

l ∙ B = 930 = 1∙2⁹ + 1∙2⁸ + 1∙2⁷ + 0∙2⁶ + 1∙2⁵ + 0∙2⁴ + 0∙2³ + 0∙2² + 1∙2¹ + 0∙2⁰.

Проверим коэффициенты b_i по предыдущей формуле:

b₀ ≡ (10∙2¹⁰ mod 11)mod 2 ≡ 0;

b₁ ≡ (10∙2⁹ mod 11)mod 2 ≡ 1;

b₂ ≡ (10∙2⁸ mod 11)mod 2 ≡ 0;

b₃ ≡ (10∙2⁷ mod 11)mod 2 ≡ 0;

b₄ ≡ (640 mod 11)mod 2 ≡ 0;

b₅ ≡ (320 mod 11)mod 2 ≡ 1;

b₆ ≡ (160 mod 11)mod 2 ≡ 0;

b₇ ≡ (80 mod 11)mod 2 ≡ 1;

b₈ ≡ (40 mod 11)mod 2 ≡ 1;

b₉ ≡ (20 mod 11)mod 2 ≡ 1;

Итак, десятичное число 10 в двоичном представлении имеет вид 1010, в A∙ N -коде будет иметь вид 1101110, а в В∙N -коде при N = 11, В = 93 число 10 будет представлено в виде 1110100010.

При использовании В∙N -кода коэффициенты bi можно вычислять сразу же, не раскладывая числа в многочлен bi≡(l∙2n-1mod A) mod 2; п = N - 1 известно заранее, так как В = (2^N-1 - 1)/N вычисляется через N.

Таким образом, при изображении числа l в В∙N -коде половина знаков равна единице, а половина — нулю. Это следует из выражения

b_i≡(l∙2^n-1mod N) mod 2

так как 2 и N взаимно простые числа, значит, остатки от деления чисел 2i на N — целые числа от 1 до N - 1. Так как число N — нечетное, количество остатков — всегда четное число, а значит половина из остатков числа нечетные, а половина — четные числа. Следовательно, половина остатков по mod 2 дает единицу, а половина — нуль.

Арифметический вес числа в В∙N -коде равен (N-1)/3, или (N + 1)/3 в зависимости от того, какое из этих чисел целое (N > 3).

В случае В∙N -кодов по известному N можно не только определить количество символов и их вид, но и заранее определять арифметическое расстояние, что непосредственно влияет на корректирующие способности кода.

Существуют еще самодополняющиеся (А∙N + В) коды. В этом случае код для дополнительного числа N — дополнительный код самого числа А.

Если числа, которые кодируются, имеют основание b, то дополнение для числа А будет (b - 1 - А). Дополнение же числа A∙N при представлении его по основанию q равно qⁿ -1 - A∙N:

qⁿ – 1 – (A∙N + B) = N(b – 1 – A) + B,

дополнение кодового числа код дополнительного числа

В = [qⁿ – 1 – N(b – 1)]/2

Код возможен только при целых В.

Расстояния для (А ∙ N + В) кода те же, что и для А ∙ N -кода.

В современных вычислительных машинах используется контроль на четность и нечетность. Этот контроль позволяет лишь зафиксировать наличие ошибки, но не позволяет ее исправить. Но он нашел широкое применение благодаря своей простоте, так как и наличие информационной избыточности требует применения контрольной аппаратуры, которая может оказаться слишком объемной, труднореализуемой. Например, в случае самодополняющихся (A∙N + В) -кодов необходимо умножить число на N, где N — простое число, прибавить В; для представления четырехзначных чисел по величине используют восемь разрядов, помимо этого приходится осуществлять коррекцию (ввод поправок) при сложении, затем сравнение полученных комбинаций с эталонными, а далее проводить исправление ошибок, если такие имеются. Но и (A∙N + В) -коды не всегда позволяют определить точное местоположение ошибки.

Проиллюстрируем вышесказанное на примере сложения двух чисел А₁ и А₂.

+

A₁ = 0110 0011

A2 = 0111 0110

-

1100 1001

0010 1010

1001 1111 1010 1111 — ближайшая разрешенная комбинация

несовпадение в

двух разрядах

Ошибка может быть либо в 5-м, либо в 6-м разрядах:

а) 1110 1001

0010 1010

1011 1111 — запрещенная комбинация

б) 1101 1001

0010 1010

10101111 — соответствует эталонной комбинации

Необходима специальная система для распознавания возможности пе­реноса.

+

1100 0010

0110 0011

-

1010 0101 — переноса не произошло

0010 1010

0111 1011 вся комбинация запрещенная, отличается от разрешенных

на три разряда

Если же делать коррекцию ошибки, используя сложение с перено­сом, то:

+

1100 0010

0110 0011

1010 0101

0001 0010

+

1001 0011 местоположение ошибки можно обнаружить

0010 1010

1011 1101
0011 1101

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

Дата добавления: 2014-01-06