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

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

Милославская Вера Дмитриевна

Методы построения и декодирования полярных

кодов

05.13.01.....Системный анализ, .управление и обработка информации

(информатика)

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

п СНЗ 2015

005557903

Санкт-Петербург - 20М

005557903

Работа выполнена в федеральном государстве!том автономном образователыюлt учреждении высшего образования «Санкт-Петербургский государственный политехнический университет».

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

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

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

кандидат технических наук, доцент,

Трифонов Пётр Владимирович Кудряшов Борис Давидович, доктор технических наук профессор,

профессор кафедры информационных систем,

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

Беззатеев Сергей Валентинович, доктор технических наук, доцент,

зав. кафедрой технологий защиты информации,

ФГАОУ В ПО * Санкт-Петербургский государственный университет аэрокосмического приборостроения» ФГБУН «Институт ■проблем, передачи информации им. A.A. Каркевина» РАН

Защита состоится 19.03.2015 в 16:00 часов на заседании диссертационного совета Д 212.229.18 при ФГАОУ ВО «Санкт-Петербургский государственный политеюшческий университет», расположенном по адресу: 195251, г. Санкт-Петербург, ул. Политехническая, д. 29

С диссертацией можно ознакомиться в библиотеке ФГАОУ ВО «Санкт-Петербургский государственный политехнический университет» и на сайте www.spbstu.ru.

Автореферат разослан

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

диссертационного совета, 1г~уС кандидат технических наук, доцент --Васильев Алексей Евгеньевич,

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

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

В 2008 году Е. Арпканом были предложены полярные коды п было показано, что они достигают пропускной способности широкого класса каналов передачи информации. Последнее означает, что для любой сколь угодно мацой величины р > 0 существует такое целое число т, что полярный код длины п = 2"' со скоростью R, меньшей пропускной способности капала, обеспечивает вероятность ошибки меньше р.

Степень разработанности темы исследования. Конструкция полярных кодов была обобщена С.Б. Корадой, Е. Сасоглу и Р.Л. Урбанке. Кроме того, было показано, что полярные коды относятся к классу обобщенных каскадных кодов, предложенных Э.Л. Блохом и В.В. Зябловым. Полярные коды могут быть также представлены как многоуровневые коды. Последние были предложены X. Пмап и исследованы У. Вакеманном, Р.Ф. Фишером и Д.Б. Ху-бером. Конструкции кодов, достигающих пропускной способности канала, рассматривались ранее в работах Дж.Д. Форни, Э.Л. Блоха, В.В. Зяблова, A.M. Барга, Ж. Земора, P.M. Рота, В. Скачека и некоторых других исследователей. Отличительной особенностью полярных кодов является простота процедур их построения, кодирования и декодирования, что делает их привлекательными для практического использования.

Однако, эксперименты показывают, что вероятность ошибки декодирования полярных кодов с практически значимыми параметрами, то есть значениями п порядка нескольких тысяч, оказывается значительно больше, чем у кодов с малой плотностью проверок на четность (МППЧ) и турбо-кодов с аналогичными параметрами. Это обусловлено малым минимальным расстоянием полярных кодов и субоптпмалыюстыо алгоритма последовательного исключения, используемого для их декодирования. II. Талом и А. Вардп был предложен алгоритм списочного декодирования, построенный па базе алгоритма последовательного исключения и обеспечивающий декодирование полярных кодов почти по максимуму правдоподобия. Также ими был предложена конструкция полярных кодов с контрольной суммой, демонстрирующая существенно меньшую вероятность ошибки декодирования по сравнению с классическими полярными кодами. К. Пию и К. Чень предложили обобщение стекового алгоритма К.Ш. Зигангиро-

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

Одним из наиболее широко используемых классов корректирующих кодов являются коды Рида-Соломона. При этом остается актуальной задача построения эффективных алгоритмов их мягкого декодирования. Следует отметить, что сложность существующих алгоритмов мягкого декодирования кодов Рпда-Солодюна, таких как метод Ксттера-Варди, является достаточно высокой. Это приводит к тому, что системы передачи и хранения информации, использующие коды Рида-Соломона, демонстрируют энергетический проигрыш порядка 3 дБ по сравнению с теоретическим пределом. Наиболее трудоемким шагом алгоритма Кёттера-Вардп является построение полинома от двух переменных, имеющего корни различной кратности. Вопрос построения быстрых алгоритмов, реализующих этот шаг, исследовался Р. Кёттером, P.P. Нильсоном, К. Ли и М.Е. О'Салливаном. Следует отметить, что метод Кёттера-Вардп не обеспечивает декодирование кодов Рида-Соломона по максимуму правдоподобия, и открытой остается задача построения алгоритмов декодирования с большей корректирующей способностью.

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

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

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

