автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методы исправления ошибок в модульной и порожденных ею метриках

САНКТ-ПЕТЕРБУРГСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ Г> п На правах рукописи

V н

ДАВЫДОВ Вячеслав Анатольевич

МЕТОДЫ ИСПРАВЛЕНИЯ ОШИБОК В МОДУЛЬНОЙ И ПОРОШЕННЫХ ЕЮ МЕТРИКАХ

Специальность 05.13. 01 - Управление в технических

системах

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

С. -Петербург 1993

Работа выполнена в Государственной академии аэрокосмического приборостроения, г. Санкт-Петербург.

Научный руководитель - Доктор технических наук

профессор Е.Т.Мирончиков

Официальные оппоненты:

доктор технических наук, профессор В.Д.Колесник

кандидат технических наук Б.Н:Степанов

Ведущая организация - Санкт-Петербургский институт информатики

к автоматизации Российской Академии Наук.

Защита диссертации состоится "_" _" 1994 г.

в _ часов _ мин. на заседании специализированного совета

К 063.21.03 Государственной академии аэрокосмического приборостроения по адресу:

190000, Санкт-Петербург, ул. Большая морская, 67

С диссертацией можно ознакомиться в библиотеке института, автореферат разослан "_"_" 1Э93 г.

Ученый секретарь специализированного совета

к.т.н., доцент В.В.ФильчакоБ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

цель работы. Целью настоящей работы является построение и

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

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

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

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

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

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

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

Практическая ценность работы состоит в том, что

разработка основных вопросов диссертации позволила:

-построить новые эффективные коды для передачи сообщений по широкому классу каналов;

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

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

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

Тем самым расширена область использования кодов в системах передачи информации.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на int. workshop on Algebraic and Combinatorial Coding Theory, Bulgaria, 1992, на IEEE Information Theory Workshop, Japan, 1993, а также на семинаре по теории информации и кодирования кафедры АСУ СПИАП (Санкт-Петербург, 1993).

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

-понятие гомоморфности метрик и методы построения кодов в метриках, гомоморфных модульной;

-методы декодирования кодов в модульной метрике; -границы мощности и скорости кодов в модульной метрике; -условия согласованности метрик битовых сдвигов и вставок

-4-

символа 0 с дискретными каналами.

Структура и объем диссертации. Диссертация состоит из введения, шести разделов, заключения, списка литературы и приложений. Работа содержит 888 страницы основного текста, 4 рисунка, список использованной литературы содержит 50 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во-введении раскрыта актуальность темы, сформулирована цель исследования, охарактеризована новизна полученных результатов, отмечена их практическая значимость и раскрыто основное содержание работы.

Первый раздел посвящен вопросам оценки мощности кодов в модульной метрике.

Пусть Vе (у^, V^.....V > - вектор длины п, компоненты

которого принадлежат алфавиту А =<о, 1.....со-п>. Весом

вектора и=(и ,иг, .. и^) в модульной метрике называется величина численно равная

«„(«)- I I

1-1

Расстояние между двумя векторами и и V длины п в модульной метрике определяется как

п

Л < и,V ) = У I и, -V |.

«-, ' 1

Пусть в множестве Ап задан о-ичный код длины п с расстоянием <1 в модульной метрике, слова которого имеют фиксированный вес Обозначим через а(п, ц) максимально возможное число слов в таком коде.

Теорема 1.1

с! п со-п/г

А(п,й,и,0) < -- ,

" - п<5-П<» - с!/2)

при условии, что знаменатель положительный.

Полученная оценка мощности равновесных кодов в модульной метрике при о = г переходит в известную границу Джонсона для равновесных двоичных кодов в метрике Хэмминга. Теорема 1. 2

а- 1

А С п, с!, V, 0) С Сп / V) £ АС п-1, а , , (2> • ,5 . J-»

Следствие.

п <3- 1

АСп.а,«,0) < п(0-П-ц Е АСп-1,й,«^-С0-1>,0)-.).

J• 1

Для 0=2, полученные рекуррентные оценки дают известные неравенства для мощностей равновесных кодов в метрике Хэмминга.

