Анализ эффективности декодирования циклических кодов с использованием двойственного базиса тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Кукунин, Дмитрий Сергеевич

• Кукунин, Дмитрий Сергеевич
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Кукунин, Дмитрий Сергеевич

Введение.

1. Аспекты применения двойственного базиса поля Галуа.

1.1. Двойственный базис поля Галуа.

1.2. Применение двойственного базиса.

1.3. Проблемы работы с полями Галуа.

1.4. Выводы. Задачи диссертационной работы.

2. Анализ эффективности декодирования двоичных циклических кодов

2.1. Особенности построения двоичных циклических кодов.

2.1.1. Двоичные циклические коды БЧХ.

2.1.2. Построение циклических кодов как рекурсивных последовательностей.

2.1.3. Коды максимальной длины.

2.2. Методы декодирования циклических кодов.

2.2.1. Оцениваемые параметры системы передачи данных.

2.2.2. Алгебраический декодер. Таблица остатков.

2.2.3. Корреляционный метод.

2.2.4. Синдромный метод декодирования кодов БЧХ.

2.3. Обработка рекуррентных последовательностей двойственным базисом поля Галуа

2.3.1. Декодирование кодов максимальной длины.

2.3.2. Использование децимаций при декодировании кодов максимальной длины.

2.3.3. Декодирование кодов БЧХЭ.

2.3.4. Эффективность методов декодирования кодов БЧХ.

2.4. Выводы.

3. Разработка методов оценки качества канала.

3.1. Особенности методов оценки качества канала.

3.2. Разработка методов оценки качества канала на основе двойственного базиса.

3.2.1. Метод разности двух наибольших "деревьев".

3.2.2. Метод оценки канала по частоте появления "деревьев".

3.2.4. Выбор метода оценки канала.

3.3. Выводы.

4. Разработка методики адаптации системы к состоянию канала.

4.1. Подходы к построению адаптивных систем.

4.2. Система с адаптивным выбором кода.

4.3. Выводы.

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

5.1. Программная реализация калькулятора Галуа.

5.1.1. Формирование поля и его хранение.

5.1.2. Реализация базовых операций в калькуляторе Галуа.

5.1.3. Особенности работы с полем большого порядка.

5.1.4. Метод контрольных точек.

5.2. Организация калькулятора Галуа.

5.2.1. Структура калькулятора Галуа.

5.2.2. Калькулятор Галуа для работы в локальной сети.

5.2.3. Калькулятора Галуа для работы в глобальной сети.

5.3. Выводы.

Введение диссертации (часть автореферата) на тему «Анализ эффективности декодирования циклических кодов с использованием двойственного базиса»

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

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

Свойства кодов БЧХ подробно рассмотрены в работах Питерсона У., Уэл-дона Э., Касами Т., Кларка Дж., Кейна Дж., Берлекэмпа Э. Повышенный интерес к кодам БЧХ подтверждается и тем, что разработано значительное количество алгоритмов декодирования таких кодов, как в частотной, так и во временной области. В работах профессора Когновицкого О.С. рассмотрена применимость двойственного базиса поля Галуа в вопросах декодирования циклических кодов с учетом их рекуррентных свойств. Рациональный выбор того или иного алгоритма требует проведения сравнительного анализа по корректирующим способностям различных методов декодирования кодов БЧХ, в том числе методов декодирования с использованием двойственного базиса.

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

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

Методы исследования. Проводимые исследования основываются на теории полей Галуа, теории двойственного базиса поля Галуа, теории кодирования, теории рекуррентных регистров сдвига и теории вероятностей. Для проведения численных расчетов использовались программные пакеты: MS Excel 2003, Mathcad 13, Advanced Grapher 2.11 и другие. Программное обеспечение, необходимое для решения поставленных в диссертации задач, реализовано в среде MS Visual С++ 6.0.

Научная новизна. Научная новизна работы состоит в следующем:

1. Исследован новый метод декодирования кодов БЧХ как рекуррентных последовательностей с использованием двойственного базиса.

2. Проведен сравнительный анализ эффективности метода декодирования на основе двойственного базиса и классических методов декодирования кодов БЧХ по вероятности правильного декодирования в зависимости от вероятности ошибки в канале.

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

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

5. Предложен новый вариант реализации дискретного логарифмирования в

Л | полях Галуа до GF(2 ) с использованием контрольных точек.

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

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

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

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

В качестве основного инструмента для проведения экспериментов был использован разработанный диссертантом программный комплекс — калькулятор

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

Реализация результатов работы. Основные научные результаты работы внедрены в практическую деятельность ЗАО Н1111 «ИСТА-Системс», а также используются в учебном процессе Санкт-Петербургского государственного университета телекоммуникаций им. проф. М.А. Бонч-Бруевича, что подтверждено соответствующими актами внедрения.