3. Разработать метод укорочения полярных кодов.

4. Разработать быстрый алгоритм мягкого декодирования кодов Рида-Соломона.

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

Научная новизна:

1. Предложена конструкция полярных подкодов Боуза-Чоудхури-Хоквингема с минимальным расстоянием большим, чем у полярных кодов с ядром Арикана с аналогичными параметрами.

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

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

4. Разработан новый алгоритм декодирования кодов Рида-Соломона, основанный на методе последовательного декодирования полярных кодов.

5. Предложен новый алгоритм, реализующий этап двумерноп интерполяции в методе Кёттера-Варди декодирования кодов Рида-Соломона.

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

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

Предложен метод построения подкодов расширенных кодов Боуза-Чоудх-ури-Хоквпнгема (полярных подкодов БЧХ), обеспечивающих меньшую вероятность ошибки при декодировании с помощью стекового и списочного алгоритмов последовательного исключения, чем известные классы полярных кодов, в частности, полярные коды с ядром Арнкана. Предложенный метод построения укороченных полярных кодов позволяет получить коды произвольной длины, демонстрирующие высокую корректирующую способность при использовании метода последовательного исключения. Полярные коды с произвольным двоичным ядром, построенные для двоичного стирающего канала с помощью предложенного алгоритма, обеспечивают малую вероятность ошибки декодирования и в Рауссовском канале. I В отличие от классического метода последовательного декодирования и ал-

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

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

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

Положения, выносимые на защиту:

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

2. Метод построения укороченных полярных кодов.

3. Метод последовательного декодирования двоичных полярных кодов и основанный на нем алгоритм декодирования коротких кодов Рида-Соломона.

4. Быстрый алгоритм, реализующий этап двумерной интерполяции в методе Ксттера-Варди декодирования кодов Рида-Соломона.

5. Метод кодирования информации укороченными полярными нодкодамп (в частности, полярными кодами) для отказоустойчивых систем хранения данных.

Степень достоверности и апробация результатов. Основные результаты диссертации докладывались на следующих конференциях: IEEE R8 International Conference on Computational Technologies in Electrical and Electronics Engineering 2010, 8-th IEEE International Symposium on Wireless Communication Systems 2011, International Workshop on Algebraic and Combinatorial Coding Theory 2012, International Symposium on Information Theory and Applications 2014, IEEE Information Theory Workshop 2012, 2013 j и 2014. Кроме того, результаты были представлены на семинарах в институте проблем передачи информации им. A.A. Харкевича Российской академии наук j (руководитель Л.А. Бассалыго) и Санкт-Петербургском государственном уни- i верситете аэрокосмического приборостроения (руководитель Е.А. Крук).

Предлагаемые алгоритмы были реализованы на языке программирования С-г-К Выполнено сопоставление результатов статистического моделирования с известными опубликованными данными.

Публикации. Материалы диссертации опубликованы в 9 печатных работах |2, 4 111, пз них 2 статьи в рецензируемых журналах |2, 8|, включенных в список ВАК, и 7 статей в сборниках трудов конференций.

Получено свидетельство о государственной регистрации программы для ЭВМ |1|. Подана заявка на патент |3|.

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

G

Структура и объем диссертации. Диссертация состоит из введения, пяти разделов, заключения и библиографии. Общин объем диссертации 200 страниц, из них 187 страниц текста, включая 67 рисунков. Библиография включает 83 наименования на 10 страницах.

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

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

В первой главе рассматриваются полярные коды и коды Рпда-Соломо-

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

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

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

Кроме того, в главе приведено определение кодов Рида-Соломона, а также описание метода Кёттера-Вардн, позволяющего реализовать их мягкое декодирование. Особое внимание уделено интерполяционному шагу метода Кёт-тера-Вардп, являющемуся наиболее трудоемким. Следует отметить, что метод Кёттера-Вардн не обеспечивает декодирование по максимуму правдоподобия, поэтому актуальной является задача построения для кодов Рпда-Соломона алгоритмов декодирования с большей корректирующей способностью.

Во второй главе показано, как может быть выполнено декодирование произвольного линейного блокового кода длины 2"' методом последовательного