Пусть А(п,а,о) - максимально возможное число слов о-ичного кода длины п с расстоянием й в модульной метрике.

Теорема 1.3

гл

АСп,а,0) < - ,

2d - пСО-1)

при условии, что знаменатель положительный.

При 0=2 полученная граница совпадает с известной границей Плоткина для максимального числа слов двоичного кода длины п с расстоянием й в метрике Хэмминга. Теорема 1.4

Для скорости Я любого кода б длины п над алфавитом ¡4=С 0,

модульное расстояние которого удовлетворяет

неравенству

п(0-1.5)

0-1

справедлива верхняя оценка

I? < 1 -

нг (" "йГ"(1 " „"о-о ) )

1од20

В случае 0=2 ограничение на параметры кода принимает ви а <п/2, а сама оценка скоростисовпадает с известной границе Элайеса для скорости двоичных кодов в метрике Хэмминга. Теорема 1.5

Для достаточно больших п, удовлетворяющих условию ййп/2, любого о существует блоковый код БСп.й.О), скорость я которое оценивается неравенством

ф

Й > 1

1од О

где (рса/п) = шах (И^)-Н С v/<1 > 3 +Н .

о<\><а/п г 3 .

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

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

Пусть 2- кольцо целых чисел. Подмножество целых чисе а={о,1, ... о-1), где й - произвольное целое число большее 1 будем называть алфавитом. Определим а", как множество о-ичны векторов длины п.

А" = {а= С а , а.....а) , а € А , 1 < 1 < п }

1 г п I

Выберем конечное поле огсд), д=рт, где р-простое число

m-натуральное число и q > п. В дальнейшем такое поле будем обозначать f. Обозначим через f* множество, ненулевых элементов поля f. Определим отображение множества q-ичных векторов длины п на множество полиномов от формальной переменной х над полем F. Для этого поставим в соответствие i-й позиций ( 1 < i < n) векторов множества а" ненулевой элемент а{ поля f. Множество

выбранных элементов 2 = la^.a^.....an)S F*' бУДен называть

множеством локаторов кодовых позиций, а сами элементы af локаторами. Определим отображение з. вектора u=(u ,u ,

L 1 2

,u ) в локаторный многочлен u(x) по правилу

п

п и

3„ (и) = и(х) = П ( 1 - ха"' ) (» 1

Множество корней произвольного многочлена у(х) обозначим supp(y). Пусть Fix]- кольцо многочленов от формальной переменной х над полем F. Выберем многочлен g(x) е Fix] такой, что

supp(g) fl £ = 0, deg(g) = t+l, д(0)=0.

Пусть s(x) 6 Fix]- многочлен степени меньше или равной deg(д)-1, свободный член которого равен 1. Определим множество векторов а = 4(a,g,s) следующим образом-.

d = с u, U е а", 3р (u) = s(x) mod gCx) }

Ошибки, не уменьшающие абсолютной величины каждой из компонент слова, будем называть однонаправленными увеличивающими ошибками, а не увеличивающие абсолютной величины каждой из компонент - однонаправленными уменьшающими. Теорема 2.1

Множество векторов Л является кодом, исправляющим t однонаправленных увеличивающих ошибок. Следствие 1.

Код А, исправляющий t увеличивающих ошибок, является кодом, исправляющим t уменьшающих ошибок.

Пусть б - целое число такое, что 0 < о с Et. Определим множество векторов в = в (г,g,s,б) следующим образом:

п

В = { U, иеЛ,Уи=б mod(2t+l) >.

L, t 1 - 1

Теорема 2. 2

Множество слов В =£(£,g,s,6) является кодом, исправляющим t ошибок в модульной метрике.

Пусть Ап""'= { а= С а , а.....а а £ А, OCiCn >.

О 1 n i

Определим множество слов B*=s*(£,g,s,б) s к""1 следующим образом

* п

В =(U е Ап*':Си ,. ,u ) £ I«(£,g,s), У u =б mod(2t+l)>.

1 п i

i-O

Следствие 1.

Множество В (£,g,s,6) является кодом, исправляющим t ошибок i модульной метрике.

Пусть х- конечное множество слов , на котором определена некоторая метрика д. Определим отображение множества х i множество ап Q-ичных слов длины п.

5 : 1 » А".

п

Будем считать, что отображение s ^обладает следующими свойствами. Для любых х, у е X, х * у, имеем

1) 9 (х) * S (у).

п п

2) dM(i?n(x),!?n(y)) > е(х,у).

