авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 | 4 |

«ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Левченко, Александр Юрьевич Разработка нейронных моделей для коррекции ...»

-- [ Страница 2 ] --

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

где лг;

= 0,1;

а,- = 0,± 1;

О / w и - 2 " А" 2". (По определению, х,- = а,- = О для /0.) В общем случае целое число можно представить не единственным набором коэффициентов а^. Пусть Тогда среди всех наборов коэффициентов а,, которыми можно представить любое данное целое число X, должен существовать, по крайней мере, один набор, для которого является минимальным. Модифицированное Т представление с минимальным Т будем называть минимальной формой числа. Условие минимальности можно записать как йг,д,ч.1 = 0, 0 / я - 1. (1.3.1.1) Последнее условие требует, чтобы в модифицированном представлении не было расположенных подряд ненулевых символов. Следующие две леммы, принадлежащие Рейтвизнеру, утверждают существование и единственность двоичной минимальной формы.

Теорема 1.3.1.1. Любое целое число имеет единственную двоичную минимальную форму.

Теорема 1.3.1.2. Для любого целого числа существует, по крайней мере, одна (а следовательно, единственная) двоичная минимальная форма.

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

0/и, х„+1=х„, x^i=r_i =0.

Для отказа от рекурсии при определении /, Рейтвизнер рассмотрел другой подход:

Гу=1,если YJ IjYt, rj=O, если О /у Yj или Yj' Ij 2-'*^, где 0Jn, /= /= т.е.

и Простой метод получения минимальной формы числа предложен Цзао-У и Чжаном [128]. Он описывается в следующей теореме.

«-1. /J+ Теорема 1.3.1.3. Пусть /=Х«/2' и 3 / = б ;

2 ' - положительные целые /=о »=о числа в обычном двоичном представлении (а,-,6,-=0,1 и а^-х^О). Тогда и преставление числа / в виде X^y+i^'j где di=bi-ai (т.е. t/,=l, если biai'.

/=о di =-1, если bi а,-;

/,=0, если 6,- =«,), является минимальной формой этого числа.

Пример. Пусть 7 = 93 (в двоичном представлении 7 = 1011101). Число 37 = 279 можно получить как 27 + 7, т.е.

+ 1011101.

Далее определим с помощью поразрядного вычитания 31-1 = 21:

_ 1011101.

(Как и ранее символ а обозначает -а.) Представление 7 = 10100101 является минимальной формой числа /.

Месси и Гарсиа [118] указали на прямые следствия теоремы 1,3.1.3.

Следствие 1.3.1.1. Минимальную форму числа - / можно получить из минимальной формы числа / изменением знаков всех коэффициентов в последней на противоположные.

Следствие 1.3.1.2. Для записи двоичной минимальной формы п разрядного двоичного числа требуется не более п + 1 разрядов.

Для получения минимальной формы числа Гото и Фукумура [107] предложили использовать метод двоичного деления без восстановления остатка, при котором нет необходимости в предварительном преобразовании чисел в двоичный вид. Пусть делитель В — нечетное целое число и делимое а - целое число из интервала [1,5-1]. Па каждом /-м шаге деления (/ = 0,1,...) определяются очередной остаток г- и цифра частного qi в соответствии со, следующими правилами:

(О,если -25/3 Г;

25/3, еслм 25/3г,-45/3, [-1,если-4В/3Г1-2В/3.

Так как В - нечетное число, то частное alB представляет собой бесконечную (и заметим, периодическую) последовательность двоичных цифр О, I и - для которой выполняется условие минимальности q',^/+i =0. Действительно, если 9/=±lj то г,ч.1 принадлежит полуинтервалу (-25/3,25/3] и, следовательно, qr,+, = О.

Перейдем к изучению канонических представлений для случая произвольного основания г позиционной системы счисления. Как и в двоичной системе счисления, каждое положительное целое число Л имеет ^ единственное представление вида N=Y,airi, 0air.

j= Представление числа Л'^ вида j= будем называть модифицированным г-ичным представлением. По-прежнему нас будут интересовать модифицированные представления с минимальным количеством коэффициентов. Кларк и Лян [101] предложили рассматривать два условия, которым должна удовлетворять минимальная г-ичная форма:

( + 6,+11 г для всех /, (1.3.1.2) iI |б,+,I, если 6,-6,+1 0. (1.3.1.3) Существование минимальной формы доказывает Теорема 1.3.1.4. Пусть /^=Е^0 ~ минимальная форма числа Л'^ с и пусть произвольное модифицированное N = Yj^ir /=0 /о =.ТогдаГ, Гй.

представление числа N с Tc = г /= (Здесь и далее \х\ - наименьшее целое, не меньшее д:.) Следуюш;

ая теорема доказывает единственность минимальной формы с условиями (1.3.1.2), (1.3.1.3) для заданного числа Л''.

Теорема 1.3.1.5. Если для положительного целого числа N /=o j= являются минимальными формами, то bP = bj^^ для всех /.

Кларк и Лян [101] обобщили также метод получения минимальной формы, принадлежащий Цзао-У и Чжану.

Теорема 1.3.1.6. Пусть N=^,^1^1 - г-ичное представление числа Л и ^ [r + \)N = Y^c^r' - r-ичное представление числа {г + Щ. Тогда N =Ybir', где /=о,= - ai+i, является минимальной формой числа Л'^.

Пример. Пусть / = 1985 — десятичное представление числа /.

Получим число (lO + l)/:

+ 1985.

Выполнив поразрядное вычитание, определим 10/:

_ 1985.

Представление / = 2015 является минимальной десятичной формой числа /.

Очевидна справедливость для г-ичной минимальной формы и обоих следствий теоремы 1.3.1.3.

Еще один простой метод определения минимальной формы, предложенный Лю и Рудольфом [113], основан на следующих соображениях.

Пусть N - положительное целое число и A(r'')=((r''^'+l)/(r + l),(r''^^ + l)/(r + l)), /0. Тогда в том и только в том случае, когда г-ичное NeA[r") представление числа (г + 1)Л'^ имеет вид (г + \)N = а„+1г"^^ +... + по, а„^1 О.

Последнее же имеет место тогда и только тогда, когда минимальная форма числа Л имеет вид ^ ' где 6„=а„+,0. Следовательно, 6„ =а„+, =[(r + l)iV//"''"^'J. Наконец, если представление минимальная форма числа Л'^, то Ы = Ь„г" +...+bQ минимальная форма числа Ы-Ь„г" есть ^Ь^г' isgnyN-b^r"]. Таким образом, J 41= алгоритм определения минимальной формы заключается в повторении следующего шага: если |Л^| е A[r"~Jj, то установить Ь„_у = [(г+ l)|iV|/r""-^'"^'JsgnA^ и вместо N использовать N'== N-b^.f"'-', у = 0,1,...,л;

если Щ^А[Г"~^), ТО Пример. Пусть iV = 1985, г = 10. Тогда |1985|е A(IO^) И 63=[lM985/10'*Jsgn(l985)=2. Л^'= 1985-2.10^ =-15. Тогда |-15|гд(102) и 62 =0 Далее |-15|eA(l0') и 6i =[lM5/102jsgn(-15)=-l. iV'=-15-(-l)-10 = - 5. Тогда |-5|€A(IO^] И ZO =[ll"5/10]sgn(-5) = -5. Таким образом, минимальная форма числа 1985 есть 2015.

В отличие от двоичного случая, когда условие минимальности (1.3.1.1) определяет единственный вид минимальной формы, для г 2 можно найти и другие условия, не совпадающие с условиями (1.3.1.2), (1.3.1.3), которые определяют модифицированные представления с минимальным количеством ненулевых коэффициентов.

И.М. Бояринов [9] показал, что модифицированное г -ичное представление п положительного целого числа N='^air, -rair, для которого 1= выполняются два условия:

если Я/ О, то а,+, = О, (1.3.1.4) если а,- = -1 (mod г), то а,_, = О, (1.3.1.5) является минимальной г-ичной ф о р м о й этого числа. В следующих двух принадлежащих ему теоремах доказываются существование и единственность минимальной ф о р м ы такого типа.

Теорема 1.3.1.7. Любое модифицированное г-ичное представление положительного целого числа можно преобразовать в представление, удовлетворяющее условиям (1.3.1.4), (1.3.1.5);

полученное представление будет минимальной ф о р м о й этого числа.

Теорема 1.3.1.8. Если д в а представления числа N /=о и /= удовлетворяют условиям (1.3.1.4) и (1.3.1.5), то ЬУ' =bf^ для всех /.

Пример. Для десятичного числа можно записать другую N = минимальную форму Л = 2025, которая удовлетворяет условиям (1.3.1.4) и ^ ' (1.3.1.5).

Еще одна и, пожалуй, наиболее естественная минимальная г -ичная форма была введена Г.А. Кабатянским [40], который доказал, что для любого положительного целого числа Л существует единственная минимальная ^ ' / форма Л = J^bir', -rbi г, удовлетворяющая следующим двум условиям:

^ ' /=о если bi = ±(г -1), то 6,_, = О.

Такая форма называется знакопостоянной. Знакопостоянная форма оказалась весьма удобной и позволила Г.А. Кабатянскому [39] вычислить объемы арифметических шаров в г-ичном случае, которые используются при получении границ Хэмминга и Гильберта для недвоичных арифметических кодов [30].

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

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

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

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

Рассматривая работу устройства, выполняющего арифметические операции в машине, ограничимся пока сложением как основной операцией, которая может быть использована для реализации других арифметических операций. Результат S сложения двух чисел А и В машине можно записать в виде S=A@B®C=R@C, где R - поразрядная (по модулю 2) сумма А иВ;

С - слово, образованное переносами. Появление одиночной ошибки возможно при формировании поразрядной суммы или при образовании и распространении переноса. В первом случае ошибка в /-м разряде приведет к изменению истинного значения суммы на +2', во втором — на ±2'"^', т. е. появление одиночной ошибки всегда приводит к изменению правильного значения суммы на ве личину ± 2-' для некоторого j. В общем случае из-за неисправностей в работе устройства полученная сумма может отличаться от истинного значения на некоторую величину Е, называемую ошибкой, и естественно определять кратность ошибки Е наименьщим количеством степеней двойки ±2-' в представлении числа Е. Действительно, в силу такого определения величину Е нельзя выразить меньшим числом «одновременно возникших одиночных»

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

Если предположить, что появление нулей и единиц в операндах равновероятно, равно как и появление различных двоичных слов в качестве операндов, а также предположить, что схема, выполняющая арифметические операции, состоит из однородных ячеек, работающих в одинаковых условиях (нагрузка по входу и выходу, единый источник питания), то можно считать, что ошибки ±2-' в у-х позициях результата выполняемой операции возникают независимо и метод максимального правдоподобия является наилучщим методом декодирования. В этом смысле понятие «арифметический вес» является некоторым расщиренным аналогом понятия «вес Хэмминга».

Итак, арифметический вес W{E) целого числа Е определяется как количество ненулевых членов в минимальной форме числа Е. Пусть полученный результат арифметической операции отличается от истинного результата на величину Е, тогда будем говорить, что произощла ошибка Е кратности t, если W{E) = t.

Цзян и Рид [100] перечислили ряд свойств арифметического веса для двоичного случая:

1) W{E)0 равенство имеет место в том и только в том случае, когда И Е = 0;

3) 4) 5) если N = 2', / О, то W{NE) = W{E) ;

6) если Е — нечетное целое число, то w{E)-w{E±i) = O или 1;

7) W[E + 2")= W(E)+1, где О 2""^;

8) Н'(2'"±)=1 + ^(:),где 0:2''-', тп + 1;

