автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Эффективная реализация алгоритмов декодирования РС-кодов

САНКТ-ПЕТЕРБУРГСКИЙ ИНСТИТУТ АВИАЦИОННОГО ПРИБОРОСТРОЕ>йЯ

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

ЗАХАРОВА Татьяна Германогла

ЭФФЕКТИВНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ ДЕКОДИРОВАНИЯ РС-КОДОВ

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

системах

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

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

Работа выполнена в Институте авиационного приборостроения, г. Санкт-Петербург

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

доцент Б.Д. Кудряшов

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

доктор технических наук-, профессор Б.В. Титкое кандидат.технических наук, с.н.с. В.Б. Афанасьев

Ведущая организация - Научно-исследовательский институт программных средств

Защита диссертации состоится » 1992 г.

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

К 063.21.03 Института авиационного приборостроения по адресу: 190000, Санкт-Петербург, ул. Герцена, 67

С диссертацией можно ознакомиться в библиотеке института. Автореферат разослан " 2-е- к а а " 1992 Г.

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

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

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

с<!;:'таций|

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

На практике в качестве корректирующих кодов очень часто используются коды Рида-соломона (РС-коды) над полем вРС? ). Это связано прежде всего с тем, что коды Рида-Соломона обладают наибольшим кодовым расстоянием, а кроме того имеют алгебраические методы декодирования. Коды Рида-Соломона успешно используются в каскадных конструкциях, при построении кодов с большими длинами. Практический интерес к кодам Рида-Соломона над полем вР(2т) обусловлен еще и тем, что элементы поля 0Г(2а) представляются в виде двоичных векторов и с ниш легко оперировать, используя цифровые схемы или ЭВМ.

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

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

Исходя из этого, можно сделать вывод о том, "что задача построения быстродействующих декодирующих устройств РС-кодоа тесно связана с задачей поиска новых аффективных методов вычислэния преобразования Фурье в полях характеристики 2.

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

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

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

- разработать алгоритм вычисления ПФ в поле 0Р(2т), инвариантный к числу вычисляемых компонент и размеру полл;

- исследовать эффективность разработанного алгоритма по числу операций сложения и умножения;

исследовать возможность применения разработанного алгоритма БПФ дам кодирования и декодирования РС-кодов:

- разработать программное обеспечение для построения вычислителей БПФ;

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

Новые результаты и положения, выносимые на защиту :

- алгоритм вычисления преобразования Фурье в поле вВ(2!п), позволящий сократить число операций при вычислении ПФ в поле СР(ёт), в том числе при вычислении неполного ПФ;

- подход к вычислению ПФ, позволящий снизить трудоемкость создания вычислителя ПФ в поле СР(ёт)ш.

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

Практическая ценность работы. Практическая ценность работа состоит в следующем:

- предложена методика эффективной реализации вычислителя синдрома, вычислителя номеров ошибочных позиций и реализации кодирования для кодов Рида-Соломона;

- разработан пвкет программ для построения вычислителя преобразования Фурье в поле 0Р(2п) с заданным числом входных и выходных символов;

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

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

"Автоматизированные системы управления" Института авиационного приборостроения, отражены в отчетах по НИР и использоввни при

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

Апробация работа.Основные результаты диссертационной работы докладывались, обсуадались и получили одобрение на:

- DC Всесоюзном симпозиуме по проблемам избыточности i информационных системах (С-Петербург, 1989);

- девятой всесоюзной конференции по теории кодирования i передачи информации (Одесса, 1988);

- научном семинаре НТО РЭС им. A.C. Попова (С-Петербург 1990);

- XVIII Всесоюзной школе-семинаре по теории информации и ei приложениям, проводимой ИППИ (Белорецк, 1991);

а также семинарах по теории информации и кодирования кафедры АСУ СПИАП (С-Петербург, 1988-1992).

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

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

КРАТКОЕ СОДЕРЖАНКЕ РАБОТЫ

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

Первый раздел посвящен обзору вопросов, связанных построением быстродействующих декодирующих устройств, определе!