3) На образе 1 в д" определено обратное отображени

1 (с), ces (X).

п п

Ошибки, произошедшие в слове х и не уменьшившие модульный ве каждой компоненты s (х), назовем однонаправленным

п 4

увеличивающими ошибками в метрике д. Соответственно, ошибки

х не увеличившие вес каждой компоненты § (х)

п

однонаправленными уменьшающими в д. Определим коды б , в и о* в метрике д.

е = Б (£ , g , s ) = 1 ( 5 (X) П jJ{£,g,s) ), п п

D = ZX £ , g , s , б ) = g"'( S (X) П EC£,g,s,6) >,

п п *

D* = £>*(£,g,s,6) = «Г'( 5 (X) П В* (Е , g , s , б ) ).

п л

Из определения отображения и гомоморфности метрики g модульной метрике следует, что код б исправляет t однонаправленных ошибок в метрике д, а коды z> и в* исправляют любые t ошибок в метрике д.

Пусть ip(z) - минимальное число > z, для которого' существует GF(ip(z)). Для кодов в модульной метрике, отображение $ можно рассматривать как тождественное

п

отображение множества а" q-ичных векторов длины п на себя. . Тогда случае выполнения строгих равенств ip(n+t) - n+i, <p(n) = n, получаем оценки

|s(a,n,s,6)| >

(n+l)'•(2t+l)

'(2, n, s, б) | >

n* • (2t+ 1 )

Пусть д С х) =х(1-р~,х)(1-|3~'х) ... <1-р~'х) И <0,0 ,0г>

... , э > П а = а, где £ = ..., ьс 5 - множество

г 1 г п

локаторов. Предположим, что определено множество векторов X длины к с заданной на нем метрикой д и отображение & (х).

71

Зададим код м длины т, обнаруживающий одиночную ошибку в метрике д. Пусть число слов такого кода больше либо равно ц-\, где ч-число элементов поля г. Слова кода ж будем обозначать векторами а и ь.

Пусть заданы вектора ао»а?. ••• длины которых равны

1 ,1 , ...,1 соответственно, Обозначим через |а |а I...

О 1 ( О 1

|atl вектор, у которого на первых 1 , позициях расположен вектор ао> на следующих позициях - вектор а}, и. т. д.

Пусть требуется передать информацию, содержащуюся в векторе u е X. Построим код } = £(и,д,м), состоящий из слов вида

v = |u laj... |aj , u € X, а € Л , 1 < i < t.

Процедура кодирования состоит из следующих этапов.

1)По информационному вектору и длины к вычисляется

ПОЛИНОМ и(х) = 30( § (U) ).

L п

2)Определяются значения полинома и(х) в точках множества

supp (g): а^ = , 1 < i < t.

3)3начение a{ кодируется в слово at кода м.

Слова .....будем называть суффиксами, а слово и

- основной частью, или информационным словом. Построенный код $ имеет длину N = к + tm и мощность = |х |. Определим множество х(б) следующим образом

Х(б)- { и е X: vlf(s (u)) mod (2t+l) = б.)

М 71

Найдется х(б), мощность которого удовлетворяет неравенству |х(б)| > |x|/(2t+n. В дальнейшем будем считать, что е качестве х(б) выбрано именно такое множество.

Построим код ?(£,д,б,л). Слова кода i имеют следующи!

ВИД:

V = |u |afI ... Iatl.

где at £ м, к i< t, a u e х(б). Процедура кодирования кода ь совпадает с кодированием кода } за исключением первого этапа, на котором передаваемая информация кодируется сначала в словс и е х(б). Построенный код $ имеет длину N = k + tm и мощност] |?|>|Х|/(2t+l). Теорема 2.3

