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

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

Фролов Алексей Андреевич

Корректирующие свойства недвоичных кодов с малой плотностью проверок

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

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

3 МАЙ 2012

Москва - 2012

005016288

Работа выполнена в Лаборатории № 3 Федерального государственного бюджетного учреждения науки Института проблем передачи информации им. А. А. Харкевича Российскоий академии наук (ИППИ РАН).

Научный руководитель: (консультант)

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

доктор технических'наук, Зяблов Виктор Васильевич

Бассалыго Леонид Александрович,

доктор физико-математических наук, ИППИ РАН, главный научный сотрудник Лаборатории Н- 4

Трифонов Петр Владимирович,

кандидат технических наук, доцент, ФГБОУ ВПО Санкт-Петербургский государственный политехнический университет, доцент кафедры распределенных вычислений и компьютерных

Ведущая организация:

Федеральное государственное автономное образовательное учреждение высшего профессионального образования Санкт-Петербургский государственный университет аэрокосмического приборостроения

Защита состоится «^г » 2012 г. в Л*^ часов на заседании

диссертационного совета Д 002.077.01 при ИППИ РАН, расположенном по адресу: 127994, г.Москва, ГСП-4, Большой Каретный переулок, 19, стр.1.

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

Автореферат разослан я £2- » сх-гу&елА- 2012 г.

Ученый секретарь

диссертационного совета Д 002.077.01, доктор физико-математических наук

И.И. Цитович

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

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

Для исправления ошибок используют помехоустойчивые коды. Важнейшим обстоятельством при выборе той или иной кодовой конструкции на практике является наличие быстрых алгоритмов кодирования и декодирования. Двоичные коды с малой плотностью проверок (МПП-коды) удовлетворяют этому требованию. Однако не менее важно, чтобы алгоритмы декодирования были способны исправить большое число ошибок. Таким образом, главным вопросом является вопрос о том, насколько ухудшаются корректирующие свойства кодов при использовании простых алгоритмов декодирования. Исследованию двоичных МПП-кодов посвящено множество работ, среди которых следует особо отметить работы таких русских и зарубежных ученых, как Р. Дж. Галлагер, М. С. Пипскер, В. В. Зяблов, К. Ш. Зигангиров, А. М. Барг, Р. Таннер, Д. Спилман, Д. Маккей, Т. Ричардсон, Р. Урбаике, Д. Бурштейн, С. Л. Литсын, Ж. Земор. Доказано существование двоичных МПП-кодов, способных исправить линейно растущее с длиной кода число ошибок при сложности декодирования 0(п log2 п), где п - длина кода. Как результат, в настоящее время эти коды используются в стандартах подвижной беспроводной связи (например, LTE), цифровой телефонии; рекомендованы для использования в стандартах оптической связи, спутниковой связи, WiMAX, 802.lin.

Все исследования будем проводить для радиочастотного канала; пусть весь диапазон частот разбит на непересекающиеся частотные поддиапазоны (подканалы) при помощи технологии мультиплексирования с использованием ортогональных частот (OFDM). В связи с ограниченностью частотного ресурса дальнейшее увеличение скорости передачи возможно лишь с помощью увеличения скорости передачи в подканалах. Этого можно добиться, увеличив мощность алфавита модуляции. Из-за этого особенно интересными становятся недвоичные корректирующие коды. Недвоичные МПП-коды впервые рассмотрены в работе М. Дэви и Д. Маккея. Число работ, посвященных исследованию недвоичных МПП-кодов, сравнительно невелико. В существующих работах по этой теме приводятся результаты имитационного моделирования. Однако результатов исследований методом имитационного моделирования недостаточно.

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

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

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

Для достижения поставленных целей необходимо решить следующие задачи:

о Исследовать потенциальные корректирующие свойства МПП-кодов над полем GF(g).

о Исследовать реализуемые корректирующие свойства МПП-кодов над полем GF{q) теоретически и методом имитационного моделирования.

о Разработать СКК на основе недвоичных МПП-кодов для системы множественного доступа. Провести исследование полученной системы в канале с аддитивным белым гауссовским шумом методом имитационного моделирования.

Научная новизна. В настоящей работе впервые:

о Теоретически исследованы потенциальные и реализуемые корректирующие свойства МПП-кодов над полем GF(q).

о Предложен алгоритм декодирования МПП-кодов над полем GF(q) с вводом стираний.

о МПП-коды над полем GF{q) использованы в СКК для системы множественного доступа.

Теоретическая и практическая ценность. Получены верхняя и нижняя границы минимального кодового расстояния для МПП-кодов над полем GF{q). Улучшена асимптотическая оценка доли ошибок, гарантированно исправимых МПП-кодами над полем GF(q) с помощью алгоритма, имеющего сложность 0(nlog2n). Получена нижняя оценка относительной суммарной скорости передачи для системы множественного доступа, использующей бесшумный векторный дизъюнктивный канал. Эта оценка асимптотически совпадает с верхней оценкой.

Результаты, полученные в процессе подготовки диссертационной работы, использованы в программе фундаментальных исследований Президиума РАН «Проблемы создания национальной научной распределенной информационно-вычислительной среды на основе GRID технологий и современных телекоммуникационных сетей» по направлению «Распределенная обработка данных. Информационная безопасность сетевых технологий» (№ Госрегистрации 01200965142), программе фундаментальных научных исследований ОНИТ РАН «Архитектура, системные решения, программное обеспечение стандартизация и информационная безопасность информационно-вычислительных комплексов новых поколений» по направлению № 3.1 «Обеспечение информационной безопасности распределенных информационно-вычислительных систем» (Регистрация РАН № Ю002-251/ОИТВС 04/10396/260503-208) и разработках ЗАО «Телум», что подтверждено соответствующими актами.