Апробация работы. Результаты работы обсуждались и были одобрены на 57, 58, 59, 60, 61 НТК профессорско-преподавательского состава и 57, 58, 59, 60 НТК студентов, аспирантов и молодых специалистов СПбГУТ. По результатам диссертации опубликованы работы [3, 10, 84, 85, 87, 119, 121 - 124, 126- 130].

Структура и объем работы. Диссертация состоит из введения, 5 глав, заключения и приложений. Работа содержит 169 страниц машинописного текста, 71 рисунок, 19 таблиц и список литературы из 130 наименований.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Кукунин, Дмитрий Сергеевич

4.3. Выводы

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

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

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

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

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

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

5.1. Программная реализация калькулятора Галуа

5.1.1. Формирование поля и его хранение

Поле GF(2*) представляет собой набор элементов 1,8,8 ,., 8 , количество которых 2k-l определяет порядок поля. Каждому элементу ет поля GF(2A) соответствует вектор, состоящий из к бит. Таким образом, программная реализация функций работы с полем требует определенных затрат ресурсов. В целях экономии памяти и рационального использования процессора, на который возлагается обработка операций над элементами, целесообразно выделять на хранение векторов и показателей степеней элементов целые числа.

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

Данную задачу можно решить с использованием языка программирования С++. Сначала определим переменные, необходимые для построения поля Галуа с заданными характеристиками. Для примера построим поле с характеристикой к=4 и характеристическим многочленом P(jc)=1+jc+jc4 [3]: int k=4; int n=15; int vector[15]; int exponents 6];.

Переменная к соответствует, вышеуказанному параметру поля, п=2к—\ определяет число ненулевых элементов. В данной ситуации нецелесообразно хранить в памяти нулевой элемент поля.

Массив vector содержит переменные, соответствующие векторам поля. Число элементов массива равно числу ненулевых элементов поля. Векторы поля будут храниться в памяти в виде целых чисел. В Windows при использовании 32-разрядных приложений на число типа int отводится 4 байта. Данное

147 свойство позволяет работать с полями GF(2*) с характеристикой до к=31 включительно. Для работы с большими полями требуются свои типы данных.

Дальнейшая методика построения поля состоит в определении вычета, который представляет собой часть характеристического многочлена без старшей степени. Для вычет в двоичном виде будет иметь вид (1100), что соответствует числу 12 в десятичной системе счисления: int Polinom=l2;

Формирование поля происходит путем сдвигов векторов с добавлением к ним вычета. Сначала необходимо определить первый элемент поля е°, соответствующий вектору (1000): vector[0]=1«k-1;.

Далее происходит присвоение первого элемента дополнительной переменной alpha, которая необходима для вычисления остальных векторов поля [3]: int alpha=vector[0]; for(inti=1;i<n;i++){ asm shr alpha, 1 asm jnc label alpha=alphaAPolinom; label: vector[i]=alpha;}.

Ассемблерная команда shr производит битовый сдвиг вправо. Бит, выходящий за пределы числа, помещается в регистр флагов в бит CF. Если в CF оказывается единица, к вектору добавляется вычет по mod 2. После этих операций массив vector будет хранить в памяти целые числа (табл. 5.1) [3].

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

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

1. Проведен сравнительный анализ эффективности методов декодирования циклических кодов, в результате которого отмечено, что применение двойственного базиса по сравнению с классическими методами (корреляционным, табличным и синдромным) обеспечивает более высокий уровень достоверности передачи данных. В качестве примеров рассмотрены М-последовательности, коды БЧХ длиной п=\ 5, а также ряд кодов БЧХ с я=31.

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

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

4. Разработаны два метода оценки качества канала в процессе передачи данных, основанные на использовании двойственного базиса. Более эффективным является метод оценки канала по частоте появления "деревьев", который обеспечивает определение вероятности ошибки в канале параллельно процессу декодирования кодовых комбинаций независимо от его результатов.

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

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

Список литературы диссертационного исследования кандидат технических наук Кукунин, Дмитрий Сергеевич, 2009 год

1. Когновицкий О.С. Основы циклических кодов: Учеб. пособие. — Л., 1972.

2. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М., 1976.

3. Кукунин Д.С., Охорзин В.М., Новодворский М.С. Построение каскадных кодов на основе кодов БЧХ и Рида-Соломона. СПб., 2004. 58 С.

4. Касами Т., Токура Н., Ивадари Ё., Инагаки Я. Теория кодирования. — М., 1978.

5. Когновицкий О.С. Алгебраический метод нахождения двойственного базиса в поле Галуа и его практическое применение // Сборник научных трудов учебных институтов связи, -JL, 1982.