Код 3- = д,ЛО исправляет t однонаправленных ошибок i

метрике g.

Следствие 1.

Код ? = 3(Z,g,6,H) является коЗом, исправляющим t ошибок в метрике Q.

Рассмотрим алгоритм декодирования ^ = <4(a,g,s) кодов, исправляющих t однонаправленных ошибок в модульной метрике. Пусть на кодовое слово а е 4 наложился вектор увеличивающих ошибок е веса Р < t. Тогда имеет место тождество Ь(х) = а(х>е(х) = sCx)e(x) mod g(x), ГДе bCxJ =Зр tb) . а(х)0£Са), е(х)=ЗрСе).

Обозначим произведение полиномов ьсх) s"J(x) через у(х). Тогда приведенное выражение можно рассматривать как стандартное ключевое уравнение, для решения которого могут применяться различные способы. Лемма 2. 1

Остаток г ^(х ) степени pit, полученный в результате применения

алгоритма Евклиба к полиномам д(х) а является искомым

полиномом е(х).

Рассмотрим особенности применения алгоритма Евклида для

декодирования я=8(2, g,s,б) кодов в модульной метрике. Будем

считать, что на слово а е ® наложился вектор ошибок е,

являющийся суперпозицией вектора увеличивающих ошибок и и

вектора уменьшающих ошибок v. При этом сумма весов векторов и

и v не превосходит величины t. Пусть u<x> = 3„(и), v(x)=3!,(v),

е(х)=3!1(в). Тогда выполняется тождество

и С х ) и (х )

b (х) = а(х)еСх) = а(х) -з s С х ) -mod gCx).

v(x) v(x)

