Введение - Построение декодера Рида - Маллера

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

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

История помехоустойчивого кодирования началась в 1948г. публикацией знаменитой статьи Клода Шеннона. Шеннон показал, что с каждым каналом связано измеряемое в битах в секунду и называемое пропускной способностью канала число С, имеющее следующее значение. Если требуемая от системы связи скорость передачи информации R (измеряемая в битах в секунду) меньше С, то, используя помехоустойчивые коды, для данного канала можно построить такую систему связи, что вероятность ошибки на выходе будет сколь угодно мала [1]. Из теории Шеннона следует, что построение слишком хороших каналов связи является расточительством, экономически выгодней использовать помехоустойчивое кодирование. Шеннон, однако, не показал, как найти подходящие коды, а лишь доказал их существование. В пятидесятые годы много усилий было потрачено на попытки построения в явном виде классов кодов, позволяющих получить обещанную сколь угодно малую вероятность ошибки, но результаты были скудными. В следующем десятилетии решению этой увлекательной задачи уделялось меньше внимания, вместо этого исследователи кодов предприняли длительную атаку по двум направлениям.

Первое направление носило чисто алгебраический характер и преимущественно рассматривало блоковые коды. Первые блоковые коды были введены в 1950г., когда Хэмминг описал класс блоковых кодов, исправляющих одиночные ошибки. Коды Хэмминга были разочаровывающе слабы по сравнению с обещанными Шенноном гораздо более сильными кодами. Несмотря на усиленные исследования, до конца пятидесятых годов не было построено лучшего класса кодов. В течение этого периода без какой-либо общей теории были найдены многие коды с малой длиной блока. Основной сдвиг произошел, когда Боуз и Рой-Чоудхури и Хоквингем[1] нашли большой класс кодов, исправляющих кратные ошибки (коды БЧХ), а Рид и Соломон [1960] нашли связанный с кодами БЧХ класс кодов для недвоичных каналов. Хотя эти коды остаются среди наиболее важных классов кодов, общая теория помехоустойчивых блочных кодов с тех пор успешно развивалась, и время от времени удавалось открывать новые коды.

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

В 70-х годах эти два направления исследований опять стали переплетаться. Теорией сверточных кодов занялись алгебраисты, представившие ее в новом свете. В теории блоковых кодов за это время удалось приблизиться к кодам, обещанным Шенноном: были предложены две различные схемы кодирования (одна Юстесеном, а другая Гоппой), позволяющие строить семейства кодов, которые одновременно могут иметь очень большую длину блока и очень хорошие характеристики. Различного рода исследования помехоустойчивых кодов активно продолжаются до сих пор.

В данном курсовом проекте необходимо разработать декодер кода Рида - Маллера с параметрами (n, k) = (32, 26).

Коды Рида - Маллера (РМ коды) являются одним из наиболее старых и хорошо изученных семейств кодов. Минимальное расстояние РМ кодов меньше, чем минимальное расстояние кодов БЧХ, за исключением кодов первого порядка и кодов с умеренными длинами. Однако большим достоинством РМ кодов является то, что они достаточно просто декодируются при помощи мажоритарно-логических устройств. Интересной особенностью кодов Рида - Маллера является то, что код Рида - Маллера r-го порядка дуален коду Рида - Маллера (m - r - 1)-го порядка

РМ коды являются простейшим примером класса геометрических кодов. Этот класс содержит также евклидово-геометрические и проективно - геометрические коды. Все коды этого класса допускают мажоритарное декодирование.

Коды Рида - Маллера характеризуются следующими параметрами[2]:

R - порядок кода, m - некоторое число, большее r, причем:

N = 2M (1),

D0 = 2M-r (2),

(3),

Где - число сочетаний i по m.

Код Рида - Маллера может исправлять следующее число ошибок[2]:

(4).

Похожие статьи




Введение - Построение декодера Рида - Маллера

Предыдущая | Следующая