есто данной работы в общей проблематике построения систем ередачи информации и формулируются задачи исследования, ^основано использование в качестве корректирующего кода кода ■ида-Соломона. Показано, что коды Рида-Соломона* допускают [римйнвние быстрых алгоритмов вычисления преобразования Фурье при гостроении кодеров и декодеров. На основе обзора известных (етодов построения Б1№ в полях GF(P) делается вывод о том, что )ти метода расчитаны на вычисление всех Компонент спектра. 1оэтрму они практически не позволяют уменьшить сложность декодера ^С-кода. Кроме того, построение оптимального вычислителя БПФ 1звестными методами связано с большой подготовительной работой, но сильно затрудняет разработку декодера. Отсюда делается вывод з необходимости разработки более эффективных методов построения ЗПФ в полях GF(2*), использование которых позволит повысить быстродействие кодеров и декодеров РС-кодов.

. На практике коды Рида-Соломона чаще используются совместно о другими блоковыми кодами в каскадных конструкциях. Это позволяет получать коды с большими длинами, а кроме того такой код способен исправлять больнее число ошибок. Одним из эффективных способов построения каскадных кодов является использование в качестве внутренних кодов блоковые коды, получаемые из сверточных. Эти коды впервые были рассмотрены в работах На H.H. и Wolf J.K. Сочетание PC-кодов в каскадных конструкциях с блоковыми кодами, получаемыми из сверточннх, позволяет использовать их в каналах с мягкими решениями. Это служит обоснованием необходимости анализа ансамбля блоковых кодов, получаемых из сверточных.

Второй раздел посвящен разработке алгоритма построения вычислителя преобразования Фурье в полях характеристики 2. Описываемый алгоритм построения БПФ в поле GF(2*) позволяет существенно уменьшить число операций, особенно операций умножения, при вычислении ПФ и применим при любых соотношениях .мэкду размером конечного поля и числом вычисляемых компонент.

Как изрестно, преоЯрчзовятае Фурьэ в поле GF(^) вектора й длины п, гдо п делит 2т~1 при некотором т, определяется как

- б -

вектор 3 , компоненты которого задаются равенствами

= "еЧ" а. .1= О.....и-», (1)

' 1=0 1

где 7 - элемент порядка п в поле СР( 2т).

Неиосродствэнное вычисление преобразования Фурье по формуле (1) требует п2 умножений и п2 сложений. Уменьшение числа операций достигается за счет использования особенностей коночного поля СР^).Поскольку любой элемент поля может быть разложен по базисным векторам этого поля

7й " Д Р* . внг).

то выражение (1) можно записать в следующем виде

п-1 . п-1 ,, ,

А, = Е Р 2 й , о. , 1=0.....П-1 .

}=0 {=0 *

При такой записи ПФ необходимо выполнить только пя умножений и в общем случае не более гс(т+пл) сложений элементов поля вР(21) для вычисления п компонент спектра. Дальнейшее сокращение числа умножений, а также сокращение числа сложений ■ происходит за счет того, что спектральные компоненты, номера которых принадлежат одному и тому ке шклотомическому классу, связаны простыми соотношениями

т-1 , т-1 „ п-1 .,.

Лд ' Е Р* 2 ь\2и- Е *[)> а1 ,

2 1 ¿=0 и=0 1=0 1

где индекс I указывает на номер циклотомического класса, £ индекс а - на номер в этом циклотомическом классе.

Дополнительное сокращение вычислений возможно в том случае, если среди циклогомических классрв имеются такие, мощность которых меньше степени расширения поля т. Это означает, что £ поле СВ(2) имеется подполе ). Тогда элементы 71{ для

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

7й = Е <Р*У ь{)} .

J=o