6. Когновицкий О.С. Об одном алгоритме мажоритарного декодирования кодов максимальной длины / Девятая всесоюзная конференция по теории кодирования и передачи информации. Тезисы докладов. Часть 1. Одесса, 1988.

7. Когновицкий О.С., Свердлов JI.M. Мажоритарное декодирование М-последовательно-стей с использованием децимаций // 49-я НТК: тез. докл./ СПбГУТ. СПб, 1996.

8. Когновицкий О.С. Метод мажоритарной обработки псевдослучайной последовательности по ^-произвольным линейно независимым ее элементам // 49-я НТК: тез. докл./ СПбГУТ. СПб, 1996.

9. Когновицкий О.С. Алгоритмы обработки рекуррентных псевдослучайных последовательностей в задачах передачи данных // Юбилейная НТК: тез. докл./ СПбГУТ. СПб, 2000.

10. Кукунин Д.С., Когновицкий О.С. Метод декодирования эквидистантных кодов // Труды учебных заведений связи / СПбГУТ. СПб, 2006. № 174. С. 45-52.

11. Когновицкий О.С. Мажоритарное декодирование циклических кодов как рекуррентных последовательностей с разложимым характеристическим многочленом // 50-я НТК: тез. докл./СПбГУТ. СПб, 1997.

12. Когновицкий О.С. Метод алгебраического кодового разделения рекуррентных последовательностей с различными характеристическими многочленами // 51-я НТК: тез. докл./ СПбГУТ. СПб, 1998.

13. Когновицкий О.С. Аналитические методы решения линейных модулярных разностных уравнений и их сравнение // 52-я НТК: тез. докл./ СПбГУТ. СПб, 1999.

14. Когновицкий О.С. Реализационные основы применения двойственного базиса поля Галуа в задачах передачи и обработки данных // 54-я НТК: тез. докл./ СПбГУТ. СПб, 2002.

15. Когновицкий О.С. Циклические коды БЧХЭ как рекурсивные последовательности // Труды учебных заведений связи / СПбГУТ. СПб, 2006.

16. Когновицкий О.С. Циклические коды Рида-Соломона как рекурсивные последовательности // 57-я НТК: тез. докл./ СПбГУТ. СПб, 2005.

17. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. Перевод с англ. М.: Радио и связь, 1987.

18. Zook Christopher P. Finite Field Inversion // Патент WO 95/12845. May 11.- 1995.

19. Zook Christopher P. Finite Field Inversion // Патент US 5,467,297. -Nov. 14. 1995.

20. Fenn S.T.J., Benaissa M., Taylor D. GF(2*) Multiplication and Division Over the Dual Basis // IEEE Transactions on Computers. 1996. - Vol. 45. - P. 319-327.

21. Fenn S.T.J., Benaissa M„ Taylor D. Finite Field Inversion Over the Dual Basis // IEEE Transactions on VLSI Systems. 1996. - Vol. 4. - n. 1. - P. 134-137.

22. Chiou-Yng Lee, Che Wun Chiou, Jim-Min Lin Concurrent Error Detection in a Bit-Parallel Systolic Multiplier for Dual Basis of GF(2m) // Journal of Electronic Testing: Theory and Applications. 2005. - Vol. 21. - P. 539-549.

23. Burton S. Kaliski Jr., Yiqun Lisa Yin Method and apparatus for efficient finite field basis conversion // Патент US 5,854,759. Dec. 29. - 1998.

24. Lambert R„ Gallant R„ Mullin R., Scott A. Vanstone Method and apparatus for finite field basis conversion 11 Патент US 2002/0025038 Al. Feb. 28. - 2002.

25. Weon-Il Jin, Mi-Suk Hun, Shang-Woo Seo Method and apparatus for basis conversion in finite field // Патент US 2004/0098437 Al. May 20. - 2004.

26. Weon-Il Jin Method and apparatus for basis conversion in finite field and a multiplier // Патент ЕР 1 455 270 A2. Sept. 8. - 2004.

27. Weon-Il Jin Method and apparatus for basis conversion in finite field and a multiplier // Патент ЕР 1 455 270 A3. Jun. 28. - 2006.

28. Chang-Hyi Lee, Jong-In Lim A New Aspect of Dual Basis for Efficient Field Arithmetic // PKC'99, LNCS 1560. 1999. - P. 12-28.

29. Zook Christopher P. Method and apparatus for determining the coefficients of a locator polynomial // Патент US 4,845,713. Jul. 4. - 1989.

30. Ba-Zhong Shen Error correction system for five or more errors // Патент US 6,343,367 B1. -Jan. 29. 2002.

31. ТанакаХ., Касахара M. Использование регистров сдвига для вычислений в полях Галуа // Экспресс-информация. Передача информации. 1969. - №2.

32. Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971.33