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



на правах рукописи

БЛИНОВСКИЙ Владимир Маркович

ЗАДАЧИ АСИМПТОТИЧЕСКОЙ КОМБИНАТОРНОЙ ТЕОРИИ КОДИРОВАНИЯ

05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Москва - 1996

Работа выполнена в Институте проблем передачи информации РАН.

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

доктор физико-математических наук, Бассалыго Л.А. доктор физико-математических наук, проф. Левенштейн В.И, доктор физико-математических наук, проф. Сиделышков В .И.

Ведущая организация: Московский физико-технический институт.

Защита состоится «............»................................. 1996 г. в ............ часов на

заседании диссертационного совета Д.003.29.01 в Институте проблем передачи информации РАН по адресу: 101447, Москва, ГСП-4, Большой Каретный пер., 19.

С диссертацией можно ознакомиться в библиотеке Института.

Автореферат разослан «...........»........................1996 года.

Ученый секретарь диссертационного совета Д.т.н.

С.Н. Степанов

Общая характеристика работы

Актуальность тем,ы. Комбинаторная теория кодирования является одной из основ при изучении возможностей повышения помехоустойчивости передаваемой информации. Методы асимптотической комбинаторной теории кодирования (АКТК) в ряде случаев позволяют получить асимптотические оценки корректирующей способности систем передачи информации. Асимптотическая комбинаторная теория кодирования является важной составной частью комбинаторики и общие комбинаторные методы, возникшие далеко за пределами кодирования находят применение в АКТК. Исследование проблем, возникающих на стыке асимптотической теории кодирования и а комбинаторики оказывается очень плодотворным и представляющим несомненный интерес как с точки зрения теории так и для приложений. Таким образом развитие АКТК как раздела математики представляется актуальной задачей.

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

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

Основное содержание работы

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

Пусть пространство Хемминга двоичных последовательностей длины п с метрикой Хемминга •). Код в гл. 1,2,3 определяется как произвольное множество А(п,К(п)) С К(п) = |— число элементов в коде А(п,К(п)). Пусть Cn(a,t) =

£iÊ/y:<i(ï,0=ta:- сфера, a Bn(a,t) = Zl=o C„(û,r)- шар Хемминга радиуса i с центром а 6 В гл. 2,3 рассматривается двоичный симметричный канал с вероятностью инверсии двоичного символа р. Рассматривается ситуация, когда по каналу необходимо передавать сообщения из множества 1, К(п). Для этого задается код Л(п,К(п)) и каждому сообщению i ставится в соответствие кодовый вектор a(i) G А(п,К(п)) (сообщение г кодируется). По каналу передается вектор а(г). Пусть Р(з/|а(г))— вероятность того, что па выходе канала будет получена последовательность у 6 при условии, что на вход капала подавалась последовательность (кодовое слово) а(г) € А(п,К(п)):

Р(у\а(г)) = 1

Для конечного множества N и целого i > 0 через обозначим совокупность всех неупорядоченных п— элементных подмножеств с попарно различными элементами. Произвольное отображение

задает правило декодирования в список объема L. Впервые списочное декодирование рассматривалось в работах Элайеса и Возен-крафта. Если функция ур/, задана соотношениями

<Рь(у) = {а,}', = г.гд min _ d(y,a), \<pL{y)\ < L,

i£*,Ji(»))\(i,;)=1,1-1}

то говорят, что функция yi, реализует декодирование по минимуму расстояния в список объема L. Декодирование вектора у 6 F£ в список кодовых векторов считается успешным, если а; £ <fiL{y), иначе считается что произошла ошибка. Пусть

РА(р, L, а) = Y1 Р(у\а)~

вероятность ошибки декодирования списком объема L кода А(п, К(п)) при условии, что был передан вектор а е А(п,К(п));

Pa{p,L) = -т^-г £ Рл{р,Ь,а)~

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

EUR) = -liminf min bgP,(p,L) R

•»—» A(r>,K(n)):hSK(n)>Rn П

EL( 0) = -liminf min

»-«> A(n,K(n)):K(n)>o(r,) П