На защиту выносятся следующие положения:

1. Верхняя и нижняя границы минимального кодового расстояния для МПП-кодов над полем GF{q).

2. Асимптотическая оценка доли ошибок, гарантированно исправимых МПП-кодами над полем GF{q) с помощью алгоритма декодирования, имеющего сложность 0(п log2n).

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

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

Апробация работы. Основные результаты диссертации докладывались на следующих конференциях: IEEE International Symposium on Information Theory (2011); XII Internationa] Symposium on Problems of Redundancy in Information and Control Systems (2009); XII International Workshop on Algebraic and Combinatorial Coding Theory (2010); конференциях молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы» (2009 2011). Кроме того, основные результаты докладывались на семинарах по теории кодирования в ИППИ РАН.

Публикации. Материалы диссертации опубликованы в 10 печатных работах, из них 4 статьи [1-4] в рецензируемых журналах и 6 статей [5-10] в сборниках трудов конференций.

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

Структура и объем диссертации Диссертация состоит из введения, обзора литературы, трех глав, заключения и библиографии. Общий объем диссертации 117 страниц, включая 64 рисунка и 8 таблиц. Библиография включает 83 наименования на 10 страницах.

Содержание работы

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

В первой главе исследуются потенциальные корректирующие свойства МПП-кодов над полем С-Р(г/). Показано, как меняются корректирующие свойства этих кодов при изменении их параметров, что важно для практического применения этих кодов.

В разделе 1.1 приводится введение к главе 1.

В разделе 1.2 описана структура МПП-кодов над полем СГ(д). Для построения проверочной матрицы такого кода рассмотрим блочную диагональную матрицу Н;,

( Н0 0 • • • О \ О Н0 ... О

Н,, =

V 0 0 ••■ Н0 ) Ь^Ъпо на главной диагонали которой находятся Ь проверочных матриц Но (щ, ко = ДоИо)-кода над полем (далее будем использовать термин код-компо-

нент), т = По —

Пусть <р (Щ) обозначает матрицу, полученную из матрицы Н;, произвольной перестановкой столбцов и умножением их па произвольные ненулевые элементы поля СР(д). Тогда матрица

Н =

( Ч=х (Нь) \ ЫНь)

V <Р£(НЬ) )

СЬтхЬп о

размера £Ьт х Ьп0, составленная из £ таких матриц, как слоев, является разреженной проверочной матрицей МПП-кода над полем

Определим ансамбль МПП-кодов над полем GF(q) следующим образом: Определение. Элементы ансамбля <?(6) получаются путем независимого выбора перестановок щ,г = 1,2, и ненулевых констант г = 1,2, j = 1,2,..., п, на которые умножаются столбцы получившихся в результате перестановок проверочных матриц слоев.

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

Для скорости кода С € <^(6) справедливо соотношение R ^ 1—£ (1 — Дц), равенство достигается в случае полного ранга матрицы Н.

В разделе 1.3 получена нижняя оценка минимального кодового расстояния для ансамбля £(Ь) МПП-кодов над полем GF(q). Основной результат этого раздела сформулирован в виде теоремы 1.2.

Теорема 1.2. Если существует хотя бы один положительный корень (относительно переменной 5) уравнения

F1(J,n0) = 0, (1)

тогда в ансамбле &{Ь) существуют коды {CijfJ^ Qiin j^jj = lj, такие что

d (Ci) ^ (<5ц — e) n, где e - сколь угодно малое положительное число; й"ц -наименьший положительный корень уравнения (1), а

F\ (<5, по) = (e-l)Hq(6) +

+ ¿max ( ¿log (s) - — log (ga (s, no))) , »>о V no /

где Нч(х) = -zlog^x) - (1 - x)logi(l - x) + xlog,(q - 1) - функция д-ичной энтропии, a go (s, щ) - производящая функция весов кодовых слов компонентного кода.

В разделе 1.4 получена верхняя оценка минимального кодового расстояния для МПП-кодов над полем GF(q). Основной результат этого раздела сформулирован в виде теоремы 1.3.

Теорема 1.3. Пусть С € £(Ь) и пусть <1{С) = d, тогда

R(C) sj min

где Д* (тп, й) - любая верхняя граница скорости линейного кода, г = ^, У е N.

Асимптотическая форма верхней границы дается в теореме 1.4.

Рис. 1. Нижние границы при д = 256

Рис. 2. Верхние границы при q — 256

Теорема 1-4- Пусть , Сь е £(Ъ) - это последовательность МПП-

кодов над полем СР(д) с относительным кодовым расстоянием <5(Сь) =

В разделе 1.5 приводится анализ результатов, полученных при д = 64, д = 256, д = 1024. Результаты для </ = 256 приводятся на рис. 1 и рис. 2. На рис. 1 приведено сравнение нижних границ, построенных для МПП-кодов с разным числом слоев (£ = 2,3,4,8). В качестве компонентного кода выбран код Рида-Соломона. Для сравнения приведена также граница Вар-шамова-Гилберта На рис. 2 приведено сравнение верхних границ,