9) если 0 j, Е2 2"~\ то Ц^, +2")= W[E2 +2") тогда и только тогда, когда 10).

И ) н'(:)[(п + 1)/2],где 2" N2"^K Арифметическое расстояние d{li,l2) между целыми числами /j и / определяется как арифметический вес их разности:

Месси [117] показал, что арифметическое расстояние удовлетворяет свойствам рефлексивности, симметричности и неравенству треугольника:

,,/2) = О тогда и только тогда, когда /, = / (в противном случае Й?(/,, Т. е. арифметическое расстояние является метрикой, и любое множество целых чисел с определенной на нем метрикой данного типа, которую можно назвать арифметической метрикой, образует метрическое пространство. Если вместо истинного значения результата / арифметической операции получено число Y = I + E, где E - ошибка веса W{E) = t, ТО d{l, Y) = t\ иными словами, ошибка веса / приводит к искаженному результату, находящемуся на арифметическом расстоянии t от истинного.

Произвольное подмножество бесконечного кольца целых чисел с определенной на нем арифметической метрикой называется арифметическим кодом. Минимальное арифметическое расстояние d^^^ кода определим как минимальное арифметическое расстояние между словами (числами) кода.

Теорема. (Месси, Гарсиа [118]). Чтобы арифметический код исправлял все ошибки веса / и менее и обнаруживал все ошибки веса t + s и менее в полученном результате некоторой арифметической операции (г, s— неотрицательные целые числа), необходимо и достаточно, чтобы минимальное арифметическое расстояние кода удовлетворяло соотношению Если не позаботиться о специальном выборе кодовых слов (а чтобы этот выбор не свелся к перебору, о специальной конструкции кода), то, скорее всего, произвольный арифметический код не представит никакого интереса.

Действительно, если d^^п = 1 (для этого достаточно, например, чтобы коду принадлежала пара натуральных чисел, отличающихся на единицу), то код не обнаруживает и тем более не исправляет даже одиночные ошибки [30].

1.3.3. AN-коцы.

Содержание этого пункта посвящено изложению конструкции так назы ваемых AN-кодов, относящихся к наиболее изученным арифметическим ко дам [30].

AN-кодом называется множество целых чисел AN, 0N В, где А - по ложительное целое число, называемое порождающим числом, или генерато ром кода, а В определяет количество чисел в коде, или мощность кода. Це лые числа, принадлежащие коду, называются кодовыми словами;

AN^, i = 1,2,..,,5, является кодовым словом для кодируемого числа Л^^, полученным умножением последнего на генератор Легко видеть, что А.

ANi +AN2 =-^{N1 + N2)^ т. е. сумма кодовых слов для A''i и N2 является кодо вым словом суммы этих чисел (если N1+N2 В);

поэтому иногда ЛЛ'^-коды называют линейными арифметическими кодами.

Теорема 1.3.3.1. Минимальное арифметическое расстояние /„,,„ AN-кода совпадает с минимальным арифметическим весом w^^^ В -1 ненулевых кодо вых слов, т. е.

Впервые об ^iV-кодах упоминается в небольшой заметке Даймонда [103] и работе Брауна [98]. Ранние результаты, относящиеся к исследованию свойств AN-кодов, отличались некоторой прямолинейностью. Задача построения Л//-кодов с заданной корректирующей способностью сводилась к отыска нию такого наименьшего положительного целого числа В, арифметический вес произведения которого на А был бы меньше заданной величины мини мального арифметического расстояния dj^m- Действительно, в этом случае AN-код с 0N В имел бы минимальное расстояние, равное по крайней ме Легко видеть, что если А1 - нечетное число, то А является генератором кода, обнаруживающего одиночные ошибки (d^i^ 1);

для обнаружения оди ночных ошибок в машинной арифметике достаточно выбрать минимально возможное значение А = 3.

Имеются обшие соображения относительно выбора величины А. Если ос нование системы счисления г входит в качестве множителя в генератор А и, следовательно, в каждое кодовое слово AN, то в г -ичном представлении ко довых слов самый младший разряд всегда равен нулю и оказывается беспо лезным. Если г не входит в качестве множителя в генератор Л, но Л и г не являются взаимно простыми, то в младших разрядах кодовых представлений некоторые цифры вообш;

е никогда не появятся. Поэтому будем в дальнейшем предполагать, что А я г всегда взаимно просты, т. е. {А,Г) = \. ДЛЯ ДВОИЧНОГО случая это означает, что имеет смысл рассматривать только нечетные значе ния А.

Следующая теорема, которая описывает AN-коды, исправляющие одиноч ные ошибки, принадлежит Брауну [98].

Теорема 1.3.3.2. Если -, когда = 1, В= -, когда А где е - наименьшее положительное целое число, удовлетворяющее указан ным сравнениям, то генератор А порождает ^4Л^-код, исправляющий одиноч ные ощибки.

Питерсон и Уэлдон [69] рассмотрели теорему 1.3.3.2 для случая, когда ге нератор А = р - простое число. Для простого р, как известно, наименьшие вычеты по модулю р образуют конечное поле GF{p) порядка р, ненулевые элементы которого образуют циклическую мультипликативную группу Порядок е{р) каждого ненулевого элемента в поле является делителем GF{P).

порядка группы /? - 1, и существует элемент порядка е{р) = р-1, называемый примитивным, такой, что различными р-\ степенями примитивного элемен та можно перечислить все ненулевые элементы поля.

Теорема 1.3.3.3. Если А = р - нечетное простое число и —,когда 2—примитивный элемент GF{p), —, когда - 2 (но не 2)—примитивный элемент GF{p), ТО генератор А = р порождает AN-код,, исправляющий одиночные ошибки.

В таблице 1.3.3.1 приведены значения В AN-кодов с исправлением оди ночных ощибок для простых А, удовлетворяющих условиям теоремы 1.3.3.3.

А В 11 13 19 23 37 7 178 1 266 9 099 61 17 602 67 128 207 71 483 939 6 958 934 26 494 256 Таблица 1.3.3.1. Соответствие между генератором А и мощностью В AN-кода, исправляющего одиночные ошибки Питерсоном [68] сформулированы также необходимые и достаточные ус ловия существования двоичных ЛЛ'^-кодов, исправляющих одиночные ошиб ки.

Теорема 1.3.3.4. Двоичный AN-код исправляет одиночные ощибки для всех значений N в области 0NB тогда и только тогда, когда вычеты ±2' являются ненулевыми и различными для всех /, при которых 2' АВ-1.

Заметим, что в формулировку теоремы внесено исправление, принадлежа щее И.М. Бояринову и Г.А. Кабатянскому [12]. В формулировке Питерсона требовалось выполнение условий для всех /, при которых 2'АВ. Рао и Трехан [125] заме-йити, что в этом случае из первого утверждения теоремы не следует второе, и предложили ограничение 2' A{B-1). Однако, как показали И.М. Бояринов и Г.А. Кабатянский, в последнем случае из второго ут верждения не следует первое. Подобное исправление внесено И.М. Боярино вым и Г.А. Кабатянским в аналогичное утверждение Рао и Трехана для г ичных кодов.

Коды из теоремы 1.3.3.3 замечательны тем, что они являются единствен ным известным примером нетривиальных двоичных совершенных арифме тических кодов.

Пусть Z^ ={O,l,...,m-l} - кольцо целых чисел по модулю т. Для любого ненулевого числа / е Z^ в Z^ существует симметричный элемент по сложе нию, равный т-1. Модульный арифметический вес w^{l) целого числа I eZ^, введенный Рао и Гарсиа [124], определяется как Доказано, что для модулей т вида 2" - 1, 2" и 2" +1 модулярный вес облада ет рядом свойств, позволяющих использовать его для определения расстоя ния в Z^. Модулярное расстояние d^{li,l2) между целыми числами /,, /2 е Z^, где т - одно из чисел вида 2" - 1, 2", 2" +1, определяется как моду лярный вес разности этих чисел Определим шар радиуса / с центром / е Z^ как множество целых чисел из Z^, модулярное расстояние от которых до центра / не превышает /. Объе мом шара У„1 назовем количество целых чисел, принадлежащих щару. По верхность этого шара, сфера радиуса / - это множество целых чисел, моду лярное расстояние которых до центра / точно равно г. Если AN-код с т = АВ может исправлять все кольцевые ошибки Е„ модулярного веса t и менее, то сферы радиуса t и менее с центрами в кодовых словах не должны пересе каться, так как в противном слз'чае нашлось бы число, находящееся на оди наковом модулярном расстоянии t или менее от двух кодовых слов. Так как должно быть В таких непересекающихся сфер и общее количество целых чисел в Z^ равно т, то любой AN-код, исправляющий t и менее ошибок, должен удовлетворять неравенству 5К„, т = АВ или (1.3.3.1) VnjA.

Полученная граница, как и для метрики Хэмминга, называется границей сфе рической упаковки. Если для некоторых кодов в границе (1.3.3.1) достигается равенство, то такие коды принято называть совершенными, или плотно упа кованными. Для Л//-кодов из теоремы 1.3.3.3, исправляющих одиночные ошибки, У„1 =1 + 2/2 и У„1=А.

Попытки построения AN-кодов с с/^;

„ 3 долгое время оставались безус пешными, пока не была изучена циклическая структура AN-кодов. Однако некоторые результаты были известны и до появления циклических AN кодов. М.А. Кармазин [45] указал па следующий вид yiA'^-кодов с минималь ным арифметическим расстоянием, равным 4 и 5.

Теорема 1.3.3.5. а) Генератор Л = (2''-ф''"^'-l), где а2, порождает AN код длины п = а{а +1) с расстоянием (/^1„ = 4;

б) генератор -l), где нечетное а 2, порождает длины AN-код с расстоянием d^^^ 5.