o(n) —> oo ; o(n)/n —> 0, когда n —> oo.

Ei(R) называется функцией надежности двоичного симметричного канала при декодировании списком.

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

Теорема 1. Для некоторого е > 0 при 0 < р < с и 1 /2-е < р < 1/2 справедливо неравенство

L+1 ✓

ад < &(0) 4 £ logip^+^l - ру-W+D (1)

л ^

+

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

Щ0) > Ёь(0) (2)

(в общем ситуации произвольного дискретного калала без памяти такая процедура в рассматриваемом случае проделана А.Г.Дъячко-вым), основная задача состояла в построении верхней оценки для

El(0). В теореме 1 получена такая оценка для малых и больших значений р. Из ( 2) следует, что одежка ( 1) точна. В теореме 1 приведена оценка только для Ej_(0) потому что в общей ситуации только в этом случае при малых скоростях удается найти точное значение £'l(R)- Однако известные рассуждения с использованием утверждения теоремы 1 и следующего неравенства Шеннона - Гал-лагера - Берлекэмпа:

P^,R,L) > Р.(р,Л( 1 + n7n),OP„.(i>,log(£' + 1)/п,£),

где п, п', d, L— натуральные числа, (! + 1 > L,

Pn(p,R,L) = min ?a(p,L),

.4(n,A(n)):logÄ(>i)>Hn

Pn[p,R,L) = min Pa(p,L),

a(n,k (n)):logA (n)>Rn

Pa{p,L) = max PA(p,L,a).

ü£a{n,k{n))

приводят к оценке

Ei(R) < ¿¿(0) - - EM (3)

где E,(ß)- известная верхняя оценка сферической упаковки, справедливая при всех значениях R. Наилучшая оценка в ( 3) достигается в случае, когда ц удовлетворяет равенству

Отметим, что оценка (1) остается справедливой, если в определении Ei(R) заменить Рл{р,Ь) на PA(p,L). Кроме того нетрудно видеть, что

Ёт Т - log (2^И)) , L —> со ;

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

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

В главе 3 получены оценки числа линейных кодов, удовлетворяющих оценке Гоблика на радиус покрытия.

Разд.3.1 является вводным. В нем содержатся предварительные сведения, используемые в этой главе. Для линейного кода Д,ц С Fj", |Ant| = 2к, радиус покрытия гА определяется равенством

гх = max min día, у).

Граница Гоблика утверждает, что существует линейный код (впрочем это утверждение верно и для нелинейных кодов той же мощности), такой что справедлива оценка

гл/п <ir_1(l-fc/n + 21ogn/n). (4)

Здесь Н(х) = -г log г — (1 — z)log(l — г)— функция двоичной энтропии.

Для произвольного кода Лц* справедлива также асимптотическая оценка сферической упаковки:

гл/п> H~l(l-k/n).

Таким образом оценка ( 4) является асимптотически точной. Основная проблема, решение которой получено в этой главе состоит в оценке доли линейных кодов, для которых справедлива оценка

гА/п< Н~1(1-к/п + о(1)). (5)

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

Пусть {An}— последовательность чисел, такая, что Д„ = о(п); ДцП-1'2 —> еж, когда п —► оо. Для последовательности {s„}; sn > О будем писать /(sr.) = 0(s„) если для всех достаточно больших п выполняются соотношения оо > Ci > f(sn)/s„ > 1/Ci >0.

Ранее автором была доказана лемма о том, что для доли линейных кодов А„* С F£ большей, чем 1 - 2~0(Л"> справедлива оценка

га/п < Д~\ 1 - к/п + 0(Д„)/п).

Доказательство этой леммы приведено в разд.3.2.

Разд.3.3 содержит теоремы в которых значительно улучшена оценка доли кодов, для которых справедлива асимптотическая оценка ( 5) по сравнению с леммой из разд.3.2. Цетральными здесь являются теоремы 2 и 3. В теореме 2 утверждается, что если для некоторого Мп С выполнено условие

2*-п|М„|>20(("ла),/3\ (6)

то для доли линейных кодов Апк С F2 , большей чем 1 — выполняется соотношение

D°^v\M*) + Ank = FÏ (7)

(здесь DX[B) = {6 G F2™ : ¿(},В) < А}). Отметим, что если мы хотим получит оценку доли линейных кодов как указало выше, условие рассмотрения окрестности Z)°",lA"'1/3)(Mn) множества Мп является существенным т.е. нельзя заменить равенство ( 7) на следующее:

Мп + Апк = F,\

В случае, когда Мп = Вп{0, г) из теоремы 2 (из соотношений ( 6),( 7)) получаем оценку ( 5), которая справедлива для доли линейных кодов большей, чем 1 —

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

( 5) для доли линейных кодов, большей, чем 1 — 2_0'Л™'. Однако остаточный член (о(1)) в формуле ( 5) при таком подходе оказывается больше.

Для линейного кода An>¡ С F¡ через А = {Л°,..., А"} будем обозначать спектр кода Ап)< (здесь А' = \А„ь С„(0,г)|- число кодовых векторов, расстояние которых от 0 равняется г). Для каждого р € [0,1] вероятность необнаруженной ошибки Ри<-(р, Апк) определяется равенством

1=1

Величина Р„г(р, Л„*) является вероятностью того, что выход двоичного симметричного канала без памяти с вероятностью инверсии двоичного символа р будет кодовый вектор, при условии, что передавался нулевой вектор.

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

Р(п,к)— mia max Р»е(р, А,^}.

Aucf? pe[o,i]

Ясно, что Р(п, к) > РиС(1/2,Апк) = 2к~п-2~п. Основное содержание этого раздела состоит в доказательстве следующей теоремы.

Теорема 4. Для некоторой константы при всех тг, к справедлива оценка

Р(п,к) < (C4/bñ+l)2'"\

В разд.3.5 рассмотрено одно применение теорем 2, 3 для понижения сложности задания кода, исправляющего ошибки и дефекты. Рассмотрим канал с дефектами и ошибками. Пусть Un = {1,..., гг}. Для произвольного вектора х = (ari,..., х„) £ F? х J С Un положим = (i,!,.. где ¿i < ¿2 < ... < i\j\, ij е J, j Е ¡7|j|.

Определим функцию : F£ -»

/ ч ( \ Г У>, i £ Un\ J; v(y,*\j) = (zi,...,zn); = ,.ei/.

Каналом с m дефектами называется множество

Фт ={v(-,x,j.); У С Un, |J| = m, € Ff1}.

Канал с дефектами впервые рассматривался Дыбаковым и Кузнецовым. Будем говорить, что код A(n,k,m,t) С Ff, \A[n,k,m,t)\ = 2* позволяет передавать N сообщений и исправляет m дефектов и до t ошибок, если существует кодирующая функция

р(г, tp) : Uff х Фт А(п, к, m, i) и декодирующая функция

Л(г) : F2" t/дг такие, что выполняются соотношения

€ Фт, г' €Un, z€ <f(Ö, z) < t.

Дальнейшие построения проводятся с использованием метода случайного кодирования. Под сложностью задания кода Д(п, k,m,t) будем понимать объем ансамбля, которому будут принадлежать код А(п, к, m, t), кодирующая функция р и декодирующая функция X.

Бассалыго и Пинскер показали, что существуют коды, которые могут быть использованы для передачи N сообщений и исправлять m дефектов и до t ошибок, параметры n,N,m,t которых удовлетворяют оценке

и имеют сложность построения удовлетворяющую соотношению log log £ ~ an. В этой же работе приведены два метода задания таких кодов. Первый - без дополнительных ограничений на параметры m,t: второй - с ограничением

4t/n < (1 ~ m/n)2 -о(1).

В этом разделе доказано, что при вмполнении последнего ограничения существуют коды, позволяющими передавать N сообщений и исправлять гп дефектов и до t ошибок, где n,N,m,t удовлетворяют оценке ( 8) и сложность построения таких кодов f удовлетворяет соотношению log log { ~ ('2 -I- б)^шля некоторого е € (0,1/2). Уменьшение сложности задания кодов достигается за счет выбора ансамбля из множеств линейных кодов, которые порождают покрытия множеств из F2n специальной конфигурации.

В главе 4 изучаются условия положительности пропускной способности произвольно меняющегося канала (ПМК) при списочном декодировании. ПМК (без памяти) будем называть семейство условных распределений:

Hj/|i,s); х G € П}; у &У

(X, У, П - конечные множества входных, выходных символов и символов состояния ПМК соответственно) с равенством

п

w(y|x,5) = П'ЧгФи3')! ¡=1

xer.pe Пусть

n / im w«(!/lr) Cr = max mm > :r)log —-, , ,

где ?(■),</(■)— распределения вероятностей на X и f! соответственно, а

В этой главе кодом А"' длины п, декодируемым списком объема Ь называется совокупность пар: А" = {(г(,А<);г = 1,...,А/}, где а', С Хп и {А,; г = 1,..., М} является Ь— кратным разбиением множества У1, т.е. f¡,eJ Л, — 0 для всех J, талик что \.]\ > X. Такое определение оправдывается выбором областей декодирования кода Л", а именно: если вектор у € А,, г = гь..., г^-, } < £ + 1 является выходом ПМК, то результатом декодирования списком объема Ь является ] < Ь -+ 1 кодовых векторов т.е. задало отображение

■■ ®ь(у) = : У € А,}, у 6 У-

Считается, что произошла ошибка декодирования списком, если переданный кодовый вектор х $ Фс(у). Средняя вероятность ошибки при декодировании кода А" списком объема I нри использовании для передачи сообщений произвольно меняющегося капала, при заданной последовательности состояний канала- 5 в П" определяется равенством

1 м

ад = Лп) = Т7£ £ <*"(? 5).