где к[у € GF(2) , v-(2m-1 )/(c,"l-i). Введем следующие обозначения

(m.-1)v

Fn = (1. P"..... P 1 ).

I

K, = { ftj ) , l = S/iM , J = ÖTrPT ,

( |Tfl j (J l

% = { fij > ' = ' - •

и «формулируем полученные результаты в виде теоремы . Теорема.

Пусть й. - ( а0. aJt..., an J; - вектор над GF(2m), где п i 2т-1 и пусть р - примитивный элемент поля GF(2n), Ъ - множество миятчлъных элементов циклотомических классов, на которые расиадиотся множество целых чисел по модулю числа 2т-1. Тогда Ш>

в поле GF(^) вектора а есть вектор 2 = ( А0, At,..., компоненты которого можно вычислить следующим образом

А „ = ( В , ( 5 К. Р* )), э = О.п yl , I < L (2) 2 1 I 1 1

Из внрпкеття (2) видно, что сопряпешшо частота спектра отличаются только ствпеиьа а, в которую возводится матрица Р. Ко;.токенты с номерами из разных циклотомических классов, но одашаковой длины, отличается только матрицами К. Тогда компоненты с номерами из разных циклотомических классов разной длины отличаются и матрицами F, и матрицами IX, и сектором

констант р.

Шчисление по формуле (г) удобно разбить па три этвпа. Сначала вычислить произведение вектора а на всэ патрицы К . Затем h.-,."l,i ¡•.^..иисдииш шлучошюго вектора па матрицы Р, а потом вычислить скалярные произведения.

Поскольку матрицы К и Р двоичные, то при умножении на шпе операций ушокения элементов поля GF(f^) не требуется. Умножения

в поло GF(2") выполняются только при умнояешга но вектор р. При этом число угаоганпй для каздой когшопентн будет определяться

длиной вактора $ , а число сложений - числом единиц в матрицах К

И Ж.

Дальнейшее сокращение числа операций связано с тем, что

вэктор констант "Р и матрицы К и Р зарвнее известны. Вычисления моино организовать таким образом, чтобы все промежуточные значения использовались при последующих вычислениях. В диссертационной работе разработаны алгоритмы оптимизации порядка выполнения операций умножения и сложения при вычислении ПФ по формуле (2) , а также получены оценки числа операций.

Для циклотомических классов одинаковой длины число операций, требуемое для вычисления всех сопряженных частот, будет одинаково. Как известно число циклотомических классов длины т1 равно числу 1(тх)

1(тг) = 1/т1 2 \1Ш) г*1'* ,

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

выражениями

К - Е *„(*!> 1(п1> • О)

' т1|П • * 1

"о = + 2 V V тг) , (4)

то ^ I та

где величины Иу(^) и М0(!\) это число умножений и число сложений, требуемых при вычислении всех п^ компонент ПФ, номера которых принадлежат 1-му циклотомическому классу, величина Нс( определяет число сложений , требуемых при умножении вектора а на все матрицы К1 т . Значения величин Н (тг) и ^с(п1) для 8

■ приисдоны в Таблице 1, а значения величин N { для п ( 255 привздены в Таблице 2.

Приведенные в Таблицах 1 и 2 данные позволяют воспользоваться оценками числа операций (3) и (4) при вычислении П® всех длин до 255.

Таблица 1

Число умножений в зависимости от мощности цнклотомического класса

ITlj 1 2 3 4 5 б 7 в

W О 1 3 5 10 10 26 21

W О 2 6 13 28 33 54 75

Таблица 2

Число сложений, требуемоо при умножении вектора а на «атриц« К.

п 3 5 7 9 15 17 31 51 63 85 127 255

"о, 3 6 14 го 59 60 гго 480 641 1212 2765 4500

Анализ построения алгоритмов ПФ показал, что по сравпеппп с

известными алгоритмами БПФ для простых длпп достигается

суцэственшй виигршп как по числу умножений, так и по числу

сложений. Для составных длил выигрыш достигается только по числу

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

одномерного ш> составной длины к многомерно?,!у ПФ, и применяя

предлагаемый алгоритм построотт БПФ для простых составляй^.

мояпо построить алгоритмы БПФ в поле GF(¡¡О*), выигрнвашие по

сравнению с известными алгоритмами как по числу умножений, так и

по числу сложений. Оценки числа умножений 1L, и числа сложений ff

У с

д.1Л построенных алгоритмов приводятся в Таблице з. В этой з:е таблице приведены характеристики лучших изпоспшх алгоритмов /?

и N .

с

В диссертационной работе получены ясимптотичес:сю оцешш числа операций при пичислешш ПФ по формуле 2. Показано , что число умножений есть воличипа порядка п log п , при отом число сложошй оценивается величиной n2/log п .

Таблица э

Оценки числа операция при вычислении ПФ длены п

п Ву(п) Я0(П) К<п>

3 1 5 1 5

5 5 15 5 15

7 6 26 9 35

9 11 44 11 44

15 20 70 20 70

81 25 113 59 235

17 42 210 34 140

31 60 388 108 645

51 143 715 . 194 790

63 131 542 158 623

85 295 1205 380 1430

127 468 3737 594 5770

255 970 4040 1225 4715

На основе предложенного способа вычисления преобразования Фурье разработан пакет программ, дозволящий с помощью ЭШ строить оптимальные схемы вычислителей БПФ для заданного поля, число входшх и выходных компонент. Схема вычислителя выводится в любом удобном для пользователя ввдэ, например в виде програ;,ыы на язике лбвшвъек.

ТротШ раздал посвящен построению бнстродайствупцшс декодирующих устройств кода Рида-Соломона. Рассматривается вэзшшюсть повышения аЭДэктпшюста декодирующих устройств за счот использования получешшх в продадуцьы раздело алгоритмов КПФ, а та!саэ уменьшение числа операций за счет рациональной организации вычислений, упрощения формул, отказа от циклов.

В Таблице 4 приведены при,¡эра кодеров и декодеров,

- и -

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

Таблица 4

Сложность кодера я декодера для (63.57) я (51,40) РС-кодов

у стр. код

(63,57) РС-код над а?(26) (51,40) РС-код над а?(2в)

разработ. станд. резработ. ст8нд.

"о Кс Л Но

кодер 30 460 342 336 77 478 400 390

декодер 100 535 531 590 244 808 814 839

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

Раздал заканчивается описанием систем связи, при разработке которых использовались предлагаемые алгоритмы. Так, например, код Ридэ-Соломона (51,40) над полем 0Р(3В) использовался в системе связи, обосиочивавдей обмен информацией по телефонным каналам мовду абонентами, располагающими IВЦ совместимыми компьютерами. п{югр8мма кодера и декодера на языке аэбежш* доя компьютера типа ГШ рс была получена с помощью разработанного програмшого обеспечения. По сравнении с обычной реализацией кодера и декодера для этого кода выигрыш по быстродействию достигается примерно в 4 рОПО

В четвертом разделе рассматривается ансамбль блоковых кодов, получаемых из сверточных усечением с "полной нейтрализацией хвостов" . Показано, что представление блоковых код-м< » виде евврточных позволяет использовать эти код?! в каяало

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

Таблица 5

Таблица кодов

Скорость, Параметры лучшего линейного блокового кода, п, к, <2 Кодовое ограничение свврточного кода, V Структура сверточного кодера

1/? 16, 8, 5 3 3, 11

24.1», Я 6 51,127

38,19, а 5 15. 57

46,23,10 . 6 135.147

1/3 18, 6, 8 3 3. 7.13

39,13,1? 4 25,33,37

43,16,11 6 117,113,155

1/4 32, 8,12 3 3,13.15.17

48,12,16 4 25.27,33,37

5?,13,17 5 31.55,67,75

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

Поскольку сложность декодирования по максимуму правдоподобия для этих кодов определяется слодувдими выражениями

н с/гп г».

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

виде сверточных позволяет упростить декодирование этих кодов по максимуму правдоподобия в канэлах с мягкими решениями. Так, например, представление (16,8,5) блокового кода п виде сверточного позволяет упростить его декодирование по максимуму правдоподобия в 16 раз.

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

В Приложениях приводятся вспомогательные материалы, алгоритмы вычисления преобразования Фурье в полэ GF(2T>) для коротких длил, а также программа вычислителя БПФ длины 7, полученная с помощью ЭВМ.

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

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

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

2. Получены асимптотические оценки числа операция слокения и умножения при вычислении ПФ по предложенному алгоритму. Показано, что число умножений ость величина порядка п log п, при этом число сложений оценивается величиной пг/ log п.

3. Предложены процедуры минимизации числа операций при построении ПФ для коротких длин. Это позволило получить алгоритм! БПФ в поле СР(2Ш), выигрывающие по сравнению с известными по числу операций сложения и умножения. Приведены алгоритма коротких БПФ.

4. Разработан пакет программ для построения вычислителя преобразования Фурье в поло GP(2™). Разработаппое програмгяюэ обеспечение позволяет автоматизировать процесс создания

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

5. Указаны аффективные методы реализации кодирования кодом Рида-Соломона, вычисления синдрома и вычисления номеров ошибочных позиций при декодировании PC-кодов. При разработке этих методов был использован предложенный алгоритм построения вычислителя БПФ в поле GF(2*). Уменьшение числа операций, особенно числа умножений, позволяет в несколько раз уменьшить время кодирования и декодирования для кодов Рида-Соломона.

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

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

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

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

1. Захарова Т.Г., Кудряшов Б.Д. Быстрое декодирование кода Голея (24,12) с помощью ЭВМ // Помехоустойчивое кодирование и надежность ЭВМ. М.: Наука, 1987, с. 24-28

2. Кудряшов Б.Д., Захарова Т.Г. Блоковые кода, получаемые из сверточных // Проблемы передачи информации , 1987, т. 25, N 4, С. 98-102.