В.Н. Кондратьев и Н.П. Трофимов [51] обобщили конструкцию М. А. Кар мазина;

их результат состоит в следующем.

Теорема 1.3.3.6. а) Генератор /1 = (2"' - ф ' ' ^ -lj с «i, П22, («,,«2) = 1, поро ждает AN-код ДЛИНЫ w = «j«2 с минимальным расстоянием /„,;

„ = 4 ;

б) AN код с генератором А = YIY-"' -l) имеет минимальное расстояние af^jn : 5, ес ли выполняются следующие условия:

1) «1, «2J •• "/ -попарно взаимно простые числа, / ^ 3 ;

•»

2) существует по крайней мере одно такое значение индекса /, при кото ром И 5;

/ 3) длина п кода определяется неравенством /, /е/ где /, U /2 = {1,2,.,,,/} И /, О/2 = 0.

Исследованиями возможности обобщения конструкции таких кодов зани мались И.М. Бояринов и Г.А. Кабатянский [13]. По аналогии с кодами для передачи сообщений они ввели конструкцию арифметического ;

w-мерного итеративного кода длины который задается генератором п = щ...п„, A = HOK^^^ - l ), Ni=n/ni, («,,иу)=1;

/,y = l,2,.,,,m.

Другой подход к построению арифметических кодов с dj^^j^ 3 был осно ван на модификации AN-кодов;

исследования подобного типа рассмотрены в работах [27, 28, 30, 31, 34, 41, 62, 71, 104, 121].

В последнее время заметно усилился интерес к г -ичным арифметическим кодам. Ограничимся результатами для произвольного г, относящимися к «до-циклическому» периоду развития Л7^-кодов. По-прежнему мощность ко да В будет определяться как наименьшее положительное целое число, ариф метический вес произведения которого на А меньше минимального рас стояния кода.

Па простое ограничение для генератора г-ичного ЛЛ^^-кода с с/^ш =3 ука зали И.М. Бояринов и Г.Л. Кабатянский [12].

Лемма 1.3.3.1. Если А - генератор г-ичного ЛЛГ-кода, исправляющего одиночные ошибки, то Аг^ +г.

Им же принадлежит обобщение теоремы 1.3.3.4 на г-ичный случай.

Теорема 1.3.3.7. г-ичный AN-кол исправляет одиночные ощибки Е = ±аг', 1аг, для всех значении Л в области 0NВ тогда и только тогда, когда ^ ', lar, т.е. синдромы одиночных ошибок, являются ненуле вычеты \±ar' А выми и различными для всех /, при которых аг' АВ-г.

Конкретными конструкциями г-ичных ^Л^-кодов занимался В.М. Грицен ко [25]. Так как для г-ичного случая Г„, =2(r-l)« + l, то совершенные г ичные AN-кощл, исправляюш;

ие одиночные ошибки, если они суш.ествуют, должны порождаться генераторами вида A = 2{r-i)n + l. В.М. Гриценко пред ложил рассматривать генераторы вида A = {r-i)p ( р — простое число, рг), порождаюшие коды длины n = {p-l)/2, т.е. коды с высокой плотностью упа ковки, поскольку в этом случае A = 2{r-i}n + r-\.

Теорема 1.3.3.8. Если порядок е^(р) элемента г в поле GF{p) равен /7-1 (г - примитивный элемент), то генератор А = {г-\)р порождает г-ичный код, исправляющий одиночные ошибки, длины и мош;

ности п = {р~\) В = (г(р-0/2 + 1У((г -1)р) лишь для г 3.

Прямое обобщение теоремы 1.3.3.3. на г-ичный случай попытались полу чить Рао и Трехан [125]. Им принадлежит следующая теорема.

Теорема 1.3.3.9. Если А = 2р^ где р — нечетное простое число, и —,если 3-примитивный элемент поля GF{p), в= —,если —3(но не 3)-примитивный элемент поля GF{p), А то генератор А порождает троичный ЛЛ'^-код, исправляющий одиночные ощибки.

Заметим, что эти коды в отличие от кодов теоремы 1.3.3.3 не являются со вершенными. Более того, результат теоремы 1.3.3.8 показывает, что даль нейшие обобщения такого типа для г 3 оказываются невозможными.

В.Н. Дынькина и Б.Н. Кимельфельда [32] продолжали интересовать г ичпые Л//-коды с генераторами A = F{r)p в случае, когда г или -г является примитивным элементом поля целых чисел порядка р. Множитель F{r) за дается здесь как НОК{2,3,...,г-1). Следующая теорема является типичным примером этой работы, в которой рассмотрены также случаи г = 7,8,11.

Теорема 1.3.3.10. Если А = F{5)p = \2р, где р - нечетное простое число, и _ ср-\,если 5—примитивный элемент поля GF{p),p = 4/ + l.

—,если 5-примитивный элемент поля GF{p),p = 4/ + 3, 6р или -,если —5 {но не 5)—примитивный элемент поля GF{p),p = 4/ + 1, -,если —5 {но не 5)—примитивный элемент поля GF{p\p = 4/ + 3, 4р i = 1,2,..., ТО генератор А = \2р порождает пятиричный AN-код, исправляющий оди ночные ошибки.

Результаты более общего характера были получены Нойманном и Рао [119].

Теорема 1.3.3.11. Если элементы р-\ и ( a - r + l)a~' поля GF{p), где 0аг-1 и не принадлежат циклической подгруппе аа~^=\, Нrip) =\^mod р\ порядка e^ip), то генератор А = {г-\)р порождает г-ичный AN-код, исправляющий одиночные ошибки, длины е^(р) и мощности г-ичный AN-код, исправляющий одиночные ошибки называется совер шенным, если все вычеты по модулю А одиночных ошибок Е = ±аг', 1 а г - 1, l^l Л5 - г, различны и совпадают с множеством всех вычетов по модулю А.

Вопросами существования совершенных г-ичных AN-кодов, исправляю щих одиночные ошибки, плодотворно занимались И.М. Бояринов и Г.А. Ка батянский [12].

Следует отметить, что не для всяких г такие коды можно построить. В ра ботах [30, 106, 109] получен ряд результатов, касающихся несуществования совершенных г-ичных AN-кодов, исправляющих одиночные ошибки. Так, например, Гото [106] показал, что не существуют совершенные г-ичные ко ды, исправляющие одиночные ошибки, для г = 10.

Вопрос о существовании нетривиальных совершенных ^iV-кодов, исправ ляюших более одной ошибки, остается открытым;

Ю.Г. Дадаев [30] предпо ложил, что скорее всего, такие коды не существуют.

Завершая рассмотрение г-ичных ЛЛ^-кодов, следует указать, что Гото и Фукумура [108] пол)^или прямое обобшение на г-ичный случай кодов из теоремы 1.3.3.6, принадлежащих В.Н. Кондратьеву и Н.Н. Трофимову.

Теорема 1.3.3.12. AN-код, с генератором A^fly' -l) имеет минимальное 1= расстояние c/^in ^ 5, если выполняются следующие условия:

1) «1, «2,...,«/- попарно взаимно простые числа и / 3;

2) существует, по крайней мере, одно такое значение /, что л,- 5;

3) длина п кода определяется неравенством где /lU/j = {l,2,...,/}, /1П/2 = 0.

Параллельно с развитием теории Л//-кодов внимание привлекала другая конструкция арифметических кодов, истоки которой следует искать в ранней работе Пирсона [120]. Коды, которые, в конце концов, получили название ос таточных, были предложены Ю.Г. Дадаевым [26] и впоследствии в частном виде переоткрыты Рао [122]. Питерсон рассматривал возможности независи мого контроля работы сумматора и пришел к выводу, что единственным спо собом подобного контроля является так называемый контроль по модулю.

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

в противном случае младшие раз ряды чисел оказываются неконтролируемыми.