¡=15£У>:Ф1.(Й?1

Пропускная способность (?£, ПМК при декодировании списком объема I. определяется равенством

Сх = вир Я,

ё!= О

где

ёь(Я) = Ипмп! пиа тахРх/з, А").

х ' и—со Л»:1огМ>Л» 460" 4 '

Несложно доказать, (аналогично тому как это делал Алсведе в случае, когда Ь = 1), что величина Сь может принимать одно из двух значений: Сь = 0 или Сь ~ Сг > 0. В той главе получены необходимые и достаточные условия на величины ги(у|ж,з) при которых выполняется равенство Сь — 0. Эти условия являются обобщением

условий Эриксона на случай Ь > 1 (в случае I = ] доказательство справедливости этих условий принадлежит Чисару и Нарай-ану). Основным в этой главе является исследование достаточных условий для того, чтобы выполнялось равенство 6/, = С,- Здесь показано, что для произвольного заданного ПМК найдется число ¿о < такое, что при Ь > Ь0 выполняется равенство Сь = Ст. Получена следующая верхняя оценка на минимальное Ь0 с указанным свойством (обозначим его ¿о):

'Ь0<^\Щ1СТ. (9)

Интересной задачей представляется построение хороших оценок (верхних и нижних) на 2о. В диссертации построена верхняя оценка для Ьо для одного класса каналов. А. именно: пусть П = {¿1,...,5|П|}, X = {асх,...,1|*|} С П\ «1 < 52 < ... < 5|я|! хг <

Х2 < ... <-31*1,

= 14-5 О ,для других у € Л1

Для определенного этими соотношениями ПМК получена следующая опенка на Ь0:

<2)1 ~3\Х\/

В ряде случаев эта оценка лучше общей оценки ( 9).

Сформулируем основные результаты диссертации.

1. Проведено исследование верхних граяид для экспоненты вероятности ошибки декодирования списком фиксированного объема при малых скоростях передачи. Полученные оценки являются асимптотически точными про нулевой скорости кода и являются продолжением границы Шеннона - Галдагера - Берлекэмпа на случай декодирования списком. Здесь же яолучен ряд соотношений

между параметрами, имеющими отношение к списочному декодированию.