на. Рассматривается структура как полярных кодов с ядром А

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

Результаты второй главы опубликованы в работах |6, 11|.

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

Для обеспечения возможности декодирования произвольного линейного кода длины п = 2'" методом последовательного исключения или его аналогами введем понятие динамически замороженных символов, равных линейным комбинациям информационных символов. Далее изложен предлагаемый подход к декодированию таких кодов.

В основе полярного кода лежит матрица поляризующего преобразования Сп = АЛ '"', где операция ®т обозначает т-кратное Кронекеровское произведение матрицы с собой и А перестановочная матрица, соответствующая обратной перестановке битов индексов входной последовательности. Используется такая проверочная матрица Н кода С, что матрица V = ИС1п удовлетворяет условиям: У^ = —1 н для любого £ е {0,..., 2"' — 1} существует не более одного з : ¿у = t, где г^ = шах {£ е {0,..., п — 1} | V},, ^ 0} , 0 < < тс — к. Если рассматривать г/Ц~1Ут = 0 как систему изп — к линейных уравнений относительно элементов последовательности € то все решения данной системы можно представить как последовательности, состоящие из к произвольных элементов щ € при £ е Л/", где N = {0,..., п - 1} \ Т при Т = {гу|0 < з < п - к}, н п — к зависящих от них элементов

Переход от замороженных символов, равных нулю, к динамически заморожен-

(1)

ным символам не влияет на вероятности ошибки Р-, декодирования символов г/,-при использовании алгоритма последовательного исключения. Таким образом, вероятность ошибки декодирования кода С методом последовательного исключения равна Р{'\Т) = 1 - Д(1 - Р).

В общем случае, множество незамороженных символов, построенное для произвольного кода С с помощью данного метода, включает много символов », с большими Р-п в то время как многие символы с малыми Г', оказываются замороженными. Вероятность ошибки декодирования при использовании метода последовательного исключения оказывается значительно выше, чем I! случае ' других современных методов декодирования. Показано, что у кодов Рида-Мал-лера и расширенных кодов БЧХ, в общем случае, замороженными оказываются символы, которым соответствует большая вероятность ошибки, однако, некоторые из таких символов остаются незамороженными. Это ведет к необходимости использования списочного алгоритма последовательного исключения с чрезвычайно большим размером списка для обеспечения вероятности ошибки декодирования, сравнимой с таковой других алгоритмов декодирования.

Для получения (2"',к, > с1) кода, декодирование которого может быть эффективно выполнено с помощью списочного/стекового алгоритма последовательного исключения и его аналогов, предлагается использовать ограничения для динамически замороженных символов высокоскоростного (2"\k.\d) расширенного кода БЧХ с достаточно большим минимальным расстоянием (I, и до волнительно заморозить к' — к символов и,■ с наибольшими вероятностями Р,. Эти вероятности могут быть вычислены с помощью метода эволюции плотностей. Предлагаемый класс кодов назван полярными подкодамп БЧХ. На Рис. 1 представлен график зависимости вероятности ошибки декодирования от отно-' шения сигнал/шум для классического полярного кода с ядром Арпкана п для полярного подкода.

В разделе 2.2 приведено описание предлагаемого алгоритма построения [ укороченных полярных кодов. Данный алгоритм позволяет пост роить коды произвольной длины, обеспечивающие малую вероятность ошибки при декодировании методом последовательного исключения. При декодировании используется представление (п,к) укороченного полярного кода в виде (2"',А; + в) полярного кода с динамически замороженными символами, где й = 2"' — п.

Укорочение произвольного (2"', А', О) линейного блокового кода С длины 2"' на в символов, задаваемых двоичным вектором , состоит I! выборе всех кодовых слов с £ С таких, что с, = 0 для i 6 8прр(5,„) и исключении из этих кодовых слов символов с,- для г Е 8ирр(5,„). Полученные таким образом вектора составляют (п = 2'" — в, к > К — в, с? > И) линейный код.

Укороченный полярный (п,к) код задается множеством замороженных символов Т, = л — к, и шаблоном 5,„ веса д = 2"' — п, где 2"'~1 <

п < 2"'. С помощью эволюции плотностей для этого кода может быть вычислена вероятность ошибки декодирования методом последовательного исклю-

Рис. 1. Вероятность ошибки декодирования (1024,512) полярных кодов

нения P^J7, S,„). В работе рассматривается случай адцнтпвного Гауссовского канала, поэтому для упрощения вычислений Р(Т, Sm) используется Гауссов-ская аппроксимация. Пусть 1Z и V множества всех шаблонов Sm веса s, и всех множеств J- С {0,..., 2'" — 1} мощности п — к, соответственно. Поскольку множество замороженных символов первоначального неукороченного кода может перестать быть оптимальным для укороченного кода, предлагается выполнять совместную оптимизацию множества Т и вектора Sm: (J-*,S*J = arg min P(T, S„,). s,„eK

Высокорегулярная структура полярных кодов позволяет снизить сложность поиска решения данной оптимизационной задачи. Вводится понятие эквивалентности шаблонов,_для эквивалентных шаблонов 5,„. и 5,„, в частности, выполняется P(Sm) == P(Sm), где P(S„,) = min Р{Т, Sm). Предложен метод выявления эквивалентных шаблонов, позволяющий построить множество Gu С TZ, мощность которого намного меньше \1Z\, удовлетворяющее следующему условию VS,„ G 1Z 3Sm е S» : P(SW) = P(S,„). Шаблон S*u может быть выбран среди Sm б Gib Кроме того, для осуществления эффективного поиска по множеству д„ предлагается рекурсивно делить его на подмножества G¡■ Каждому подмножеству G¡ сопоставляется оценка снизу для вероятностей P(Sm), Sm € G¡-Для осуществления очередного шага рекурсии выбирается подмножество с наименьшей такой оценкой.

На Рис. 2 представлен график зависимости вероятности ошибки декодирования от отношения сигнал/шум для укороченных полярных кодов, построенных с помощью предлагаемого метода. Данные коды были построены так, что они являются иодкодами заданных расширенных кодов БЧХ. Декодирование укороченных кодов выполнялось с помощью алгоритма последовательного де-

Рис. 2. Сравнение корректирующем способности укороченных полярных колон и кодов

мппч

кодирования, описанного в разделе 3.2 , с Ь = 128. Для сравнения показана корректирующая способность кодов МППЧ из стандарта \ViMAX, для декодирования которых использовался алгоритм распространения доверия.

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

Задача построения (п = 1"',к) двоичного полярного кода с I х I ядром М сводится к задаче выбора (п — к) замороженных символов ип 0 < г < ?г, которым соответствуют наибольшие вероятности ошибки Р; декодирования методом последовательного исключения. Вероятность Р; может быть вычислена по заданному распределению логарифмических отношений правдоподобия для символа и,. Однако задача нахождения данного распределения является крайне трудоемкой. В связи с этим, в работе рассматривается более простая задача построения полярного кода для двоичного стирающего канала. Показано, что задача построения полярных кодов для случая двоичного стирающего канала с вероятностью стирания р сводится к задаче оценки вероятностей отказа от декодирования £}(р,(3) для 0-ых информационных символов (1,р) линейных блоковых кодов, порождаемых последними /4 строками ядра М, ц = / — /3, 1 < ц < I. Эта вероятность может быть представлена как С2(р,(3) = Др''(1 — р)1~'\

где Д. число неисправимых конфигураций стираний веса е, 0 < е < /.

Предложены два метода оценки числа неисправимых конфигураций стираний В,.. Первый метод позволяет найти точное значение В,, однако, в случае / > 32 сложность данного метода оказывается чрезмерно высокой для практического применения. Этот метод предполагает построение решетки, задаю! и

щей смежный класс кода с проверочной матрицей Г, состоящей из /« последних строк ядра М. Данный смежный класс состоит из кодовых слов г',-1, удовлетворяющих условию Г (г',-1) = (1 0 ... 0) , где а^-р подвектор вектора а'-, состоящий из элементов 6 Т) Г) (у,..., /(}. Построенная решетка преобразуется в двоичное дерево решений (ДДР) В 1)1), соответствующее функции /(Е), являющейся характеристической функцией для множества У = \е\Е; = 1 - Г (4_1)Г = (1 0 • • • 0)Г| . В свою очередь, ДДР ВШ преобразуется в ДДР ВОБ, соответствующее функции /(Е) = \/б"еу(АгЛ' =о путем выполнения рекурсивных операции для поддеревьев. В, вычисляется как количество путей в ДДР £?£Ш из корня в терминальную вершину "0:\

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

Теорема 1. Прие < |_(Зг/+1)/2] число неисправимых конфигураций стираний В,. = ('!'•) Ль '¿дс Л наименьший вес кодового слова с',-1 = и(','-1Г при

щ = 0 и и1^"1 £ {О, I}'1 \ Д: число кодовглх слов с', 1 веса г. При е > [(3(/ + 1)/2] -число неисправимых конфигураций стираний ограничено сверху В,. <

тт(Е^ С:!) А-. О)-

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

В третьей главе рассматриваются предлагаемые алгоритмы декодирования полярных кодов. Результаты этой главы опубликованы в работах |8 111.

В разделе 3.2 представлен алгоритм последовательного декодирования полярных кодов с ядром Арикана и полярных подкодов с ядром Арикана, в основе которого лежит стековый алгоритм последовательного исключения. Стек содержит несколько входных последовательностей и'{) различной длины. На каждой итерации стекового алгоритма последовательность и,) с наибольшим значением метрики удлиняется на один элемент. Общепринятой метрикой для пути и'() является вероятность Р(ы,')|г/("-1). Если длина пути с наибольшей метрикой равна п, то данный путь возвращается в качестве результата декодирования. Предложена новая метрика пути, то есть новый метод предсказания того, какое начало пути и'п может соответствовать решению задачи декодирования. Задача декодирования состоит в поиске пути «о ^ = 0, которому соответствует наибольшее значение вероятности

р* — Р(иЦ 1\у{\ Если решение задачи декодирования соответствует и[„ то р* = max P(t/[{_1|y("_1). Вычисление вероятности Т(и{ь у,""1) на г-ой фазе алгоритма последовательного исключения является крайне трудоемкой задачей. Рассмотрим пути i'[j]("_1 такие, что t;[j](', = и «[j]""/ € {0,1}" ' \ О < j < 2"~'_1. Предположим, что и'0 соответствует наиболее вероятному кодовому слову. Пусть J случайная величина, равная j, если наиболее вероятное кодовое слово полярного кода соответствует пути Заметим, что J = j предполагает v[j]i, = 0, Ii € Т. Мы предлагаем оценить Т(и'(), у,',1-1)

как т(и>»уг1) « ^и^гЧг/Г1)] = Е^Г^ЖЛГ'кГ1)^ = Л >

= гДе а = arg max Р^^ГЧг/о'"1)- Вероятность

Щ"'п-и!Г')

P{J = aj, усредненная по всем принятым последовательностям, ограничена снизу вероятностью П(г) = (1 — Pj), где Pj вероятность ошибки деко-

jer.j>i

дпрованпя символа Uj при условии того, что известны правильные значения предыдущих символов и у, j' < j. Таким образом, получаем следующую оценку для Т^уЦ-1):

ГК,2/Г1) = ДК)уГ1)П(г). (2)

Вычисление значения вероятности R(u{): уЦ'1) осуществляется рекурсивно согласно выражениям

Щг^,у1Г1) = max - (3)

■«ai 11 е{<»,1} \ / \ ' ' /

Ä(«Sf+,.»ff-1) = R («2™. © Ä vT~l) К У^) (4)

с начальным условием R(b,yj) = P(b\yj), b £ {0,1}. Величина Cl(i) может рассматриваться как оценка снизу для вероятности Р {J = а}, усредненной по множеству принятых последовательностей.

На Рис. 1 представлен график зависимости вероятности ошибки декодирования от отношения сигнал/шум для предлагаемого алгоритма, списочного алгоритма Тала-Варди и алгоритма направленного поиска, описанного в разделе 3.1 . Корректирующая способность алгоритма направленного поиска совпадает с таковой списочного/стекового алгоритма последовательного исключения. Результаты приведены как для (1024,512,16) классического полярного кода с ядром Арпкана н (1024, 512,28) полярного и од кода с ядром Арикана, так и для (1032,516) кода МППЧ.

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

Таблица 1. Средняя сложность декодировании, х1()3 вещественных операции

Предлагаемый подход МППЧ, air. раепр. дов.

Сложения Сравнения Слож. iogfanli(i)

L = 32 L = 256 L = 2048 L = 32 L = 256 L = 2048 < 200 пт. < 200 пт.

0 141 833 5231 227 1332 8374 2С17 1307

0.5 133 752 42G5 218 1224 6968 2333 1112

1 73 28С 1232 122 477 2065 1469 722

1.5 32 88 267 54 151 461 394 185

2 18 27 42 31 48 74 140 62

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

В разделе 3.3 описано обобщение предлагаемого метода последовательного декодирования на случай полярных кодов с произвольным двоичным ядром. Выполнено обобщение процедуры вычисления метрики пути, задаваемой выражением (2). Вероятности R(u'0, г/о"1) вычисляются также рекурсивно, однако, на каждом шаге рекурсии выполняется поиск двух наиболее вероятных кодовых слов в коде, порожденном последними строками I х I ядра поляризации. Алгоритм предполагает использование для этих кодов декодеров, работающих почти по максимуму правдоподобия. Численные результаты показывают, что предлагаемый подход позволяет выполнять декодирование полярных кодов с ядром БЧХ почти по максимуму правдоподобия. Сложность последовательного алгоритма декодирования можно оценить в 0(Ln log; п) базовых операции, где базовая операция соответствует поиску наиболее вероятного кодового слова в коде, порожденном последними строками ядра поляризации.

В разделе 3.5 рассматривается обобщение предложенного в разделе 3.2 ач-горитма последовательного декодирования на случай расширенных кодов Рида-Соломона над полем F2»>. При декодировании используется представление расширенных кодов Рида-Соломона, описанное в разделе 2.1 .

На каждой итерации алгоритма путь с наибольшей метрикой (2) удлиняется на один элемент. Для информационного символа и,; рассматривается 2"1 значений, а для замороженного только одно. Вычисление вероятности ДЖУ,',1"1) = тах ^КГЧУо-1) сводится к рекурсивному применению

выражений (3) и (4), при этом поиск максимума в выражении (3) должен осуществляться по щ G F2-. Для вычисления метрики Т(и'{), у,"-1) необходимо найти оценки вероятностей Р ~ для 0 < j < г, где Р. является вероятностью ошибки декодирования алгоритмом последовательного исключения символа iij б F2»" при условии того, что известны правильные значения символов uj>, 0 < j' < j. В случае аддитивного Гауссовского канала задача вычисления Pj2 ^ может быть сведена к задаче вычисления математических ожиданий логарпф-

мических отношений правдоподобия (ЛОПП) = log ¡ ^ для случая

' 1 (<<п|'/|) )

иередггчи нулевого кодового слова, то есть uf,-1 = 0, u¡ € F2"', при применении Гаусс-овской аппроксимации. ЛОПП рассматриваются как зависимые Гауссов-скпе случайные величины с заданной ковариационной матрицей. Предлагается аппроксимировать числитель P(ii{¡~1,011) и знаменатель Р(«(')|2/()1-1) наибольшими слагаемыми, что позволяет свести задачу поиска математического ожидания ЛОПП /„. к задаче поиска математического ожидания максимума среди зависимых Гауссовских случайных величин с различными распределениями. Это математическое ожидание максимума предлагается оцепить посредством построения верхней и нижней границ, являющихся математическими ожиданиями максимумов из новых независимых Гауссовских случайных величин с различными распределениями. Сложность декодирования расширенных кодов Рида-Соломона можно оценить как 0(Ln'ilogn) операций над вещественными числами. Необходимо отметить, что при увеличении длины КОда п требуемый размер списка L растет экспоненциально.

В случае передачи двоичного образа кода Рида-Соломона по каналу без памяти можно показать, что Л2.»(и(„ у,"-1) = Щи)1 R ("оЬЬ Уа^Ш > гДе иоЬ1 = (tf„[j],..., u,[j]), u, = и u,[j]cij, u4[j] € F2, (a(),..., am-i) некоторый базис IFY», 11 vV\j\ подвектор вектора уЦ'1, соответствующий j-ым битам принятых символов. Таким образом, декодирование кода над F2™ может быть реализовано посредством т синхронизированных запусков декодера для двоичных кодов. Синхронизация необходима для вычисления R2m(u'(), у("-1) но найденным R (г'(>ЬЬ У()_1Ы)> 0 < j < т, на слое поляризующего преобразования, соответствующем входной последовательности, а также вычисления значений динамически замороженных символов согласно выражению (1) с использованием арифметики поля F2'". Применение этого подхода в случае передачи двоичного образа приводит к значительному снижению сложности декодирования.

Í9'")

Вероятность ошибки для символа u¡ может быть вычислена как P¿ = 1 — (1 — Pi)"1, где P¡ вероятность ошибки декодирования г-го бита двоичной входной последовательности при использовании алгоритма последовательного исключения. Таким образом, Г22».(г) = JJ (1 — Pf ') может быть вычислена

с номощыо методов, разработанных для двоичных полярных кодов. На Рис. 3 приведен график зависимости вероятности ошибки декодирования от отношения сигнал/шум для предлагаемого алгоритма декодирования и метода направленного поиска, корректирующая способность которого такая же, как у стекового алгоритма последовательного исключения. При той же корректирующей способности предлагаемый алгоритм декодирования обеспечивает значительное снижение сложности по сравнению со стековым алгоритмом последовательного исключения и декодированием методом направленного поиска. Также приведены данные для метода Кёттера-Вардп.

В четвертой главе предложен комбинаторно-алгебраический алгоритм

В|,/«<1. «В

Рис. 3. Вероятность ошибки декодирования кода Рида-Соломона (31,15) в случае передачи двоичного образа по аддитивному Гауссовскому каналу

декодирования длинных (п, к) кодов Рида-Соломона. Данный алгоритм построен на базе метода Кёттера-Варди и метода Чейза. Для реализации интерполяционного шага метода Ксттера-Варди разработан быстрый алгоритм двумерной интерполяции. Результаты четвертой главы опубликованы в работах [2, 4, 5|.

На интерполяционном шаге метода Кёттера-Варди решается задача построения интерполяционного полинома по множеству точек !.г,. ;/,•). О < г < п, О < э < (?. При этом интерполяционный полином должен иметь минимально возможную (1 ,к — 1)-взвешенную степень и корни кратности как минимум Мц во всех точках Точка является корнем полинома С}(х,у)

кратности Л/,.;, если соответствующие производные Хассе х,у) удовлетворяют условию (^"^{х)^]) = 0, а + /3 < Л/, Интерполяционный шаг является наиболее трудоемким. Известно, что искомый полином <5(.т, у) содержится в базисе Грёбнера идеала многочленов, имеющих корни кратности М^.

Предлагаемый алгоритм двумерной интерполяции предполагает итеративное построение требуемого идеала многочленов, при этом кратности корней увеличиваются согласно двоичному методу возведения в степень. Применение метода перекодирования позволяет обеспечить дополнительное снижение сложности. Сложность предлагаемого алгоритма декодирования составляет 0(?г2/; '), где /.I наибольшее значение кратности Мц. Кроме того, предложен комбинаторно-алгебраический алгоритм декодирования, использующий метод Чейза для снижения вероятности ошибки. Более конкретно, осуществляется перебор двух наиболее вероятных значений для заданного числа наименее надежных символов принятой последовательности. Переиспользование результатов промежуточных вычислений позволяет избежать многократное увеличение сложности.

В пятой главе представлен метод кодирования информации для отказо-

устойчивых систем хранения данных, основанный на теории полярных кодов. Изложен разработанный алгоритм систематического кодирования полярных кодов с произвольным двоичным ядром поляризации, в основе которого лежит алгоритм, предложенный Э.Л. Блохом и В.В. Зябловым для обобщенных каскадных кодов. Идея предлагаемого алгоритма заключается в сведении задачи систематического кодирования полярного кода длины I"1 с 1x1 ядром поляризации М к I задачам систематического кодирования полярного кода длины V'l~l. Алгоритм предполагает, что ядро М является нижнетреугольной матрицей с единичной диагональю. Показано, что это предположение не влияет на вероятность ошибки декодирования, достижимую используемыми полярными кодами. В случае полярного кода с ядром Арикана асимптотическая сложность предлагаемого алгоритма равна O(nlogn) и совпадает со сложностью алгоритма Арикана, где п длина кода. В случае I х I ядра БЧХ сложность предлагаемого алгоритма О (nlog(n) log1+"(0)! W а <2.

Рассмотрено применение предложенного подхода в отказоустойчивых системах хранения данных, включающих в себя совокупность высокопроизводительных твердотельных дисков. Необходимость кодирования данных в таких системах возникает вследствие недостаточной надежности дисков. Было показано, что предложенный метод позволяет построить кодер с производительностью, превышающей производительность кодера кода Рида-Соломона в 1.6 раза при сопоставимых параметрах кодов. Заметим, что при обновлении даже небольшого числа информационных символов кодового слова может потребоваться обновление почти всех проверочных символов, что ведет к перегрузке дисков, на которых хранятся проверочные символы. В классических архитектурах RAID-5 и RAID-G для решения этой проблемы используется циклический метод балансировки нагрузки. Однако он не может быть использован в сочетании с кодами, не являющимися кодами с максимальным достижимым расстоянием. Предлагаемый метод балансировки нагрузки предназначен для двоичных обобщенных каскадных кодов с внутренними полярными кодами с ядром Арикана п внешними двоичными линейными кодами, в частности, он может быть использован для полярных кодов с ядром Арикана, представленных в виде обобщенных каскадных. Метод включает две составляющие: балансировка нагрузки для внешних кодов и балансировка нагрузки для внутренних кодов. Для внешних кодов выполняется построение семейства вложенных множеств информационных совокупностей, используемых для размещения информационных символов. Это обеспечивает балансировку нагрузки среди группы дисков, соответствующих заданному внешнему коду. Балансировка нагрузки между различными группами дисков обеспечивается благодаря записи половины кодовых слов внутреннего кода в обратном порядке. Показано, что если внутренний код является полярным кодом с ядром Арикана, то получаемые при кодировании последовательности являются кодовыми словами исходного обобщенного каскадного кода. Численные результаты показывают, что обеспечивается степень сбалансированности нагрузки на носители данных, близкая к

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

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

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

Предложена конструкция кодов, называемых полярными подкодами БЧХ, декодирование которых может быть эффективно выполнено с помощью списочного/стекового алгоритма последовательного исключения и его аналогов.

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

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

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

Выполнено обобщение предлагаемого метода последовательного декодирования на случай полярных кодов с произвольным двоичным ядром. Численные результаты показывают, что предлагаемый подход позволяет выполнять декодирование полярных кодов с ядром БЧХ почти по максимуму правдоподобия. На базе предложенного метода последовательного декодирования построен алгоритм декодирования коротких кодов Рида-Соломона над полем Рг-. Показано, что предлагаемый подход обеспечивает меньшую вероятность ошибки декодирования, чем метод Кёттера-Варди.

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

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

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

|1| Милославская В. Генератор двоичных полярных кодов с ядром большой размерности. Свидетельство о государственной регистрации программы для ЭВМ 2012614815. 2012.

|2| Милославская В., Трифонов П. Гибридный алгоритм мягкого декодирования кодов Рида-Соломона // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. 2011. № 2. С. 169 174.

|3| Заявка 20Ц1Ц215 Российская Федерация, МПК G 06 F 11/00. Способ и устройство кодирования и декодирования данных в скрученном полярном коде / Милославская В., Трифонов П.; заявитель Самсунг Электронике Ко., Лтд.; пат. поверенный Мпц A.B. №364; заявл. 10.04.2014. 36 е.: ил.

|4| Müoslavskaya V., Trifonov P. Fast interpolation in algebraic soft decision decoding of Reed-Solomon codes // Proceedings of IEEE R8 International Conference on Computational Technologies in Electrical and Electronics Engineering. 2010. Pp. 65 69.

|5| Müoslavskaya V., Trifonov P. Hybrid interpolation algorithm for algebraic soft decision decoding of Reed-Solomon codes // Proceedings of 8th IEEE International Symposium on Wireless Communication Systems. 2011. Pp. 131 135.

IОI Müoslavskaya V., Trifonov P. Design of polar codes with arbitrary kernels // Proceedings of IEEE Information Theory Workshop. 2012. Pp. 119 123.

|7| Müoslavskaya V., Trifonov P. Performance of binary polar codes with high-dimensional kernel // Proceedings of International Workshop on Algebraic and Combinatorial Coding Theory. 2012. Pp. 263 268.

|8| Müoslavskaya V., Trifonov P. Sequential decoding of polar codes // IEEE Communications Letters. 2014. Vol. 18, no. 7. Pp. 1127 1130.

¡9j Müoslavskaya V., Trifonov P. Sequential decoding of polar codes with arbitrary binary kernel // Proceedings of IEEE Information Theory Workshop. 2014. Pp. 377 381.

1101 Müoslavskaya V., Trifonov P. Sequential decoding of Reed-Solomon codes // Proceedings of International Symposium on Information Theory and Applications. 2014. Pp. 424 428.

|11| Trifonov P., Müoslavskaya V. Polar codes with dynamic frozen symbols and their decoding by directed search // Proceedings of IEEE Information Theory Workshop. 2013. September. Pp. 1 5.

Подписано в печать 22.12.2014. Формат 60x84/16. Печать цифровая. Усл. печ. л. 1,0. Тираж 100. Заказ 12622Ь.

Отпечатано с готового оригинал-макета, предоставленного автором, в Типографии Политехнического университета. 195251, Санкт-Петербург, Политехническая ул., 29. Тел.: (812) 552-77-17; 550-40-14