Пусть y(x)=b(x5s~'(x). Тогда получаем

y(x)v(x) s ц(х) mod g(x).

Вес принятого слова ь позволяет определить разность, между

степенями многочленов и(х> и у(х). Пусть

с1ед(и(1{))-с1ед(у(х>> = г. Применим алгоритм Евклида для полиномов у(х) и д(х) до тех пор, пока в качестве остатка не будет получен многочлен и(х), степень которого не превосходит величины (1+г)/г. Лемма 2. 2

Корни найденного и(х) однозначно определяют вектор

увеличивающих ошибок.

Устраняя обнаруженные увеличивающие ошибки из принатого слова ь, приходим к слову Ь', в котором имеют место только уменьшающие ошибки. Таким образом, дальнейшее декодирование осуществляется по алгоритму для ¿-кодов, описанному выше.

Рассмотрим декодирование кодов ,м), исправляющих г однонаправленных увеличивающих ошибок. Пусть в принятом слове ь на позициях суффиксов произошло ошибок, на информационных позициях - гг ошибок и ^ + 1 На первом этапе производится отдельное декодирование каждого из I суффиксов. Выделим суффиксы, на позициях которых код м обнаружил ошибки, в множество явно дефектных суффиксов. Обозначим множество корней полинома д'(х), соответствующих этим суффиксам, через 2. .Определим полином д^(х) как частное от деления многочлена д'(х) на полином ¡1 (х), где

(Их) = П < 1 - /Г'х) .

реа

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

Ь <х) = а(х)и(х),

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

полинона ь(х) от корней полинома д'(х). Обозначим такие

значения через s , s.....s . Пусть i , 1.....1 -значения

* 2 t-p 12 t-p

суффиксов не принадлежащих множеству явно дефектных суффиксов.

Доопределим s = i, i =i, a =o. По

t-p+i t-p»» t-p»i

интерполяционной формуле Лагранга определим полином f(x).

t-p+1 t-p-1 Cx -/3 )

f(x> = T Cs /I 1 П - .

^ ( i

i-1 J-1.J* I (pt-|3 )

Пусть k из t-p суффиксов s , s . . . ,s вычислены

12 t-p

неверно, вследствие ошибок веса кратного г, произошедших на

позициях слова ь, соответствующих данным к суффиксам. Тогда

полином г(х) представляется в следующем виде:

k t xg'Cx)

f Сх) = u(x> + £ —-- .

i = l (x - )

где ? .....у - ненулевые элементы поля f, в ,й.....в -

1 2 ' i 7 2

корни полинома д'(х), соответствующие искаженным суффиксам.

Домножим обе части равенства на полином а(х) = (х-/з кх-з )

1 2

<х-э з. Тогда получим

Зг у а (X )

f(x>a(x) - xg'(x) £ - = u(x)Cx-/3 ) ... (х-0 К

' 1.1 Сх-/3{) 1 *

Применяя алгоритм Евклида к полиномам ftx) и хд'(х), получим

на i-ом шаге остаток г (х) степени t^ + k < t-P, корни которого

соответствуют произошедшим увеличивающим t ошибкам и к

2

суффиксам, в которых произошло четное число ошибок. Лемма 2. 3

Остаток г1(х) степени r<t-p, полученный в результате

применения алгоритма Евклида к полиномам f(x) и хд'^(х)

совпадает с точностью до постоянного множителя с полиномом

u(x>(x-/3 J {х-(3 > . . . (х-В )=еСх>. 12 k

Декодирование $(£,д,а,м), исправляющих t ошибок в

модульной метрике аналогично рассмотренному случа! декодирования £-кодов. Отличие состоит в том, что нг информационных позициях принятого слова ь располагайте} увеличивающие и уменьшающие ошибки одновременно.

На основе методов, изложенных в данной главе, построен! семейства кодов в модульной метрике, параметры которые приведены в таблицах Приложения 2.

Третий раздел посвящен вопросам построения кодов I метриках, гомоморфных модульной.

Пусть двоичное слово и имеет длину п и вес Добавим в начало и конец этого слова две единицы. В результате получим двоичное слово и" длины п+2 веса ь+2. Перенумеруек слева направо единицы слова и" от 0 до ь+1. Последовательность нулей слова и", заключенных между ¡-й и х+1-й единицами и", где 0 < 1 <; ь, будем называть 1-й серией нулей слова и. Числс нулей в 1-й серии слова и обозначим (и) и назовем длиной этой серии. Расстояние в метрике вставок и выпадений нуля вычисляется по формуле:

ь

Си, V) = [ | э ( и ) - Б ( V ) |.

с« о

Метрика вставок и выпадений символа 0 гомоморфна модульной метрике, если отображение 5 множества двоичных слов В длинь

п

N в о-ичные вектора длины п задается следующим образом:

Каждому вектору и е В ставится в соответствие вектор длии серий нулей в(и)=&п(и) длины п=«х(и)+1, символы которого е сумме дают величину к = где «х(и)~ вес вектора и е

метрике Хэмминга.

С использованием данного отображения и оценки мощности кодов в модульной метрике получена следующая оценка мощности кода © длины N => оз с исправлением t вставок и выпадений

символа 0:

|б| >

N

Пусть и и V - двоичные вектора длины п, содержащие ь единиц каждый. Перенумеруем слева направо позиции векторов от 1 до п, а единичные символы от 1 до ь. Обозначим номер позиции, в которой расположен 1-й единичный символ вектора и, через Г1(и). Пусть 1 - некоторое целое число, большее или равное 1. Тогда для векторов и и V величина сдвигового расстояния между ними г(и,V) определяется следующим

образом:

га , если V (и) * V (у) ИЛИ для

(1 (и,У) = ья. г

р

некоторого 1 |г{(и) - «^су)! > 1, Т |г (и)-г (V)| , V = ы (и) = V (V)

в остальных случаях.

Пусть В - множество двоичных векторов длины ы, удовлятворяющих (й,к) ограничению. Обозначим через В множество слов из В, имеющих вбс Хэмминга равный р. Метрика битовых сдвигов гомоморфна модульной метрике, если отображение

отображение § следующим образом: р

Каждому вектору и 6 В поставим в соответствие л- ичный р

вектор г(и)= -(г^си),гг(и>.....гр<и)) ДЛИны р-

Пусть (<1,к) - ограничение отсутствует, т.е. с!=0, к=а>. С использованием введенного отображения и оценки мощности кодов в модульной метрике доказывается, что мощность кода (5 длины N с исправлением t битовых сдвигов удовлетворяет неравенству

г"*'

|в| > -- .

(21+1) N

Множество слов бей" назовем о-ичным кодом длины п.

исправляющим г перестановок (или ошибок оператора), если для любых различных и, V е б выполняется неравенство <1^(и, V) > 21+1. Расстояние <1 в метрике ошибок оператора между словами и и V численно равно минимальному числу перестановок соседних символов, переводящему иву. Обозначим через число компонент вектора и е о" равных 1, где о<1<о-1. Вектор а=(з , ...з ) назовем типом слова и. Будем считать, что

4 О 1 <3-1

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

т+- 1

символов равных т+1. Перенумеруем слева направо позиции иГт'' и символы вектора и'"1'' равные т+1. Поставим в соответствие вектору и<',в'' вектор рСт} = (р'?-1 ____р'"") длины , где

12 I т+1

-номер позиции, в которой расположен з.-й символ т+1 вектора иГт'\ Для удобства обозначений доопределим и^'^и. Метрика ошибок оператора заданная на множестве о" гомоморфна модульной метрике, если отображение определено следующик

образом:

Каждому вектору и е о", обладающему типом з, соответствует вектор р, у которого на первых позициям

расположен вектор на следующих позициях - векто]

р'°3, и т. д. .

С использованием введенного отображения и оценки мощност] кодов в модульной метрике получена следующая оценка мощностз О-ичного кода б длины п с исправлением ъ ошибок оператора:

<2П .

|в| > - .

<.гt + \) (п - Гп/й1)1

Пусть н - множество о-ичных слов длины п. Будем считать что слова к заданы над алфавитом А= {0,1,2.....о-1>

О-четное. Вес вектора и =(и .и.....и > е И в метрике Ли,

12 п

определяется как

п

V (и) = X Iи ], где

{«1

О

если оси < -

2

О

'V ■

о-и , если - < а <0-1.

' 2 '

Расстоянием Ли между векторами и и V длины п называется вес Ли разности этих векторов - вектора е.

(1 (И^) = V (и - V).

ъ ъ

Метрика Ли гомоморфна модульной метрике, если задано отображение 5 множества н в множество о/2-ичных слов длины

гп

2п. Данное отображение ставит в соответствие любому 1£4 пару символов (1Г1->,1Г2'>) по следующему правилу:

= 1, если 21/(2 > 1, и 1(1> = ов противном случае.

I. если Iе*= 0, и \сг= о-1-1 в противном случае.

Используя введенное отображение и оценку мощности кодов в модульной метрике показывается, что мощность о-ичного кода б длины п с исправлением t ошибок в метрике Ли оценивается неравенством

О"

|в|> —

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

На.основе методов, изложенных в данной главе, получены семейства кодов в метрике ЛИ, метрике битовых сдвигов и метрике вставок и выпадений сомвола 0, параметры которых представлены в таблицах Приложения 2.

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

Суффиксная конструкция с исправлением t ошибок в модульной метрике предусматривают наличие кода ©. Слова такого кода, добавляемые в виде суффикса к информационному сообщению и, обеспечивают кратность модульного веса вектора, получаемого в результате, величине 2t+i. Данную операцию будем называть операцией согласования веса, а код е - согласующим кодом. К б предъявляется следующее требование: для любого целого i от

О ДО 2t В 6 НаЙДеТСЯ СЛОВО веса w в i mod(2t+l).

Код может содержать не одно, а несколько слов, вес которых w удовлетворяет условию v з i mod(2t+i). Такие слова будем называть i-м классом е и обозначать б(i). Число слов в б(i) назовем мощностью i-oro класса. Пусть м-минимальная мощность классов кода б. Тогда б может использоваться не только для согласования веса, но и для передачи м сообщений.

Алгоритм поиска согласующих кодов состоит в следующем. Для каждого последующего значения длины п согласующего кода при заданных q и t определяются мощности классов б" (i) с использованием известных мощностей классов 6n"'(i), вычисленных для согласующего кода длины n-i. Указанные модности связаны соотношением

|®пи>| =Q¿' i' len"'(j)|.

(J+p) s i moa D

где d=2t+i. Таким образом, сложность вычислений параметров q-ичного согласующего кода длины п, состоящего из d классов, оценивается 0(n*q-d), а необходимая память - 0(d).

Задача кодирования для согласующих кодов в модульной метрике СВОДИТСЯ К тому, чтобы ПО числу f= > mod (2t+1) и

информационному вектору а определить вектор ь е 6(1), где i = C2t + i-f) mod с 2t +1). Декодирование состоит в обратной процедуре. Показывается, что сложность операций кодирования и декодирования согласующих кодов в модульной метрике оценивается o(n3«Q3).

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

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

Дискретный канал К задается множеством входных векторов и и множеством выходных вектороа v. Метрика d, описывающая к, называется метрикой согласованной с каналом если для любых векторов и е V и , v^e V выполняется равносильность неравенств

p(v |и) > pcv?|u) <==> d(v?,u) < dCVg.u),

где pcv^lu) и pcv2|u) - вероятности получения на выходе канала векторов' и v2 соответственно при условии, что передавался вектор и.

Обозначим через Рт_к = Р(тI к) вероятность того, что ¿-з.я серия нулей длины к слова V на входе канала, в котором происходят только вставки символа 0, перешла в результате т-к вставок в .^ую серию длины т слова и на выходе канала. Теорема 5.1

Двоичный канал без памяти, в котором происходят только вставки символа О, согласован с метрикой V) тогда и только

тогда, когда

<Р >'

Р = —-- , Р > Р , 1 < 1 < +ОЭ

I (Р ,<-1

о

Теорема 5.2

Не существует двоичного канала, в котором происходят вставки ивыпадения символа О, согласованного с метрикой dg(u,v).

Пусть р - вероятность сдвига " любого символа 1, передававшегося слова v, на I бит влево или вправо в канале с ошибками типа битовых сдвигов. Теорема 5.3

Метрика битовых сдвигов согласована с сдвигающим каналом, г котором используется )-код с величиной Л > 21 тогда I только тогда, когда

р'

Р =--- ,Р >Р , 2 < ¡. < 1.

« р1-1 о 1

о

Однако, в общем случае не существует дискретного канал; согласованного с метрикой битовых сдвигов.

в заключении изложены основные научные и практически! результаты диссертационной работы.

в Приложениях представлены таблицы согласующих кодов кодов, исправляющих ошибки в модульной метрике, метрике Ли метрике вставок и выпадения символа 0 и метрике битовы

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Построены верхние границы мощности и скорости кодов в модульной метрике, частным случаем которых являются известные границы в метрике Хэмминга.

4. Определены условия согласованности метрики вставок и выпадений символа 0 и метрики битовых сдвигов с дискретными каналами.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. В.А.Давыдов. Коды, для исправления дефектов. Проблемы передачи информации. Москва, том 29, вып 1, 1993 г.

2. В. А.Давыдов. Коды, исправляющие ошибки в модульной метрике, метрике Ли и ошибки оператора. Проблемы передачи информации. Москва, том 29, вып 3, 1993 г.

3. G.A.Kabatianskii,V.A.Davidov,A.J.H.Vink. On erro correcting codes for three types of channels Proc.Int.Workshop on Algebraic and Combinatorial Codin Theory, Bulgaria, 1992, pp. 101-103.

4. V.A.Davydov, V. Yu. Krachkovsky. A New Class o: Additiv-Error-Correcting Codes and Algebraic Error-Correctim Codes for the Constrainted Channels. IEEE Inf. Theor; Workshop, Japan, 1993.

5. В. А. Давыдов. 0 выборе дискретных сигналов в одно] задаче разрешения. В кн. 9-й Симпозиум по проблем! избыточности в информационных система: Тез. докл. Л. , 1986, с. 193-194.

6. В. А. Давыдов. 0 кодах для каналов с множественны! доступом. В кн. 10-й Симпозиум по проблеме избыточности i информационных система: Тез. докл. Л., 1989. с. 109-112.