Из рассмотренного метода контроля следует, что если сумматор оперирует числами Ne.Z^ и N — наименьшие вычеты чисел по нечетному модулю W, 1, то совокупность последовательностей [A'^.Q (//)], где С(//) = |Л'^|, обра зует арифметический код, обнаруживающий одиночные ошибки. Будем предполагать, что и число N - информационное число, и число CI{N) - про верочное число представлены в двоичной системе счисления. Как видно, та кое строение кодовых слов позволяет считать код систематическим. Усиле ние корректирующей способности кода связано с обобщением этой конст рукции - увеличением количества проверочных чисел. Назовем остаточным кодом, или при фиксированном значении / /-остаточным кодом, совокуп ность последовательностей вида где N^Z^,, / = 1,2,...,/ и mj, W2,..., w/ - генераторы остаточного N CI{N)= кода, являющиеся делителями т. Легко видеть, что В [28], [30] указываются способы построения остаточных кодов, являю щихся также Л//-кодами, поэтому они имеют особое название - разделимые ЛЛ^-коды. При этом нельзя не отметить, что разделимые Л//-коды лишены недостатка неразделимых Л7^-кодов, связанного с отсутствием инвариантно сти последних относительно операции умножения. К тому же, разделимые Л//-коды позволяют обеспечить параллелизм при выполнении действий над информационными и избыточными символами и имеют преимущества перед неразделимыми Л//-кодами при декодировании.

1.3.4. Циклические Л//-коды Интенсивное развитие теории арифметических кодов началось с исследо ваний циклической структуры AN-колов, в результате которых были решены задачи построения Л//-кодов с широким диапазоном корректирующих спо собностей.

Пусть целое число I&Z^, где т = 2"-1, имеет двоичное представление _i,a^_i,...,ai,ao)- Тогда целое число T{I), двоичное представление которого _2,a«_3,...,«o^/i-i) получено ИЗ двоичного представления числа / путем ле вого циклического сдвига, связано с числом / соотношением Г(/) = 2/,если 12"-\ T{I) =21- (2" -1), если 2""' 1т.

Будем называть AN-код. циклическим, если для каждого кодового слова AN целое число T{AN) также является кодовым словом.

Теорема 1.3.4.1. Генератор А и количество кодовых слов В в циклическом Л//-коде связаны соотношением АВ = 2"-1, и каждое число А, являющееся делителем 2" - 1, порождает циклический AN-код с В = \2" -\у А словами.

Пусть е{А) - показатель, которому принадлежит 2 по модулю А. Если А порождает циклический ЛЛ^-код, то А должно быть делителем 2 " - 1. Легко видеть, что е{А) всегда должно делить п. Если п е{А), то тогда окажется, что 2^и) _1 будет кодовым словом и вес этого кодового слова равен 2. Чтобы из бежать этого неинтересного случая, будем всегда полагать, что длина кода и в общем случае выбирается как показатель е{А), которому принадлежит 2 по модулю генератора Л ЛЛ'^-кода.

Алгебраическое описание циклического AN-кода заключено в следующих двух теоремах.

Теорема 1.3.4.2. В кольце целых чисел по модулю т = 2" -\ подмножество целых чисел является циклическим тогда и только тогда, когда оно является идеалом.

Теорема 1.3.4.3. Подмножество целых чисел образует идеал тогда и только тогда, когда оно состоит из всех целых чисел, кратных некоторому целому числу.

Первые упоминания о циклических.4Л'^-кодах, скорее всего, принадлежат Г.К. Кладову, А.Я. Шлильбергу [47] и Мандельбауму [114]. Однако появле ние циклических ЛЛ'^-кодов часто связывают с поиском AN-кодон с «боль шим» расстоянием, т. е. с расстоянием по крайней мере больше 3. Первые на этом пути примеры циклических ЛЛ'^-кодов были независимо предложены Мандельбаумом [115], О.Б. Соколовым и И.И. Еникеевым [73] и Чжаном и Цзао-У [99];

последние, кроме того, указали на сушествование работы Бэр роуза [97]. Любопытно, что все эти независимые предложения рассматривали задание циклического AN-кот генератором одного и того же вида.

Как известно из теории чисел (подробности см., например, у Хассе [79]), разложения в чисто периодическую г-ичную дробь a = O,ai...a^ имеют те и только те рациональные числа а, которые могут быть представлены пра вильной дробью а = с/В со знаменателем, взаимно простым с г;

при этом длина п периода равна порядку класса вычетов г mod В, взаимно простых с модулем, а последовательность а,...а„ совпадает с последовательностью цифр в г-ичном представлении числа с\г" -1)/В. Если В = р — простое число, то в том и только в том случае, когда г является первообразным корнем по модулю р,т. Q. когда « = /7-1, дроби с/р, получающиеся циклическим сдви гом периода в г-ичном представлении одной из них, например 1//?, исчерпы вают все р - 1 правильных дробей с/р со знаменателем р.

Рассмотрим двоичное разложение дроби I/р с периодом длины р-1, где р — простое число и 2 является первообразным корнем по модулю р. Двоич ную последовательность, составляющую период разложения, обозначим как ap_2,ap_3,...,ai,ao)- Деление единицы на р представляет собой итеративный процесс, на каждом шаге которого образуется цифра частного и остаток;

(/ + 1)-й остаток /г,+1 определяется по /-му остатку Л- согласно правилу, //,+1 = 2hi (mod p ), где /JI = 1, a цифра частного определяется как «,, _ /1, если 2hi р, "(р-1)-' - 1 0, если 2hi р. Если рассматривать дво Легко видеть, что /, = 2' ' (mod р), а «(p-i).,- = 2' г ичную последовательность, составляющую период разложения дроби 1/р, как целое число, то Аналогично периоды разложения дробей а/р, где а = 2,3,...,р-1, представ ляющие собой все возможные различные циклические сдвиги последова тельности (ap_2«p-3-ai,ao), могут рассматриваться как целые числа 2 - Аа = а.

Р Итак, имеется р-1 ненулевых двоичных (p-l)-разрядных чисел, которые делятся на Л и могут быть получены одно из другого циклическим сдвигом.

Если добавить к ним слово, состоящее целиком из нулей, то тем самым будет построен двоичный циклический AN-код с генератором Л = (2^"^ -l)/p и ко личеством слов В = р, где р — простое число и 2 — первообразный корень по модулю р.

Ни Мандельбауму [115], ни О.Б. Соколову и И.И. Еникееву [73] не удалось точно определить минимальное расстояние предложенного ими кода;

это бы ло сделано Бэрроузом [97], Гото н Фукумура [108] и Чжаном и Цзао-У [99].

которых модулярные расстояния между всеми парами раз У1Л'^-КОДЫ, ДЛЯ личных кодовых слов одинаковы, естественно называть эквидистантными.

Так генератор А = (2^"^ -l)/p, где р - простое число и 2 - первообразный ко рень по модулю р, порождает эквидистантный циклический AN-код длины л = р - 1, содержащий р слов, с dj^m = (р ± l)/3.

Еще один пример циклического AN-кода был рассмотрен ранее. В случае если -2, но не 2 является первообразным корнем по простому модулю р, то, как следует из определения циклического кода, генератор А = р порождает циклический совершенный AN-код длины n = {p-i)/2 с /„,;

„ = 3. Если 2 явля ется первообразным корнем по модулю р, то генератор А = р также порож дает совершенный ^Л'^-код длины n = {p-l)/2 с c/^jn = 3, однако этот код уже не будет циклическим, и поскольку в этом случае А = [г^'^"^^'^ +^уВ, то, следуя Берлекэмпу [7], будем называть его негациклическим.

Месси и Гарсиа [118] предложили для оценки циклических У4Л^-кодов ис пользовать сходное со скоростью передачи отношение двоичного логарифма числа кодовых слов к двоичному логарифму общего количества целых чисел BZ, R = (l0g2 в)/ l0g2 W = (l0g2 5)/(l0g2 А + l0g2 В).

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

при отсутствии кодирования, т. е. когда Л = 1, скорость R = \ если же имеется только одно кодовое слово, т. е. 5 = 1, то скорость /? = О. Величина Iog2 А на зывается избыточностью. Как видно, эквидистантные AN-коды с В-р я ^min =(;

?±l)/3 и совершенные AN-коды с А = р и /„;

„ =3 являются в опреде ленном смысле предельными случаями циклических ^iV-кодов: первые име ют большую корректирующую способность, но низкое значение скорости;

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

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

Пусть числа, меньшие т = 2"-\, могут быть разделены на три класса:

M^={2"/3,2''*^/^) и U^ ={^"^Чз,2''-\), где {а,Ь) обозначает L^=(o,2"/2), множество целых чисел /, а1 Ь.

Месси и Гарсиа [118] доказали следующее утверждение.

Теорема 1.3.4.4. В каждом циклическом AN-коде с В1 всегда существует по крайней мере одно нечетное кодовое слово AN^, принадлежащее L^, та кое, что w{ANi)=w^i^.

Итак, кодовые слова, принадлежащие L^, т. е. слова, содержащие в двух старших разрядах минимальной формы нули, представляют особый интерес для циклических AN-кодов. Заметим, что минимальные формы этих слов об ладают свойством «циклической несмежности», т. е. в «-разрядной мини мальной форме (б„_1,6„_2,...,б1,6о) кодового слова, принадлежащего L^, ^п-Фо = О • Поэтому если производятся циклические сдвиги этих минимальных форм, то результаты всегда будут также л-разрядными минимальными фор мами, хотя полученные минимальные формы могут уже соответствовать числам, не принадлежащим L^.

Следующая теорема, обобщающая подход, который использовался для оп ределения djnin эквидистантного кода принадлежит Препарата [121] и адап тирована Месси и Гарсиа [118]. Надо отметить, что сам результат был извес тен и раньше (см., например, Ю.Г. Дадаев [31], Цзао-У и Чжан [128]).

Теорема 1.3.4.5. Арифметический вес w{l) целого числа I еЬ„ равен коли честву вычетом 2'/, О / «, принадлежащих классу М^ = \2" /З.г""^' /з).

т Применение теоремы 1.3.4.5 для вычисления арифметического веса ко до вого слова ANi е L^ можно упростить с учетом следующего замечания. Так как т = АВ, то = 2'ANi 2'ANi = А 2'N в' АВ так что 2'AN m находится в классе М„ тогда и только тогда, когда в классе находится А2', но последнее условие выполняется тогда и только в тогда, когда 2'N принадлежит множеству целых чисел в полуинтервале в (5/3, 25/з]. Таким образом, теорема 1.3.4.5 имеет следующее Следствие. Для любого кодового слова AN^ е L^ произвольного цикличе ского AN-Kojxa арифметический вес w{ANi) равен количеству вычетов в / = 0,1,...,«-1, находящихся в полуинтервале (5/3, 25/з].

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

Совокупность слов, взятых по одному из каждого такого подмножества, бу дем называть множеством циклических представителей. Двоичное выраже ние для у-го циклического представителя имеет вид («Й-1,«„-2»-.«О)» ^Д^ ;

aj - нечетное число, «у «y+i5 «i =1;

/ = 1,2,...,«;

у = 1,2,...,/ и / В - количество циклических представителей. Совокупность чисел aj будем на зывать циклическим базисом С{в). Произведение элемента циклического ба зиса на генератор А определяет соответствующий циклический представи тель. Условие включения некоторого нечетного числа aj в циклический ба зис заключается в неразрещимости сравнения «У2' S а2 (mod 5), / = 1,2,...,«, для всех О 2 у.

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

Далее рассмотрим циклические AN-коды с известным расстоянием. Преж де всего обратим внимание на ЛЛ'^-коды с А = \2" ~lj/B в случае, когда п - не четное число. Будем называть циклический AN-код примитивным, если ни один из простых сомножителей В не делит двучлен 2" -1 при п'п. В слу чае примитивного кода все циклы, образованные вычетами ^y2-^|mod В, бу дут иметь одинаковый период, равный п, и количество / циклических пред ставителей определится как Ы{в-\)1п.

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

Кроме того, сумма арифметических весов всех циклических представителей примитивного кода равна [(л + 1)/3]. Тогда имеет место следующее утверж дение, высказанное независимо Гото и Фукумура [108] и Ю.Г. Дадаевым [31].

Теорема 1.3.4.6. Если В - простое число и -2, но не 2 является первообраз ным корнем по модулю В, то генератором A = \2S^~^^'^ -\]lВ порождает цик лический длины минимальным расстоянием AN-код п = {В-1)/2 с Легко видеть, что этот код является эквидистантным. Кроме того, так как принадлежит показателю (S-l)/2 по модулю В, т. е. 2 является квадратич ным вычетом (КБ) по модулю В, и п = {В-l)/2 — нечетное, то В может быть только вида 5 = 8? + 7.

Если хотя бы один из сомножителей числа В, делящего 2"-\, делит 2" - при п' п,то циклический AN-код называется непримитивным. Ю.Г. Дадаев [31] рассмотрел некоторые простые случаи непримитивных Л7^-кодов.

Пусть / = (2"-l)/5, где В - простое число, В = \^"' -\)/А', п'п и Л'//-код яв ляется примитивным. В этом случае каждое ненулевое слово AN-кода будет представлять собой двоичную последовательность, состоящую из двоич ных последовательностей Л'Л^-кода длины «', повторенных п1п' раз. Коды, содержащие хотя бы одно слово, которое получено более чем однократным периодическим повторением п' первых символов, будем называть кодами с собственным периодом. В рассматриваемых кодах все слова содержат собст венный период длины «';

такие коды удобно относить к кода исключительно с собственным периодом. В общем случае из определения непримитивных кодов следует, что коды исключительно с собственным периодом имеют ме сто, когда все сомножители В для кода с генератором А = (2" -Ij/B входят в разложение двучлена 2 " ' - !, п'п. Количество циклических представителей для кода исключительно с собственным периодом 1 = {В-\)1п' и минималь ное кодовое расстояние с/щт =^mm^/^'5 где J^jn - минимальное расстояние соответствующего примитивного кода, образующего для данного кода собст венный период.

В частном случае, когда Л'= 2 " ' - !, !«"«', и Л = (2" -1)/(2'''-1), минималь ное расстояние AN-кот d^^^=2nln'. Если А'= \ и Л = ( 2 " - l j ^ " ' - l ), то ^min =«/«';

на существование таких тривиальных кодов указывали И.Л. Ерош н С.Л. Брощ [34]. Кроме того, Хуан и Хартманн [111] отметили, что и в случаях, когда 5 = (2"'-1)/(2''" +1) и Б = (2"'+1)/(2"'+1), и для кода с генератором Л = (2"-l)/[2'''+l). Наконец, если 5 = (2''-l)/(2"''-l)(2"2 -l), то поскольку/;

„;

„ =w|2""-l)(2''2 - I ) J = 4, T O d^^^ =Ап1п'.

Для непримитнвных кодов, где в разложение В входит, например, ^ со множителей и каждый из этих сомножителей является делителем некоторого двучлена 2"^ - 1, n'j п, j = l,2,...,s, кодовое расстояние определяется как ми нимальная из величин d'.^^^^nln'j.

В случае и код с генератором В = \2/^^-Ц!"'^-\) щп А = (2" -l)/(2''' - ф " ^ -l) длины п = щп2 имеет d^^^ = nlrij = «i, поскольку ариф метический вес кодового слова А\1"^-\]=\1"-\)l\^"^-\^ равен точно «i, а арифметический вес любого другого ненулевого кодового слова не меньше щ.

Непримитивные коды, для которых не все сомножители В входят в разло жение двучлена с меньшим показателем, относятся к кодам частично с соб ственным периодом. В случае, если только один из сомножителей В входит в разложение двучлена с меньшим показателем, имеет место сравнение В-1 sn'r {mod п), где г — количество циклических представителей с собственным периодом п'.

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

Обратимся теперь к случаю, когда длина циклического Л//-кода - четное число, и начнем с рассмотрения примитивных кодов. Если А = \^^" -Ij/B, то легко видеть, что для всех примитивных кодов четной длины число В долж но входить в разложение числа 2" +1 и ни один из сомножителей числа В не должен входить в разложение числа 2"' +1, п' п.

Если В - простое число и показатель, которому принадлежит 2 по модулю В, является четным, то двоичная последовательность («2«-i^2«-2'—'^ь^о)»

, i = \,2,...,2n, состоит из двух полупериодов, каждый из которых является дополнением другого, т. е. а2„_у + ajn-ij+n) = 1 Для всех у, l,Jn.

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

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

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

Примером циклических примитивных кодов четной длины являются экви дистантные коды с генератором А = \2^~^ - l ) / 5, где В - простое число и 2 первообразный корень по модулю В.

Рассмотрим еще один пример примитивных кодов четной длины, для ко торых можно определить минимальное арифметическое расстояние [31].

Числа 2^ +1 называются числами Ферма. Понятно, что простые числа Ферма (а все простые числа вида 2" +1 являются числами Ферма) в качестве В ис пользовать неинтересно, так как коды с генератором Л = (2^''-1)/(2"+l), где 2" +1 — простое число, имеют минимальное расстояние, равное 2. Если же п имеет нечетный делитель, то само число 2" +1 содержит в своем разложении простое число Ферма.

Теорема 1.3.4.9. Если 2" + 1 = 2 ^ +чП/'/» г'Д® ни одно из чисел р^, pj,..., Ps не является делителем числа 2"' +1, л' «, то циклический AN-Koji, с гене ратором /= имеет минимальное арифметическое расстояние, равное 4.

Рассмотрим далее некоторые классы непримитивных кодов четной длины.

Так в [29], используя результаты исследований циклической структуры сие темы вычетов по составному модулю, выполненные В.Д. Колесником и Е.Т.

Мнрончнковым [49] и Мандельбаумом [116], построен циклический AN-код с генератором А = \2" -\]/{piP2) длины п = HOK{{j?i-\),{p2-l)} и мощностью В = pip2, где Pi и Р2- нечетные простые числа.

Цзао-У и Чжан [128] и В.Н. Дынькин, Г.М. Тененгольц и Г.И. Хабелашви ли [33] независимо рассмотрели частные случаи кодов с B = piP2, для кото рых им удалось определить точное значение минимального расстояния.

Теорема 1.3.4.10. Если В = pip2, В не делит 2"'^- +1 и а) 2 — первообразный корень по модулям р^ и Р2 я НОД{{р1 -l),(/'2 ~0} = или б) 2 — первообразный корень по модулю pi, 2 — квадратичный вычет по модулю Р2 и Н0Д{{р1 -\),{р2 -1)/2} = 1, то генератор O(PI-1XP2-1)/2_I А = Р\Р порождает AN-код, длины п = {р^ - I X P 2 - 1 ) / 2 С минимальным расстоянием Г.М. Тененгольц и В.Н. Дынькин [75] извлекли из теоремы 1.3.4.10 любо пытный частный случай. Если pi=3 и Р2= l(mod З), то AN-код с генератором А = [2^2"' -1)/{Зр2) имеет такую же длину и такое же минимальное расстояние, что и эквидистантный код с В = Р2 и 2 - первообразным корнем по модулю Р2 но в три раза большую мощность.

Цзао-У и Чжан [128] и Ю.Г. Дадаев [29] независимо рассмотрели случай В = р''. Так Ю.Г. Дадаевым доказана следующая теорема.

Теорема 1.3.4.11. Если В = р'' и 2 - первообразный корень по модулю р, то генератор А = порождает AN-код длины п = р'"\р-\) с мини р'' мальным расстоянием если p = l(mod З) или p = 3, и если p = -l(mod З) для г 1 (для г = 1 d^^^ ={р +1)/3 ).

Цзао-У и Чжан пошли в обобщении еще дальше, и им принадлежат сле дующие два результата:

1. Генератор где р - простое число, г 1 и 2 является квадратичным вычетом по модулю р, порождает AN-код, нечетной длины и = p'•"^(^7-l)/2 с минимальным рас стоянием [, 1 r- LTJ| «min = ^ 2. Генератор л = Г2^''"'^2'2"'^^-')(^2-0/2 -\\/{p^'^р^'^), где pj Рг - простые числа;

г,, Г2 1;

2 - первообразный корень по модулям pj, pj ЯСд{р,'^"'(р1 -1),Р2'^~^{Р2 -1))=2 и Pi'^P2'^ не делит 2"^^ +1, порождает ЛЛ^-код длины п = PI'^~V2'^~4PI ~IXP2 -1)''2 С минимальным расстоянием если pi = l(mod З) и Р2 s -l(mod З), и Pl'+l в остальных случаях.


В заключение рассмотрения двоичных циклических AN-кодов заметим, что трудности в определении точного значения минимального расстояния, особенно для кодов с «промежуточными» значениями скорости, привели к необходимости построения оценок искомых расстояний. Некоторые резуль таты по этой проблеме получены в работах [ПО], [111], [127]. Кроме этого, отметим, что хотя многие утверждения, касающиеся двоичных циклических AN-КОД.ОВ, начиная от способа их задания и заканчивая, например, верхней границей для минимального расстояния, можно легко обобщить на случай произвольного основания, не очень много известно о корректирующих свой ствах г-ичных циклических У47^-кодов [30]. Так любопытные обобщения на случай г-ичных циклических ЛТ^-кодов получены И.М. Бояриновым [9], И.М. Бояриновым и Г. А. Кабатянским в[10]и[11], Кларком и Ляном - [101], [102].

Таким образом, корректирующий код СОК обладает рядом достоинств: не зависимость образования разрядов числа (в силу чего каждый разряд несет информацию обо всем исходном числе) и малоразрядность остатков в пред ставлении числа [5]. Отсюда вытекает возможность независимой параллель ной обработки разрядов, что ограничивает распространение ошибки, воз никшей в остатке по какому-либо модулю, на другие разряды числа. Мало разрядность остатков в представлении числа говорит о том, что наиболее ве роятны одиночные ошибки, а также открывается возможность построения эффективной табличной арифметики. Указанные достоинства кода СОК по зволяют значительно повысить скорость выполнения операций сложения, вычитания и умножения (по сравнению с осуществлением этих операций в позиционной системе счисления). К основному недостатку кода СОК отне сем высокую арифметическую сложность процедуры локализации ошибоч ных остатков.

Решением проблемы уменьшения недостатков кода СОК является по строение гибридного кода AN-СОК, этому и будет посвящено содержание главы 2. Другим путем рещения поставленной проблемы является совмест ное использование корректирующих свойств кода СОК и нейронных сетей (НС), об этом пойдет речь в главе 3.

Выводы по главе 1.

1. Приведена классификация помехоустойчивых кодов. Рассмотрены наи более применимые из них для контроля выполнения различных операций ЭВМ. Изучаются две конструкции арифметических кодов - коды системы остаточных классов (СОК) и ЛЛА-коды.

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

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

4. Получены формулы для исправления искаженных разрядов представле ния чисел в коде СОК. Исследованы отдельные факты обнаружения и ис правления ошибок, порядок которых превышает число, гарантированное ми нимальным расстоянием кода.

5. Описаны основные факты теории Л//-кодов. AN-кощл обладают свойст вом арифметичности, при этом они имеют простые алгоритмы кодирования и декодирования. Циклические представители Л//-кодов, кроме того, имеют широкий диапазон корректирующих способностей.

Глава 2. Математическая модель корректирующего кода AN-СОК, обнаруживающего и исправляющего ошибки, возникающие нри обра ботке данных.

2.1. Гибридный код ^iV^-COK, его корректирующие снособности.

Коды СОК и ЛЛ'^-коды, описанные в главе 1, обладают рядом достоинств, наличие которых у единого кода, используемого для обнаружения и исправ ления ошибок, возникающих при обработке данных, было бы весьма полез ным. Подобные рассуждения приводят к задаче построения кодов, представ ляющих собой синтез кодов СОК и AN -кодов.

С учетом теоремы 1.2.2.4 для исправления всех одиночных ошибок в коде СОК достаточно ввести не менее двух избыточных оснований так, чтобы их произведение было не меньше произведения любых двух модулей кода. При этом под одиночной ошибкой подразумевается искажение числа, являющего ся остатком от деления исходного числа N на число р,, т.е. разряда по моду лю р, в представлении числа Л в системе остаточных классов. С учетом ^ ' реалий действительности каждый из разрядов представления исходного чис ла // в системе остаточных классов в ЭВМ все равно приходится представ лять в двоичной системе счисления, это приводит к тому, что упомянутый код СОК может исправлять искажение [logjO?, -l)+l] двоичных символов, но лишь в одном разряде представления числа N, что не всегда целесообразно.

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

Здесь и далее говоря о коде ^iV-COK, будем иметь ввиду их двоичных представителей, хотя с учетом сведений главы 1 ряд рассуждений можно аналогично проделать и на случай, когда для построения гибридного кода используются г-ичные ЛЛ'^-коды.

Установим, при каких условиях длина (число разрядов, необходимых для кодирования информации) гибридного кода AN-СОК окажется меньше дли ны кода СОК, считая, что оба кода представлены одними и теми же инфор мационными основаниями, т.е. определяют числа из одного диапазона, и «минимальное расстояние» обоих равно 3. Заметим, что условие относитель но минимального расстояния в гибридном коде накладывается на каждый модуль.

Пусть р,, /?2 •• Рк ~ информационные модули гибридного кода и кода • СОК, Л,, ^2,..., А^ - соответствующие генераторы ^/^-кодов для каждого из информационных оснований кода AN-СОК;

р^^^, р^^^,..., р„ -проверочные модули кода СОК. Пусть минимальное расстояние обоих кодов равно (с/ = 3). Докажем справедливость следующего утверждения.

Теорема 2.1.1. Длина гибридного кода ЛЛ'^-СОК меньще длины кода СОК, если р,,р,^2*^'ЛЛ'...-Л, (2.1.1) где р,., Pi^ — два наибольщих информационных модуля, к - число информа ционных оснований.

Доказательство. Длина кода СОК равна сумме (2.1.2) Ясно, что [logj p,+\] = \log2iPi -l)+l]+l лишь в том случае, когда р, = 2°, т.е.

когда есть степень двойки, а в остальных случаях Pi,-l)+l]. В силу взаимной простоты модулей можно заклю чить, что если и верно [logj р, +l] = [log2(/?, -l)+l]+l, то только для одного из /, / = 1,и, поэтому 2;

[iog,(A-i)+i]i;

[iog,(A-i)+i]+|;

[iog,/,,+i]-i. (2.1.3) Учитывая определение целой части числа, имеем (2.1.4) )p,-\.

1=1 1= Ык+\ 1=к*\ Применяя свойства логарифмов, правую часть неравенства (2.1.4) можно записать в виде Xlog,(p,-l)+log,np,-l, (2.1.5) 1=1 i=t+l ЧТО в силу условия с/ = 3 и теоремы 1.2.2.4 больше, чем, (2.1.6) где р,^, д — два наибольших информационных модуля.

Из формул (2.1.2)-(2.1.6) получим l)+log2(A,Aj-l. (2.1.7) Длина гибридного кода равна сумме ^тя-о = E N : 4 ^ - 0 + 1 ]. (2.1.8) 1= Учитывая определение целой части числа, утверждать, что (2.1.9) 1)+1).

Применив свойства логарифмов, имеем (2.1.10) f^\og,{p,-l)+f^\og,A,+k, /=i 1= Из формул (2.1.8)-(2.1.10) получим (2.1.11) t Таким образом, из (2.1.7) и (2.1.11) заключаем, что длина гибридного кода меньше длины кода СОК (Z,^.„б^^J co W /-I /= откуда ^ I o g j Ai+{k + l), Теорема доказана.

Замечание. Теорему 2.1.1 можно несколько усилить, отметив, что в силу теоремы 1.2.2А выражение 2.1.5 не меньше, чем где py - наибольший информационный модуль. Тогда неравенство 2.1. примет вид [pj +lj(py +2)2'^*^А1А2 -...-Ai^.B случае, когда проверочные моду ли СОК уже выбраны, оставив выражение 2.1.5 без преобразования, неравен ство теоремы 2.1.1 можно заменить на неравенство Ограничившись рассмотрением кодов с двумя информационными модуля ми, можно доказать правильность следуюш;

его утверждения.

Теорема 2.1.2. В случае двух достаточно больших информационных осно ваний р, и Р2 длина гибридного кода ЛЛ'^-СОК меньше длины кода СОК, считая, что оба кода представлены одними и теми же двумя информацион ными основаниями и минимальное расстояние обоих равно 3.

Доказательство. Пусть Л, и ^2 - генераторы Л//-кодов для информацион ных модулей р, и Р2 соответственно, причем, считая р, и Р2 достаточно большими, с учетом формул теоремы 1.3.3.3 можно утверждать, что Л, « р, и ^2 «Рг- Откуда вытекает справедливость неравенства p^p2 8/l,/l2, что в силу теоремы 2.1.1 означает верность формулировки данной теоремы. Тео рема доказана.

На рисунке 2.1.1 мы видим графики зависимости длины кода от диапазона кодируемых чисел для кодов СОК и ЛЛ'^-СОК. При построении графиков по лагалось, что оба кода представлены одними и теми же двумя, постоянно растущими, информационными основаниями и «минимальное расстояние»

обоих равно 3.

L• 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 5500 Рис. 2.1.1. Графики зависимости длины кода от диапазона ко дируемых чисел для СОК AN Пример. Пусть /1, =^2 =23, следовательно Л/,(23,3) = Л/2(23,3) = 89. В каче стве информационных оснований возьмем /?, = 88 и /?2 = 87, а в качестве про верочных - poi =89, Ро2 =91- Найдем длины кодов СОК и AN-СОК, и опре делим длина какого из них меньше.


Прежде всего, заметим, что условие (2.1.1) теоремы 2.1.1 выполняется:

88-87 8-23-23. Поскольку [log2(88-l)+l]=7, [log2(87-l)+l]=7, [log2(89-l)+l] = 7 и [log2(9l-l)+l]=7, то длина кода СОК равна =7 + 7 + 7 + 7 = 28, длина же гибридного кода, так как [log2(23-(88-l))+l] = ll и [log2(23.(87-l))+l]=ll, равна L^^^^^^ = 11 +11 = 22. Итак, ^Гибрид Добавим еще одно информационное основание р^ = 83, при этом в качестве генератора ЛЛ^-кода для р^ в гибридном коде оставим число 23, т.е. А^=2Ъ.

Так как 83 87, то проверочные модули можно оставить прежними и мини мальное расстояние не изменится.

Определив, что [log2(83-l)+l] = 7 и [log2(23-(83-l))+l] = ll, получим LcoK =28 + 7 = 35, Lr^^pud = 22 +11 = 33, т.е. Ьгибрид ^сок но неравенство (2. неверно: 88-87 2;

8-23-23-23 (даже рассматривая формулу (2.1.12), видим, что 89-913^8-23-23-23).

Приведенный пример указывает на необходимость подчеркнуть следую щий факт.

Замечание. Отметим, что формула (2.1.1) теоремы 2.1.1 задает достаточ ное, но ни необходимое условие того, чтобы длина гибридного кода была меньше длины кода СОК, т.е. из того, что р^/7,^ 2***^,^2 -...-Л» не следует, что длина кода AN-СОК больше длины кода СОК.

Таким образом, в этом параграфе предложен гибридный код ЛЛ''-COK, представляющий собой синтез кодов системы остаточных классов и AN кодов, найдено достаточное условие того, чтобы длина кода ^iV-COK была меньще длины кода СОК, считая, что оба кода представлены одними и теми же информационными основаниями, а также установлено подобное преиму щество гибридного кода перед кодом СОК, в случае, когда они заданы двумя больщими информационными модулями и «минимальное расстояние» обоих равно 3...

2.2. Действия иад числами, представлеиными в коде AN-СОК.

Пусть каждый из остатков безызбыточного или корректирующего кода системы остаточных классов (кода СОК) представлен в виде двоичного AN кода. Полученный код мы назвали гибридным кодом AN-СОК. Ясно, что преобразование исходного кода СОК в гибридный код AN-СОК повлияет и на известные алгоритмы выполнения действий над числами, представленны ми в коде СОК. Установим правила выполнения действий над числами, пред ставленными в коде AN -СОК.

Пусть pi, р2,..., р„ — основания кода СОК, А^, А2,..., А„ — генераторы Л//-кодов для модулей pi, Р2,..., р„ соответственно. Если числа /?,• взаимно простые, то набор остатков (наименьших неотрицательных вычетов) {а1,а2,:;

Сс„) числа N по выбранным основаниям однозначно задает число N из диапазона [О,Л),где О = р1/72 •...•/?„, т.е.

N' или а/ = A'^(mod р,), / = 1,и. (2.2.1) N = (ai,a2,-,««f ^^, где or,- = iV Число N, удовлетворяющее условию будем называть правильным числом.

В силу конструкции гибридного кода AN-СОК число Л'^, удовлетворяющее условиям (2.2.1) в коде AN-СОК имеет вид N = (ар),аW,...,^^^-^'''', где « ^ = Л,а,, «, ^ iV(mod р,), 1 = Гп. (2.2.2) Из свойств сравнений следует, что формулы (2.2.2) могут быть записаны в виде Л = (aW,aW,....4'^Г"^''^ где « Н ^ ^,iV(mod А,р,), i = u.

Г (2.2.2') Формулы (2.2.2') позволяют без промежуточного перехода к коду СОК пред ставить число N в коде AN-СОК.

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

Пусть W =(аМ,а(^), « М Г " ' " ', а W, =(5р'./'^''.-./?1"'Г""- С учетом правил выполнения операций сложения и вычитания в СОК, конструкции кода AN-СОК, а также формул (2,2.1) и (2.2.2) можно заключить, что, / = М, (2.2.3), /=п. (2.2.4) Действительно, полагая, что Г/= а,-± А-(mod/?,), по свойствам сравнения получим ЛГ/ = Aiiai ±/3i){mod А^р^), AiYi = Aitti ± 47?;

(mod /4,/7,), что и требовалось показать.

Аналогично рассуждая, тот же результат (формулу) для операции вычита ния мы получим, если введем понятие отрицательного числа (-Л'^) в коде СОК по формуле т.е. поделив рабочий диапазон на интервалы положительных и отрицатель ных чисел.

Замечание: отметим, что при описании правил выполнения операций сло жения и вычитания, ограничения накладываемые на генераторы У4ЛГ-кодов Л, были связаны лишь с правилами построения Л7/-кодов и желаемыми коррек тирующими способностями, которыми должен обладать код AN-СОК.

Перейдем теперь к описанию операций умножения и деления нацело (без остатка), которые также относятся к модульным.

Попытка применения формул, аналогичных формулам (2.2.3), (2.2.4) и формул умножение чисел в коде СОК, для осуществление операции умноже ния двух чисел, представленных в коде AN-СОК, приведет к следующему:

пусть ИЗ свойств сравнений имеем /i = Mi/^i (mod (2.2.5) i(mod Л Р, ) ИЛИ mod Последнее означает, что перемножение соответствующих ЛЛ'^-остатков опе рандов не приводит к получению искомого результата (^iV-остатков произ ведения), но промежуточные формулы (2.2.5) позволяют заключить следую щее. Для получение произведения двух чисел, представленных в коде AN СОК, нужно один из операндов перевести в код СОК и умножить по модулю AiPi остатки полученного числа на соответствующие /47/-остатки другого операнда.

Для быстрого перевода чисел из кода АЫ-ОХЖ. в код СОК потребуем, что бы элементы Л,- были обратимы по соответствующим модулям р,-, т.е. суще ствовали рещения сравнений Л,х = 1 (mod Pi), последнее требование будет выполнено, если числа Л,- и /?,• являются взаимно простыми. Тогда на основании формул (2.2.2) формулы перевода чисел кода ЛЛ'^-СОК в код СОК примут вид:

iV = (ai,a2.-.««f^^. где щ ^^•aJ'^Hmod р,), / = п. (2.2.6) Отметим, что при заданных Л,- и р,- (т.е. при задании кода ^iV-COK), величи также являются вполне определенными, наперед заданными числа ны ми.

Таким образом, операция умножения чисел, представленных в коде AN СОК, осуществляется по формулам:

,i = l,n. (2.2.7) '"''/и А: Pi Аналогично рассуждая, для выполнения деления нацело применимы сле дующие формулы:

{л) Ш-СОК А..- ос), где у}'^' = Pi т.е.

{A) \N-COK a / = !,«, (2.2.8) HO для обеспечения возможностью коррекции результата деления предпочти тельнее формулы M^) у{л) ЛА)У N-COK (2.2.9), где у} ' = Заметим, что для осуществимости операции деления без остатка в коде AN-СОК достаточно, чтобы это деление было осуществимо в коде СОК (т.е.

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

Пример. Определим сумму, разность и произведение чисел A^i = 3 и Л^2 =7, представленных в коде AN-СОК с основаниями Pi = 4, Р2=5, р^= и генераторами ^iV-кодов ^, = ^2 = Лз = 3, и, кроме того, вычислим частные от деления произведения этих чисел на каждый из сомножителей.

N, = (9,9,,AN-сок i-6 -•О - N,N2 = 12 15 21.

AN-COK =9-3-9 9-2-6 =(3.3.0) 12' 5115'.AN-сок 3. 3-- О 21.

12 = (9,6,0)AN-COK,3-3-4 0-3-4, 12' 5ll5' AN-COK 3. 3•— о N.

12 15 21.

\ AN-COK.AN-сок = О = 3.3. о 12 21, Как видим при необратимости составных частей делителя формулы (2.2.9) не дают однозначного результата, но при использовании формул (2.2.8) прихо дим к следующей последовательности рассуждении.

,AN-COK, AN-COK 3 о |3| 3.- 3.

3- 15' 9 4 12 0 7 21, 15 21, В силу ТОГО, Ч О исходные операнды являются правильными числами Т (A'^iA'^2 ^ г'Д^ D = Р\Р2Ръ\ и поскольку Рз =7 является делителем числа N (остаток по этому модулю равен нулю), то число N2 заведомо не меньше рз ^1^2 тт P\PiP% И следовательно ' ^ ^и-^^^л = Р\Р2' Последнее означает, что модули рх и Л'2 РЪ P2 П Л О Т Ю определяют частное от искомого деления, т.е. остатки по ос ОН СЬ нованиям pi и Р2 однозначно определяют и вычет по модулю р^ Итак, ^1^2 _C • h h ^1 h -;

_ /Q Q QVN-COK VN-COK Немодульные операции (определение знака числа, абсолютной величины числа, сравнение чисел и др.) над числами кода AN-COK будем считать осу ществимыми в силу их осуществимости над числами в коде СОК и формул (2.2.6), позволяющих произвести перевод чисел кода AN-COK в код СОК. В силу отсутствия контроля ошибочного выполнения немодульных операций в коде СОК мы не выводим специальных правил их выполнения над числами кода AN-СОК.

Итак, в данном параграфе обоснована осуществимость модульных и немо дульных операций над числами гибридного кода AN -СОК, получены форму лы для представления числа N, заданного в десятичной системе счисления или в виде систематической записи, в коде AN-СОК, перевода чисел кода AN -СОК в код СОК и обратно, а также формулы, задающие правила выпол нения модульных операций над числами в коде AN -СОК.

2.3. Геометрические модели кодов СОК и Геометрическая модель избыточного кода системы остаточных классов (СОК) является немаловажным объектом исследования, так как она позволя ет уяснить важные соотношения теории помехоустойчивого кодирования, определяющие корректирующие возможности кодов СОК. Кроме того, эта модель дает возможность предугадать некоторые результаты, которые затем можно будет доказать строгим математическим путем. Исследования теории помехоустойчивого кодирования при помощи геометрических методов до полняет алгебраическую теорию кодирования и является обобщением теории кодирования сигналов, представленных в системе остаточных классов.

В [94, 95] предложена геометрическая модель помехоустойчивого кода в системе остаточных классов (кода СОК), базирующаяся на совокупности единичных п-мерных кубов. Ее смысл состоит в следующем. «Каждому представлению числа в СОК, образующему кодовые комбинации, ставятся в соответствие верщины единичных п-мерных кубов, кодовые точки которых:

образуют Р„=р^-р2-...-р„ вершин.

Количество n-мерных кубов онределяется выражением Пусть новерхность единичных п-мерных кубов обладает тем свойством, что любые две вершины на ней могут быть соединены нрямыми, имеющими конечную длину. Тогда для каждой нары вершин 4 и Aj поверхности п мерных кубов существует нижняя граница длин нрямых, лежащих на этой поверхности и соединяющих выбранные точки. Эта нижняя граница длин прямых есть расстояние между точками А, и Aj — d^^^. Определенное таким образом расстояние удовлетворяет трем основным аксиомам метрики:

Всякое множество Р„ комнлексов СОК, в котором для любой нары его элементов (точек) 4 и Л^ определено число с/^^^, удовлетворяющее трем ос новным аксиомам метрики, называется метрическим пространством. Функ ция d^^ называется метрикой этого пространства, а ее значение для какой либо пары точек (верщин) единичных п-мерных кубов - расстоянием между этими точками.

Введенная метрика такова, что единственная ощибка изменяет одну коор динату кодовой точки, две ощибки две координаты, к ощибок - к координат.

Ощибка по одному основанию может изменить одну координату на величи ну, равную глубине ощибки Д,. Расстояние между двумя верщинами единич ных п-мерных кубов 4 и Aj можно онределить как наименьщее число ребер, которые следует пройти при движении из вершины А, к верщине Aj. Смеж ные ребра, определяющие глубину ощибки по одному основанию, нри онре делении расстояния считаются за одно ребро. Необходимо отметить, что движение но ребрам п-мерных кубов может нроисходить не только в преде лах данного куба, но и кубов, соседних снрава, слева, сверху и снизу.

Наибольшей наглядностью обладает геометрическая модель для кодов СОК, представленных тремя основаниями: р, = 2, Pj = 3, Рз = 5, где р, и pj информационные основания, а pj — контрольное основание. При этом рабо чий диапазон А = Pi' Рг = ^, а полный диапазон /'з = А * Рг" Л = 30. В рассмат риваемом случае число А однозначно определяется представлением («,,«2) поэтому разряд а^ можно считать избыточным. Входной алфавит состоит из Рз букв (0,1,..., 29). Тогда значность кода СОК, обеспечивающего представ ление и передачу всех букв этого алфавита, будет равна Л(ог,,а2,аз), где а, =0,1;

«2 =0.1,2;

а^ =0,1,2,3,4.

Глубина ошибок для первого основания равна А, = 1, для второго основа ния может меняться от Д2 = 1 до А2 = 2 и для третьего основания — от Аз = до Аз = 4. Каждая буква представляется тремя десятичными разрядами. Зна чения разрядов О а, р, - 1, где / = 1,2,3.

Такая геометрическая модель кода СОК показана на рисунке 2.3.1, где у каж дой из вершин отмечены координаты.

Ось X имеет один единичный отрезок, соответствующий модулю p^, ось у имеет два единичных отрезка, соответствующие модулю Р2 и ось z имеет четыре единичных отрезка, соответствующие модулю р^.

Величина расстояния между различными кодовыми комбинациями (векто рами) изменяется от 1 до «, где п — количество модулей;

в нашем примере / = 3. Например, расстояние между точками d^^^^ = 1, d^^^_, = 2, d^^ = 3.»

Обратим внимание читателя на то, что при всех достоинствах данной мо дели, можно заметить и некоторые ее недостатки. Изложенная модель не по зволяет изображать код СОК с числом оснований, превышающим 3. Кроме этого отметим, что при изображении кода СОК, желательно учесть такую конструктивную особенность этого кода как «цикличность» (например, рас смотрим кодовые комбинации А^, A^^ и ^26 кода, геометрическая модель ко торого изображена на рисунке 2.3.1;

поскольку Лб=(0,0,1), ^, =(o,l,l), Лб =(0,2,l), при увеличении в А^ разряда по модулю Р2=3 на единицу мы получим Л,6, а результатом этого же преобразования в А-^^ будет (0,2,4) (0,2,3) (0,2,2) Рис. 2.3.1. Геометрическая модель избыточного кода с тремя основаниями Модель кода СОК с одним основанием, учитывающая свойство циклично сти, очевидна. Каждое кодовое слово будем нредставлять точкой окружно сти. К примеру, имея код с одним основанием р = 5, нолучим следующую геометрическую модель (см. рис. 2.3.2). Ясно, что в таком коде все кодовые слова (комбинации) являются разрешенными, и код корректирующими свой ствами не обладает.

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

Рис. 2.3.2. Геометрическая модель кода СОК с одним основанием Таким образом, модель кода СОК с двумя основаниями есть «каркас тора»:

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

Рис. 2.3.3. Геометрическая модель ко да СОК с двумя основаниями Заметим, что расстояние между двумя кодовыми словами Д и Aj можно определить как наименьшее число дуг, которые следует пройти при движе нии из точки 4 к точке Aj. Глубина ошибки для основания р,^ может изме ^ = 1 до Ajt = —, где — - целая часть числа, полученного при няться от делении р^ на 2, что равно числу малых дуг, которые приходится проходить при движении по дуге соответствующего модуля. Например, для модели, представленной на рисунке 3, глубина ошибки для модуля р^=5 может при нимать значения от А, =1 до А, = — = 2, для основания ^2 =3 глубина ошиб ки равна А2=1. Определяя расстояние между точками А^ и А^, движемся сначала по дуге А^А^^А2, затем по дуге A2A^, либо сначала по дуге /Ij^io затем по дуге A^QA^AT, ЧТО означает, что искомое расстояние равно с^ ^ = 2.

/^^ Чего же мы добились и какой ценой? Полученная модель отражает свойст во цикличности, но не позволяет изображать код СОК с числом оснований, превышающим 2.

Сделаем еще одну попытку улучшения геометрической модели, иллюстри рующей код СОК. Пусть каждой кодовой комбинации соответствует единст венная точка плоскости, причем точки, сгруппированы в окружности по сле дующему критерию. Существует единственная минимальная окружность та кая, что вне этой окружности нет точек, определяющих кодовые комбинации полного диапазона, будем называть данную окружность внешней или окруж ностью нулевого уровня. Существуют окружности первого уровня, соответ ствующие первому основанию кода СОК, такие, что все точки, изображаю щие кодовые слова, имеющие одинаковые остатки по первому основанию, не выходят за пределы соответствз^ющей окружности. В исходной модели точ ками касания окружности нулевого уровня с окружностями первого уровня являются точки, определяющие кодовые комбинации, имеющие остатки, равные нулю, по всем основаниям, начиная со второго, кода. Окружности второго, третьего и т.д. уровней, строятся по аналогии, они соответствуют второму, третьему и т.д. модулям кода СОК. Таким образом, точки касания окружностей i-ro уровня с окружностью (i-l)-ro уровня, определяют кодовые слова, у которых остатки по всем основаниям кода совпадают, кроме остатка по i-му основанию. Определения расстояния между кодовыми словами и глубины ошибки остаются теми же, что и для предыдущей модели, за той лишь разницей, что в процессе работы конструктивные части модели прихо дится переориентировать.

На рисунке 2.3.4 изображена модель кода СОК, представленного основа Рис. 2.3.4. Геометрическая модель кода СОК с тремя модулями (исходное состояние) ниями Pi =2, j^2 = 3, Pi =5.

Модель отражает свойство цикличности кода СОК, позволяет изображать код СОК с любым числом оснований, но теряет свойство «стационарности»:

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

Например, для определения расстояния между А2б={о,2Л) и Л,, =(1,1,4) представляем модель в виде, изображенном на рисунке 2.3.5. Определив наименьшее число дуг, которые следует пройти при движении из точки А^в к точке Л„ (/^26 -^1б -Л -^^9)» получаем, что расстояние между ^2^ и /I,, равно 3.

Каждая из описанных моделей кода СОК обладает своими достоинствами, но, к сожалению, и имеет вполне определенные недостатки.

Перейдем теперь к построению геометрических интерпретаций гибридного Рис. 2.3.5. Геометрическая модель кода СОК с тремя модулями (переориентированная) кода Процесс преобразования чисел из кода СОК в код AN -СОК можно изобра зить в следующем виде (см. рис. 2.3.6).

На рисунке 2.3.6 показан пример геометрической интерпретации перевода чисел кода СОК в AN -код, а именно остатков по основанию р = 5 в 3N -код.

Говоря о геометрической модели гибридного кода, очевидным является то.

.Л^ N ^ Nи Рис. 2.3.6. Геометрическая модель перевода чисел из кода СОК в код AN-СОК и обратно что на величину расстояния между кодовыми словами будет влиять как арифметическое расстояние между числами AN-кода (количество ненулевых членов в минимальной форме модуля разности этих чисел), представляющи ми остатки по модулю Л,/?,-,так и базовая конструкция кода СОК. Так модель гибридного кода, построенного на базе безызбыточного кода СОК, может быть представлена в виде иллюстраций определения арифметического рас стояния между /liV-остатками по определенному модулю, причем для каждо го основания в отдельности.

Например, на рисунке 2.3.7 изображена модель определения арифметиче ского расстояния между AN -остатками по модулю Ар, где А = 3, р = 7. У ка 3N ^14 ^' Рис. 2.3.7. Геометрическая модель определения арифметического расстояния между AN -остатками по модулю Ар ждой кодовой верщины указан арифметический вес соответствующего числа (так w(3iV2) = Л^ь) = ^(00 И о) = w(o 1 Ою) = 2, w(3?/5) = ^(^15) - ^(01111) = vv^lOOOi] = 2 ). По числу AN^ однозначно определяется //;

. Пусть число Ni^ - ближайщее из данных к NQ с учетом направления об хода (соответственно ANi^ — ближайщее к ANQ );



Pages:     | 1 || 3 | 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.