2. Построена оценка доли линейных кодов, которые являются асимптотически оптимальной г— сетью в пространстве Хэмминга, Существенным здесь является установлений того, что доля таких кодов превышает 1 - 2-п,,(п), о(п) —♦ оо, когда п —» оо. Эта оценка находит многочисленные применения, одно из которых - понижение сложности задания кодов, исправляющих дефекты и ошибки, рассмотрено в диссертации.

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

Апробация работы. Результаты диссертация докладывались на межлабораторных семинарах по теории кодирования и теории информации Института проблем передачи информации РАН, семинарах в научных центрах зарубежных стран: Университет г. Ви-елефельд (Германия), Болгарский Математический институт ВАН (Болгария), Университет Макуоер (Австралия), Университет г.Тель-Авив и Технион (Израиль). Они были доложены на: Третьем международном семинаре по теории информации "Сверточные коды; связь с многими пользователями", Сочи 1987; Международных ворыдопах по алгебраической и комбинаторной теории кодирования, Варна 1988, Новгород 1995; Франко - Советском и Франко -Израильском воркшопах по алгебраической теории кодирования, Париж 1991, 1993; конференции по дискретной математике, Вел-дховен 1992; Международном симпозиуме по теории информации

и ее приложениям, Сидней 1994; Международном симпозиуме по

теории информации, Вистлер 1995".

Литература

[1] В.Блиновский "Покрытиепространства Хэммингатрансляциями множеств на вектора линейного кода", Проблемы Передачи Информации, т.27, N3, 1991, с.196-201

[2] В.Блиновский "Асимптотически точные равномерные границы на спектр смежных классов линейных кодов",Проблемы Передачи Информации, т.26, N1, 1990, с.83-86

[3] В.Блиновский "Асимптотически точная граница на спектр смежных классов линейных кодов", Труды 9-ой Всесоюзной конференции по теории кодирования а передачи информации, Одесса, 1988, с. 168-170

[4] V.Blinovsky "One inequality from the information theory", Abstracts of the IEEE Information theory workshop, Haifa. 1996, p.62

[5] V.Blinovsky "The lower bound for cardinality of codes correcting errors and defects", Lect.Notes in Comp.Sei., N575, SpringerVerlag, 1991, p.102-112

[6] В.Блиновский "Граница для вероятности необнаруженной ошибки", Проблемы Передачи Информации, т.32, N2, 1996, с.

[7] V.Blinovsky "New bound on the probability of undetected error",in Proc. of the IEEE Int.Symp.Inform.Th., Whistler, Canada, 1995, p.57

[8] В.Блиновский "Нижние границы для вероятности ошибки при декодировании списком фиксированного объема", Проблемы Передачи Информации, т.27, N4,1991, с.17-33

[9] V.Blinovsky "The exponent of the error probability for the bounded list decoding codes with zero rate", Proc.of the Third Workshop on Inf.Th.'Conv.Codes; Multi-user Comm.', Sochi, 198T, p. 189-191

[10] V.Blinovsky "List decoding", Diskrete Math., 106/107, North-Holland, 1992, p.45-51

[11] V.Blinovsky and M.Pinsker "One relation which is used to obtain the capacity of the arbitrary varying channel under list decoding", Proc.Fourth Int.Workshop 'Algebraic and Comb.Coding Th.', Novgorod, Russia, 1994, p.30-34

[12] V.Blinovsky and M.Pinsker "One method of the estimation of the size of the list for list decoding in arbitrary varying channel", Proc.of 1S1TA-94, Sydney, Australia, 1994, p.607-609

[13] В.Блиновский, П.Нарайал, М.Бинскер "Пропускная способность произвольно меняющегося канала при списочном декодировании", Проблемы Передачи Информации, т.31 ,N2, 1995, с. 3-19

[14] V.Blinovsky "List decoding", Discrete Math., v.106/107, Reprint in Topics of Discrete Math., N7, A collection of contributions in Honour of J.van Lint, 1992, p.45-51

[15] V.Blinovsky "Estimation of the number of linear codes asymptoticaly achieving the Goblick bound for covering radius", Proc.of the First Int, Conf. on Algebraic and Comb. Coding Theory, Varna, Bulgaria, 1987, p.22-24