построенных для МПП-кодов с разным числом слоев (£ — 2,3,4,8), в качестве функции К* использована первая граница Мак-Элиса-Родемича-Рам-сея-Велча. Для сравнения приведены также граница Варшамова-Гилберта и верхняя граница для линейных кодов (Ди(5)), полученная из границ Плотки-на, Бассалыго-Элайеса и первой границы Мак-Элиса-Родемича-Рамсея-Вел-ча.

В разделе 1.6 приводятся выводы к главе 1.

Выводы к главе 1

о Получена нижняя граница минимального кодового расстояния для МПП-кодов над полем С.Р(<7). Эта граница улучшается с увеличением числа слоев ((.). При £ ^ 8 эта граница проходит очень близко к границе Варшамова-Гилберта и начинает отходить от нее лишь на высоких скоростях.

я(б) = 1пп(д(аж

о Получена верхняя граница минимального кодового расстояния для МПП-кодов над полем GF{q). Эта граница лучше всех известных верхних границ для линейных кодов. Она улучшается с увеличением числа слоев. При I = 21 и q ^ 32 эта граница лежит ниже границы Варша-мова-Гилберта, т.е. МПП-коды с такими параметрами хуже лучших из известных линейных кодов. При q ^ 1024 не достаточно и трех слоев.

Результаты первой главы опубликованы в работах [3, 10]. Во второй главе исследуются реализуемые корректирующие свойства МПП-кодов над полем GF(q). Современные системы связи требуют высокой скорости передачи и при этом высокой надежности, следовательно, нужны длинные коды с хорошими корректирующими свойствами при простом декодировании. В связи с этим получена асимптотическая оценка доли гарантированно исправимых ошибок при декодировании с помощью алгоритма, имеющего наименьшую из известных сложность. Кроме того, предложены новые относительно просто реализуемые алгоритмы декодирования. Эффективность этих алгоритмов показана с помощью имитационного моделирования.

В разделе 2.1 приводится введение к главе 2.

Раздел 2.2 посвящен асимптотической оценке доли ошибок, исправляемых МПП-кодами над полем GF(q). Этот раздел состоит их четырех параграфов.

В параграфе 2.2.1 приводится описание мажоритарного алгоритма декодирования л/, который является обобщением двоичного мажоритарного алгоритма.

В параграфе 2.2.2 в виде теоремы 2.5 формулируется основной результат главы 2.

Теорема 2.5. Если существует по крайней мере один положительный корень (относительно переменной ui) уравнения (2), то в ансамбле &(Ь) существуют коды (с вероятностью рь : lim рь = 1), которые могут исправить лю-

6—>оо

бую комбинацию ошибок веса не более [^J при сложности декодирования 0(nlog2n), причем

w„ = Wo - £i,

где Wo - наименьший положительный корень уравнения (2), г\ - сколь угодно малая положительная величина,

h(u) + ш log2 (q - 1) - £F2(a, и, п0) = 0, (2)

где h{uj) = —wlog2 w — (1 — w) log2(l — w) - двоичная энтропия, а функция

1 при таком выборе мы получаем класс кодов на двудольных графах, в который входят коды на днудольных графах-распшрителях(в англоязычной литературе используется термин "expander codes")

Рис. 3. Сравнение зависимостей доли гарантированно исправимых ошибок от Я при д = 128

Рис. 4. Сравнение зависимостей доли гарантированно исправимых ошибок от q при Л = 0,5

F2(a,üJ,nо) определяется следующим образом:

F2(a,cj, nQ) = h (ш) + шlog2 (q — 1) ——h (ашп0) +

п0

+ шах ^ ш log2 (s)--log2 (д0 (s, щ)) -

5>0 По

, ( gi (з.пр)^ \

где а > | + е2, е2 сколь угодно малая положительная величина. Поиск максимума ведется по всем положительным s таким, что

ампд < gi (s,n0) 1 — auno д0 (s, n0)'

гДе до (si "о) производящая функция весов кодовых слов компонентного кода, <7i (s, щ) - производящая функция весов всех остальных слов. В параграфе 2.2.3 дается доказательство основного результата. В параграфе 2.2.4 приводится анализ полученных результатов. На рис. 3 и рис. 4 показано сравнение полученной оценки (зависимость помечена цифрой 1) доли гарантированно исправимых ошибок и лучшей из существующих оценок (зависимость помечена цифрой 2). Видно, насколько полученная оценка лучше.

Раздел 2.3 посвящен исследованию реализуемых корректирующих свойств МПП-кодов над полем GF(q) методом имитационного моделирования.

В параграфе 2.3.1 приводится описание двух алгоритмов декодирования: алгоритма декодирования с вводом стираний (■&,) и алгоритма распростране-

ния доверия2 (л/вр). Эти алгоритмы больше, нежели алгоритм л/ подходят для практического применения. Оба алгоритма являются итеративными.

Алгоритм л/, был предложен в работе [2] и является алгоритмом декодирования с жестким решением. Он был разработан для применения в случае наличия ошибок и стираний в слове на входе декодера. Однако в работе [2] показано, что он эффективнее алгоритма л/ в случае, если во входном слове присутствуют только ошибки. Главное отличие этого алгоритма от мажоритарного состоит во вводе стираний на места символов, подозрительных на ошибки. На каждой итерации подозрительные символы заменяются стираниями, и далее в пределах этой итерации выполняется только исправление стираний. Стирания, которые были введены и не были исправлены, после итерации удаляются. Эти две операции повторяются до тех пор, пока не случится такого, что в процессе итерации мы не исправили пи одного стирания.

Алгоритм л/вр Для МПП-кодов над полем OF(q) предложен М. Дэви и Д. Маккеем и является модифицированной версией алгоритма распространения доверия для двоичного случая. Это алгоритм с мягким решением, на входе алгоритма априорные распределения для каждого из символов принятого слова, на выходе - апостериорные. Он гораздо эффективнее алгоритма л/, однако в то же самое время и гораздо медленнее последнего, несмотря на все улучшения, сделанные в последнее время (использование многомерного преобразования Фурье, работа с логарифмами вероятностей).

В параграфе 2.3.2 рассмотрен g-ичный симметричный канал (дСК).

Исследована зависимость корректирующих свойств МПП-кодов над полем GF(q) от числа слоев (£) при разных скоростях. Получено, что алгоритм л/вр лучше работает при малом числе слоев (£ = 3 при R = 0, 25 и R = 0, 5; £ = 4 при R = О, 75). Для алгоритма результат такой - i = 6 при R = 0, 25 и R = 0,5; t = 7 при R = 0,75.

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

Показано, что корректирующие свойства (доля исправимых ошибок при условии, что вероятность ошибки на блок равна Ю-4) МПП-кодов над полем GF(q) улучшаются с увеличением длины кода (использован алгоритм л/вр).

Приведено сравнение разных декодеров (л/вр при q = 2, 8, 64) в д-ичном симметричном канале при q = G4 (рис. 5). Параметры кодов - R = 0, 5; Z = 3; пц = 6; длина п = 510 в случае декодера над GF(64), длины в остальных случаях подбираются так, чтобы количество бит оставалось таким же, т.е. п = 1020 в случае декодера над GF(8) и п — 3060 в случае декодера над

2 в англоязычной литературе используется термин "belief propagation"

о:

ш

СР(64) СР(8)

0.05 0.1

0.15 0.2 0.25 0.3

Рис. 5. Вероятность ошибки на блок, дСК при </ = 04

(З.Р(2) (длины заданы в символах соответствующих полей).

В параграфе 2.3.3 приведено сравнение недвоичных МПП-кодов с двоичными в канале с аддитивным белым гауссовским шумом (АБГШ) при разных модуляциях. Параметры кодов - Я = 0, 5; £ = 3; п0 = 6; длина п = 1020 в случае декодера над (?.Р(8) и п = 3060 в случае декодера над £¡^(2) (длины заданы в символах соответствующих полей).

На рис. С показано сравнение при использовании фазовой манипуля-ции(ФМн) с М = 8. При малых Еъ/И^ лучше оказывается двоичный код. Это можно объяснить так: входные символы записаны в коде Грэя, поэтому доля битовых ошибок оказывается меньше (примерно в \0g2Q раз), чем доля символьных. Однако в случае больших Еъ/Ио выигрывает недвоичный код.

На рис. 7 показано сравнение при использовании частотно-позиционной модуляции(ЧПМ) с М = 8. В этом случае МПП-код над (7^(8) оказывается гораздо лучше двоичного.

В разделе 2.4 приводятся выводы к главе 2.

Выводы к главе 2

о Улучшена асимптотическая оценка доли ошибок, гарантированно исправимых МПП-кодами над полем с помощью алгоритма декодирования, имеющего сложность О(п1о§2п).

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

под Еь/Ыо пошшештся отношение сигнал/шум на информационный Сит

Рис. G. Вероятность ошибки на блок,

АБГШ, ФМн

Рис. 7. Вероятность ошибки иа блок, АБГШ, ЧПМ

о Проведено исследование алгоритмов л/вр и si, в различных каналах при разных модуляциях. Показано, что s^bp лучше алгоритма В то же самое время он гораздо медленнее последнего, поэтому он не подходит для приложений, где важна высокая скорость.

о Методом имитационного моделирования показано, что МПП-коды над полем GF(q) гораздо более эффективны нежели двоичные в qCK и канале с АБГШ при ЧПМ.

Результаты второй главы опубликованы в работах [1, 2, 5-7, 9].

Третья глава посвящена применению недвоичных МПП-кодов в сиг-налыю-кодовой конструкции для системы множественного доступа. Результирующая система строится на базе технологий мультиплексирования с использованием ортогональных частот (OFDM) и псевдослучайной перестройки рабочей частоты (ППРЧ). Эта система позволяет одновременно работать очень большому числу пользователей, что очень важно для таких систем как, например, LTE и WiMAX.

В разделе 3.1 приводится введение к главе 3.

В разделе 3.2 приводится описание СКК для системы множественного доступа, использующей бесшумный векторный дизъюнктивный канал. Обозначим число активных пользователей через S. Будем предполагать, что все пользователи используют один и тот же конечный алфавит - символы поля GF(q).

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

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

Интервал времени за которое передается один вектор будем называть тактом. Будем предполагать, что в системе используется тактовая синхронизация (наличие блочной синхронизации не требуется).

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

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

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

где Л означает поэлементную конъюнкцию матриц.

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

С, Л У,- = С,,

(3)

декодирования (в рассматриваемом случае ошибочное декодирование невозможно).

В разделе 3.3 получена нижняя асимптотическая граница суммарной относительной скорости передачи для вышеописанной системы. Для того, чтобы получить эту оценку, построены оценки вероятности отказа от декодирования (обозначим ее через р, и потребуем р, < 2~т,с > 0), необходимых кодового расстояния и длины кода.

Скорость передачи информации от одного активного пользователя (в битах на один такт) равна

Суммарная скорость передачи всех активных пользователей может быть найдена как

« к

Яе(<7, 5, к,с) = 22 Ъ(<1> к, с) = Б————

п{д, о, к, с)

Пусть 5 = 77, введем теперь асимптотическую величину

р(Ък,с)= Цп1Яе07,73Лс)

<7->оо Ц

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

Теорема 3.2 При 7 < — 1п (1 — 2~с) справедливо соотношение

р (7, к, с) > -7 (1о§2 (1 - е-1) + с) .

Л. Вильхельмссои и К. Ш. Зигангиров показали, что при некоординированной передаче в случае равномерного распределения вероятностей символов на входе (как и в рассматриваемом случае) р(7, к, с) ^ —71°§2 (1 — е~7)-Предложенная конструкция позволяет обеспечить асимптотическую относительную суммарную скорость передачи сколь угодно близкую к этой верхней границе при с = е.

В разделе 3.4 приводится описание модифицированной СКК на основе недвоичных МПП-кодов для системы множественного доступа, использующей векторный канал с АБГШ.

Для борьбы с шумом необходим длинный код, декодирование которого по минимуму расстояния неприменимо на практике. В связи с этим конструкция из раздела 3.2 и этом случае не подходит. Приведем описание отличий модифицированной СКК.

Основные отличия:

Другие пош,зо-

Рис. 8. Блок схема предложенной СКК

о При передаче используем ЧПМ сМ = 5;

о Для борьбы с шумом добавлен внешний МПП-код на полем ОР(С}), где С} = цк. Таким образом код из раздела 3.2 становится внутренним (в качестве алгоритма декодирования используем алгоритм ¿^ар);

о Внутренний код будем декодировать по максимуму правдоподобия, а не по минимуму расстояния.

На рис. 8 приведена блок-схема предложенной системы.

В разделе 3.5 приводится исследование вышеописанной СКК методом имитационного моделирования. Зафиксируем следующие параметры: <5 = 64; N = 510; Я = 0, 5; г? = 64, п = 8, г = 0,125 (в качестве внутреннего кода используется код с повторением над С.Р(64)). На рис. 9 приведены полученные результаты: четыре зависимости при 5 = 4,8,12,16. Пусть требуется, чтобы вероятность ошибки на блок была меньше Ю-4, в табл. приведены значения Еъ/№о, при которых это требование выполняется. Заметим здесь, что в этом примере система эффективна далее, когда число активных пользователей составляет четверть от числа подканалов.

В разделе 3.5 приводится выводы к главе 3.

Выводы к главе 3

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

о Разработана СКК на основе недвоичных МПП-кодов для системы множественного доступа, использующей векторный канал с АБГШ. С помощью имитационного моделирования показана эффективность этой системы.

75 85

Рис. 9. Вероятность ошибки на блок от £'ь/Лго

Таблица

Зависимость Е^/Ыц от 5

5 4 8 12 16

Еь/Ма, дБ 7,10 7,91 8,81 9,86

Результаты третьей главы опубликованы в работах [4, 8].

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

Основные результаты:

1. Построены верхняя и нижняя границы минимального кодового расстояния для МПП-кодов над полем (^(<7);

2. Предложен мажоритарный алгоритм декодирования МПП-кодов над полем

3. Улучшена асимптотическая оценка доли ошибок, гарантированно исправимых с помощью алгоритма, имеющего сложность 0(пк^2п);

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

5. Показано, что МПП-коды над полем СР(ц) гораздо более эффективны, чем двоичные, в (/СК и канале с АБГШ при ЧПМ;

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

7. Разработана модифицированная СКК на основе иедвоичпых МПП-кодов для системы множественного доступа, использующей векторный канал с АБГШ. Показана эффективность этой системы.

Список публикаций

1. Фролов А. А., Зяблов В. В. Асимптотическая оценка доли ошибок, исправляемых q-ичными МПП-кодами // Пробл. передачи информ. 2010. Т. 46, № 2. С. 47-65.

2. Зяблов В. В., Рыбин П. С., Фролов А. А. Алгоритм декодирования с вводом стираний для МПП-кодов, построенных над полем GF(q) // Информационно-Управляющие Системы. 2011. Т. 50, № 1. С. 62-68.

3. Фролов А. А., Зяблов В. В. Границы минимального кодового расстояния для недвоичных кодов на двудольных графах // Пробл. передачи информ. 2011. Т. 47, № 4. С. 27 42.

4. Зяблов В. В., Фролов А. А. Сигналыю-кодовая конструкция для системы множественного доспупа, использующей векторный канал с аддитивным белым гауссовским шумом // Информационные процессы. 2012. Т. 12, № 1. С. 98-104.

5. Frolov A., Zyablov V. The Application of Q-aiy LDPC-codes for Fiber Optic Lines // Proc. of XII International Symposium on Problems of Redundancy in Information and Control Systems, Saint-Petersburg, Russia. 2009. — May. P. 121-125.

6. Зяблов В. В., Фролов А. А. Сравнение корректирующей способности МПП-кодов с кодами-компонентами разной избыточности // Информационные технологии и системы (ИТиС'09), пос. д/о Бекасово, Россия.

2009.-Дек. С. 160-163.

7. Зяблов В. В., Фролов А. А. Исследование корректирующих свойств МПП-кодов с кодом-компонентом Рида-Соломона // Информационные технологии и системы (ИТиС'10), г. Геленджик, Россия. 2010. — Сент. С. 74-78.

8. Осипов Д. С., Фролов А. А., Зяблов В. В. Сигнально-кодовая конструкция на базе q-ичных кодов для защиты от сосредоточенных помех // Информационные технологии и системы (ИТиС'11), г. Геленджик, Россия. 2011.-Окт. С. 167-173.

9. Frolov A., Zyablov V. Insertion of Erasures as a Method of Q-ry LDPC Codes Decoding // Proc. of XII International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2010), Akademgorodok, Novosibirsk, Russia.

2010.-Sept. P. 138-143.

10. Frolov A., Zyablov V. Upper and Lower Bounds on the Minimum Distance of Expander Codes // Proc. of IEEE International Symposium on Information Theory (ISIT 2011), Saint-Petersburg, Russia. 2011. - Jul./Aug. P. 1302-1306.

Подписано в печать:

11.04.2012

Заказ № 7122 Тираж -100 экз. Печать трафаретная. Объем: 1 усл.п.л. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Федеральное государственное бюджетное учреждение науки Институт проблем передачи информации им. А. А. Харкевича

Российской академии наук

61 12-1/813

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

Фролов Алексей Андреевич

Корректирующие свойства недвоичных кодов с малой плотностью проверок

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

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель д. т. н.

Зяблов Виктор Васильевич

Москва - 2012

Содержание

Введение ......................................................................4

Обзор литературы..........................................................9

Глава 1. Потенциальные корректирующие свойства недвоичных МПП-кодов.............................11

1.1. Введение...............................11

1.2. Структура МПП-кодов над полем .............11

1.3. Нижняя оценка минимального кодового расстояния для МПП-кодов над полем .......................13

1.4. Верхняя оценка минимального кодового расстояния для МПП-кодов над полем .......................22

1.5. Анализ результатов.........................26

1.6. Выводы к главе...........................29

Глава 2. Реализуемые корректирующие свойства недвоичных МПП-кодов................................33

2.1. Введение...............................33

2.2. Асимптотическая оценка доли ошибок, исправимых МПП-кода-

ми над полем .........................33

2.3. Результаты имитационного моделирования............54

2.4. Выводы к главе...........................88

Глава 3. Применение недвоичных МПП-кодов в сигнально-кодо-

вой конструкции для системы множественного доступа ... 89

3.1. Введение...............................89

3.2. Описание сигнально-кодовой конструкции для векторного дизъ-

юнктивного канала.........................89

3.3. Асимптотическая оценка относительной суммарной скорости передачи...............................93

3.4. Модифицированный вариант сигнально-кодовой конструкции

для векторного канала с АБГШ..................100

3.5. Результаты имитационного моделирования............103

3.6. Выводы к главе...........................106

Заключение..................................107

Литература..................................108

Введение

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

Для исправления ошибок используют помехоустойчивые коды. Важнейшим обстоятельством при выборе той или иной кодовой конструкции на практике является наличие быстрых алгоритмов кодирования и декодирования. Двоичные коды с малой плотностью проверок (МПП-коды) удовлетворяют этому требованию. Однако не менее важно, чтобы алгоритмы декодирования были способны исправить большое число ошибок. Таким образом, главным вопросом является вопрос о том, насколько ухудшаются корректирующие свойства кодов при использовании простых алгоритмов декодирования. Исследованию двоичных МПП-кодов посвящено множество работ, среди которых следует особо отметить работы таких русских и зарубежных ученых, как Р. Дж. Галлагер, М. С. Пинскер, В. В. Зяблов, К. Ш. Зигангиров, А. М. Барг, Р. Таннер, Д. Спилман, Д. Маккей, Т. Ричардсон, Р. Урбанке, Д. Бурштейн, С. Л. Литсын, Ж. Земор. Доказано существование двоичных МПП-кодов, способных исправить линейно растущее с длиной кода число ошибок при сложности декодирования 0(п log2 п), где п - длина кода. Как результат, в настоящее время эти коды используются в стандартах подвижной беспроводной связи (например, LTE), цифровой телефонии; рекомендованы для использования в стандартах оптической связи, спутниковой связи, WiMAX, 802.lin.

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

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

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

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

Для достижения поставленных целей необходимо решить следующие задачи:

о Исследовать потенциальные корректирующие свойства МПП-кодов над полем GF(q).

о Исследовать реализуемые корректирующие свойства МПП-кодов над

полем GF(q) теоретически и методом имитационного моделирования.

о Разработать СКК на основе недвоичных МПП-кодов для системы множественного доступа. Провести исследование полученной системы в канале с аддитивным белым гауссовским шумом методом имитационного моделирования.

Научная новизна. В настоящей работе впервые:

о Теоретически исследованы потенциальные и реализуемые корректирующие свойства МПП-кодов над полем GF(q).

о Предложен алгоритм декодирования МПП-кодов над полем GF(q) с вводом стираний.

о МПП-коды над полем GF(q) использованы в СКК для системы множественного доступа.

Теоретическая и практическая ценность. Получены верхняя и нижняя границы минимального кодового расстояния для МПП-кодов над полем GF{q). Улучшена асимптотическая оценка доли ошибок, гарантированно исправимых МПП-кодами над полем GF(q) с помощью алгоритма, имеющего сложность 0(nlog2n). Получена нижняя оценка относительной суммарной скорости передачи для системы множественного доступа, использующей бесшумный векторный дизъюнктивный канал. Эта оценка асимптотически совпадает с верхней оценкой.

Результаты, полученные в процессе подготовки диссертационной работы, использованы в программе фундаментальных исследований Президиума РАН «Проблемы создания национальной научной распределенной информационно-вычислительной среды на основе GRID технологий и современных телекоммуникационных сетей» по направлению «Распределенная обра-

ботка данных. Информационная безопасность сетевых технологий» (№ Госрегистрации 01200965142), программе фундаментальных научных исследований ОНИТ РАН «Архитектура, системные решения, программное обеспечение стандартизация и информационная безопасность информационно-вычислительных комплексов новых поколений» по направлению № 3.1 «Обеспечение информационной безопасности распределенных информационно-вычислительных систем» (Регистрация РАН № 10002-251/ШТВС-04/103-96/260503-208) и разработках ЗАО «Телум», что подтверждено соответствующими актами.

На защиту выносятся следующие положения:

1. Верхняя и нижняя границы минимального кодового расстояния для МПП-кодов над полем GF(q).

2. Асимптотическая оценка доли ошибок, гарантированно исправимых МПП-кодами над полем GF(q) с помощью алгоритма декодирования, имеющего сложность 0(nlog2n).

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

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

Апробация работы. Основные результаты диссертации докладывались на следующих конференциях: IEEE International Symposium on Information Theory (2011); XII International Symposium on Problems of

Redundancy in Information and Control Systems (2009); XII International Workshop on Algebraic and Combinatorial Coding Theory (2010); конференциях молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы» (2009-2011). Кроме того, основные результаты докладывались на семинарах по теории кодирования в ИППИ РАН.

Публикации. Материалы диссертации опубликованы в 10 печатных работах, из них 4 статьи [11, 14, 20, 21] в рецензируемых журналах и 6 статей [12, 13, 17, 47-49] в сборниках трудов конференций.

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

Структура и объем диссертации Диссертация состоит из введения, обзора литературы, трех глав, заключения и библиографии. Общий объем диссертации 117 страниц, включая 64 рисунка и 8 таблиц. Библиография включает 83 наименования на 10 страницах.

Обзор литературы

МПП-коды были предложены Р. Дж. Галлагером в [7] в 1960 году. В этой работе были получены нижняя оценка минимального кодового расстояния и оценка вероятности ошибки при декодировании по минимуму расстояния. Кроме того были предложены алгоритмы декодирования, подходящие для практического применения (алгоритм распространения доверия1 и мажоритарный алгоритм). В 1974 г. В. В. Зяблов и М. С. Пинскер доказали существование МПП-кодов, способных исправить линейную долю стираний при декодировании с помощью алгоритма, имеющего сложность 0(nlog2n). В 1975 г. ими был получен аналогичный результат для ошибок. В 1981 г. в работе [77] Р. Таннер предложил метод построения длинных кодов из коротких кодов компонентов. Конструкция МПП-кодов Галлагера является частным случаем конструкции Таннера и получается из нее, если использовать код с двоичной проверкой на четность в качестве компонентного кода. Таким образом, коды построенные Таннером можно назвать обобщенными МПП-кодами. После этого ввиду слабого развития вычислительной техники МПП-коды были на долгое время забыты.

Активное исследование МПП-кодов началось в середине 90-х годов в связи с появлением работ М. Сипсера, Д. Спилмана [74, 76] и Д. Маккея [61]. Можно выделить несколько основных направлений исследований этих кодов:

о исследование мажоритарного алгоритма декодирования [10, 15];

о исследование алгоритма распространения доверия [27, 32, 35, 37, 38, 54, 62, 69];

о исследование исправления стираний [9, 41];

1 в англоязычной литературе используется термин "belief propagation"

о исследование вероятности ошибочного декодирования [23, 29-31, 72];

о исследование распределения весов [33, 42, 56, 66];

о исследование нерегулярных МПП-кодов [57, 60, 61, 71];

о исследование сложности кодирования МПП-кодов [58, 70];

о построение явных конструкций МПП-кодов [16, 59];

о построение проверочных матриц МПП-кодов со специальными свойствами [22, 36, 44-46, 50].

Недвоичные МПП-коды впервые рассмотрены в работе М. Дэви и Д. Маккея [39]. В этой работе предложен алгоритм декодирования, являющийся обобщением алгоритма распространения доверия для двоичного случая, и проведено исследование методом имитационного моделирования. Число работ, посвященных исследованию недвоичных МПП-кодов, сравнительно невелико. В существующих работах по этой теме [26, 40, 43, 51, 53, 64, 65, 67, 68, 73, 78-81] приводятся упрощенные варианты алгоритма декодирования и результаты исследований этих модифицированных алгоритмов методом имитационного моделирования.

Глава 1

Потенциальные корректирующие свойства недвоичных МПП-кодов

1.1. Введение

В первой главе исследуются потенциальные корректирующие свойства МПП-кодов над полем СР^), т.е. минимальное кодовое расстояние этих кодов. Построены нижняя и верхняя оценки кодового расстояния для этих кодов. Показано, как меняются корректирующие свойства этих кодов при изменении их параметров, что важно для практического применения этих кодов.

1.2. Структура МПП-кодов над полем С-Р(д)

Для построения проверочной матрицы МПП-кода над полем б?-Р(<7) рассмотрим блочную диагональную матрицу

на главной диагонали которой находятся Ъ проверочных матриц Н0 {щ, /с0 = ЕоЩ, г10)-кода над полем СР(д) (далее будем использовать термин код-компонент), т = щ — ко.

Пусть (р (Щ) обозначает матрицу, полученную из матрицы Нь произвольной перестановкой столбцов и умножением их на произвольные ненулевые

/

Н0 0 • • • О

О Н0 ... О

V

о о

элементы поля GF(q). Тогда матрица

Н =

/ ^(Нб) х

^2(Н ь)

\

<Ре(Нь)

/ ibmxbno

размера £Ьт х Ъщ, составленная из £ таких матриц, как слоев, является разреженной проверочной матрицей МПП-кода над полем GF(q).

Определим ансамбль ¿>(Ь) МПП-кодов над полем GF{q) следующим образом:

Определение 1.1. Элементы ансамбля <#(Ь) получаются путем независимого выбора перестановок 7= 1, 2,..., £ и ненулевых констант qj, г = 1, 2,...,£\ j = 1,2,... ,п, на которые умножаются столбцы получившихся в результате перестановок проверочных матриц слоев.

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

Замечание 1.2. Из определения ансамбля ¿>(Ь) ясно, что длина кода п = Ъщ.

Нижняя оценка скорости кода С G ^(Ь) получена в [77].

£Ъ (п0 - к0)

R > 1

Ъпг

1 ~ £{l — Rq) ,

(1.1)

равенство достигается в случае полного ранга матрицы Н.

Графически код можно представить в виде двудольного графа, в котором символьные вершины соответствуют столбцам проверочной матрицы, а кодовые вершины соответствуют строкам. Этот метод был предложен Танне-ром в [77]. Пример двудольного графа Таннера приведен на рис. 1.1:

Слой 1 Слой 2 Слой /.

Рис. 1.1. Граф Таннера

1.3. Нижняя оценка минимального кодового расстояния для МПП-кодов над полем С^Р(д)

В этом разделе будет получена нижняя граница минимального кодового расстояния для ансамбля <§(Ъ). Результаты этого раздела являются модифи-кацированными версиями результатов работ [7, 25, 28, 55, 75]. Так как отличия (хоть и небольшие) все-таки присутствуют, приведем полностью все необходимые доказательства.

Отметим, что используемый метод требует знания полных распределений весов кодовых слов компонентных кодов. Одновременно с этим, статьи [24, 25] предлагают другой способ оценки минимального кодового расстояния, для которого нужно лишь кодовое расстояние компонентных кодов. Результаты, получаемые при таком подходе, слабее, так как используется меньше информации о компонентных кодах, но в некоторых ситуациях это может быть полезно.

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

Пусть <§ - это ансамбль кодов, имеющих длину п. Через А [\У ] обозначим

среднее по кодам число кодовых слов веса У/, т.е.

где А{ (Ш) - это число слов веса ]¥ в коде Сг- £ $.

Теорема 1.1. (Галлагер, [7]) Если выполняется условие

й

IV=1

то в ансамбле <§ существует код С, такой что & (С) > (1.

й __<* Щ

Доказательство. Заметим, что ]Г) А(]¥) < 1 => ]Г] ¿С -^г (У^) <

г=1

а это значит, что суммарное число кодовых слов веса меньше либо равного

в ансамбле <§ меньше числа кодов, следовательно, найдется код С €

ни одного из этих слов не содержащий ¿(С) > (1. к

<1 _

Замечание 1.3. Отметим, что если ^ А (IV) — ,В < 1, то в ансамбле £ найдется по крайней мере (1 — ,8) кодов Сг, таких что с? {Сг) > й. Замечание 1.4. Отметим, что

= = {*> -Г)' (1-2)

где = {у^ 6 (СГ(д))п : - У/}, - это число кодов из

ансамбля содержащих кодовое слово V. Теперь перейдем к ансамблю £(Ь).

Лемма 1.1. Среднее по кодам число кодовых слов веса \¥ в ансамбле

т

[Аг т)£

А{\У) =

те;

где А\ (И^) - число кодовых слов веса \У в первом слое. Доказательство.

У1)

✓Т" /! Кодовое*? / ' 1 / \ \ \ \ \ ч ч \ \ \ Кодовое?

/ / / / ✓ 1 Кодовре? ч \ ч \

/ г * 1 г \ *

<А(н >) ...

\ / <=> Ч \ 'V

Кодовое^ \ / Кодовое?

^ * /

н.

Рис. 1.2. Подсчет N

Рассмотрим фиксированный вектор у^ длины п, |у^[ = IV. В соответствии с уравнением (1.2) нужно вычислить . Рассмотрим отдельно ансамбли первых (¿а), вторых (1/2), £-тых (1^) слоев. Если известны

1=1

это следует из того, что перестановки и ненулевые множители для слоев выбираются произвольно и независимо. По этой же причине Ь\ = 1/2 = ... = Ье, следовательно,

Для того чтобы вычислить N (1/1, у^) зафиксируем один конкретный слой, а перестановки и умножения на константы будем производить с элементами вектора у^, а не со столбцами проверочной матрицы. Так как все слои являются эквивалентными, пусть это будет слой с тождественным отображением р = гй. Все сказанное проиллюстрировано на рис. 1.2.

В соответствии со свойствами отображений (р.[ среди векторов {(р(~1 (у^)}^ есть все возможные кодовые векторы веса И7", причем каждый из них повторяется К раз, где

К = Ш\{п- \¥)\{д-1)п~ш. 15

Таки