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

2.8 Зоны переключения

Гибкость использования мобильного WiMAX обеспечивается сегментированием и созданием зон переключения.

Сегмент -- это объединение части доступных OFDMA-подканалов (в крайнем случае, один сегмент может содержать все подканалы). Один сегмент используется для установления единственного экземпляра процесса управления доступом к среде (MAC).

Зона переключения -- множество смежных OFDMA-символов «вниз» или «вверх». В каждом из них использованы одни и те же методы разделения каналов.

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

Рис. 2.6 иллюстрирует структуру зоны памяти, которая обеспечивает набор поднесущих, используемых в сотах. Соты идентифицируются с помощью идентификатора соты (ID Cell X, ID Cell Y, ID Cell Z). Идентификаторы этих сот размещаются в преамбуле. Идентификатор с номером ID Cell 0 закреплен за широковещательными соединениями. В данном случае в начале области каждой соты размещены адреса поднесущих, соответствующих принципу частичного использования, а потом адреса поднесущих, соответствующих принципу полного использования. Эти области памяти могут быть использованы в зависимости от разработанной программы.

2.9 Структура кадра TDD

Документы рассматриваемого стандарта для физического уровня IEEE 802.16е PHY предусматривают дуплексную передачу с временным разделением (TDD -- Time Division Duplex) и полудуплексную передачу по принципу «полудуплекс в частотным разделением» (HDFDD -- Half-Duplex Frequency Division Duplex).

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

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

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

- обеспечивает взаимодействие с системой антенн MIMO и другими прогрессивными технологиями антенн;

- в отличие от FDD, который требует парных каналов, принцип TDD требует только одного канала по направлениям «вверх» и «вниз», что обеспечивает лучшую адаптацию в выделяемом спектре;

- реализация приемопередатчиков для TDD менее сложна, поэтому устройства, реализующие этот принцип, дешевле.

Рис. 2.7 отображает структуру кадра для дуплекса с временным разделением. Каждый кадр включает два подкадра -- «вниз» и «вверх», разделенных промежутком передача/прием (TRG -- Transmit/Receive Guard period) и прием/передача (RTG -- Receive/Transmit Guard period) для предупреждения конфликтов.

Для нормальной работы в кадре содержится следующая информация.

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

Заголовок управления кадром (FCH--Frame Control Header): следует за преамбулой, содержит информацию о конфигурации кадра подсистемы мобильной связи, включая длину сообщения, схему кодирования, используемые подканалы.

Карты распределения информации для направлений DL-MAP и UL-MAP: содержат информацию о закреплении каналов и другую управляющую информацию для направлений «вниз» и «вверх».

Порядок расположения информации UL (ranging): данные о подканале, передаваемые по направлению «вверх», время распространения по замкнутой петле, информация для настройки частоты, управления мощностью и запросы на дополнительное расширение полосы пропускания.

UL-индикатор качества канала (CQI-- Channel Quality Indicator) предназначен для регистрации информации о состоянии канала (обратной связи). Канал, по которому передается CQI называют CQICH.

Подтверждение UL АСК: информация подтверждения сообщений, которые поступили по направлению «вниз».

Рис. 2.7. Структура кадра OFDM WiMAX при работе по принципу TDD

2.10 Контрольные вопросы

1. Как осуществляется распределение информационных потоков в системе OFDM?

2. Что называют символом в системе OFDM?

3. Для чего используется префикс при формировании ряда Фурье?

4. Как осуществляется защита от межсимвольной интерференции?

5. Каково назначение поднесущих канала OFDMA?

6. Как осуществляется наращивание пропускной способности?

7. Какова структура кластеров для четных и нечетных символов OFDM?

8. Какую операцию называют смежной перестановкой?

9. Дайте определение термину «зона переключения»?

10. Перечислите информационные блоки кадра TDD?

2.11 Проектное задание

Разработайте функциональную схему модулятора со многими несущими на основе OFDM. При этом используйте следующие параметры: ширина канала - 5 МГц; частота опроса - 5.6 МГц; размер преобразования Фурье - 512; число подканалов - 8. Выберите недостающие параметры, характерные для стандарта. Проведите анализ требований к отдельным функциональным узлам. Сформулируйте какие критерии необходимо использовать при разработке данной схемы.

Учебный модуль 3. Коды Рида-Соломона

3.1 Комплексная цель модуля

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

3.2 Общее определение

Коды Рида-Соломона (R-S code) -- это недвоичные циклические коды, символы которых представляют собой m-битовые последовательности, где m-- положительное целое число, большее 1. Коды Рида-Соломона (n, k) определены на m-битовых символах при всех n и k, для которых

Размещено на http://www.allbest.ru/

(3.1)

где k -- число информационных битов, подлежащих кодированию, а п -- число кодовых символов в кодируемом блоке. Для большинства сверточных кодов Рида-Соломона (n, k)

(3.2)

где t- количество ошибочных битов в символе, которые может исправить код, а n-k=2t -- число контрольных символов. Расширенный код Рида-Соломона можно получить при n= 2^m или n= 2^m + 1.

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

(3.3)

Код, который исправляет все искаженные символы, содержащие ошибку в t или меньшем числе бит можно выразить следующим образом:

(3.4)

Здесь означает наибольшее целое, не превышающее х. Из уравнения (3.4) видно, что коды Рида-Соломона, исправляющие t символьных ошибок, требуют не более 2t контрольных символов. Из уравнения (3.4) следует, что декодер имеет n-k "используемых" избыточных символов, количество которых вдвое превышает количество исправляемых ошибок. Для каждой ошибки один избыточный символ используется для обнаружения ошибки и один -- для определения правильного значения. Способность кода к коррекции стираний выражается следующим образом:

(3.5)

Возможность одновременной коррекции ошибок и стираний можно выразить как требование

(3.6)

Здесь -- число символьных моделей ошибки, которые можно исправить, а -- количество комбинаций символьных стираний, которые могут быть исправлены. Преимущества недвоичных кодов, подобных кодам Рида-Соломона, можно увидеть в следующем сравнении. Рассмотрим двоичный код (n, k) = (7, 3).

Общее число комбинаций 2ⁿ = 2⁷=128, из которых 2^k-2³ = 8 (или 1/16 часть всех комбинаций) являются кодовыми словами. Затем рассмотрим недвоичный код (п, к) = (7,3), где каждый символ состоит из m = 3 бит. Общее число комбинаций содержит 2^nm = 2²¹ = 2 097 152, из которых 2^km = 2⁹ = 512 (или 1/4096 часть всех комбинаций) являются кодовыми словами. Если операции производятся над недвоичными символами, каждый из которых образован т битами, то только незначительная часть (т.е. 2^km из большого числа 2^nm) возможных комбинаций является кодовыми словами. Эта часть уменьшается с ростом т. Здесь важным является то, что если в качестве кодовых слов используется незначительная часть пространства, то можно достичь большего d_min .

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

Коды Рида-Соломона эффективны для исправления пакетов ошибок, т.е. они оказываются эффективными в каналах с памятью. Также они хорошо зарекомендовали себя в каналах с большим набором входных символов. Особенностью кода Рида-Соломона является то, что к коду длины n можно добавить два информационных символа, не уменьшая при этом минимального расстояния. Такой расширенный код имеет длину n + 2 и то же количество символов контроля четности, что и исходный код. Вероятность появления ошибки в декодированном символе, Р_Е, можно записать через вероятность появления ошибки в канальном символе, р.

(3.7)

Здесь t -- количество ошибочных битов в символе, которые может исправить код, а символы содержат т битов каждый.

Для некоторых типов модуляции вероятность битовой ошибки можно ограничить сверху вероятностью символьной ошибки. Для модуляции MFSK с М = 2^m связь Р_в и Р_Е выражается формулой

(3.8)

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

Рассмотрим код (n, k) = (255,247), в котором каждый символ состоит из m = 8 бит (такие символы принято называть байтами). Поскольку n-k=8, из уравнения (3.4) можно видеть, что этот код может исправлять любые 4-символьные ошибки в блоке длиной до 255. Пусть блок длительностью 25 бит в ходе передачи поражается помехами, как показано на рис. 3.1. В этом примере пакет шума, который попадает на 25 последовательных битов, исказит точно 4 символа. Декодер для кода (255, 247) исправит любые 4-символьные ошибки без учета характера повреждений, причиненных символу. Другими словами, если декодер исправляет байт (заменяет неправильный правильным), то ошибка может быть вызвана искажением одного или всех восьми битов. Поэтому, если символ неправильный, он может быть искажен на всех двоичных позициях. Это дает коду Рида-Соломона большое преимущество при наличии импульсных помех по сравнению с двоичными кодами (даже при использовании в двоичном коде чередования).

3.3 Рабочие характеристики кода Рида-Соломона

Для того чтобы код успешно противостоял шумовым эффектам, длительность помех должна составлять относительно небольшой процент от количества кодовых слов. Чтобы быть уверенным, что так будет большую часть времени, принятый шум необходимо усреднить за большой промежуток времени, что снизит эффект от неожиданной или необычной полосы плохого приема. Следовательно, можно предвидеть, что код с коррекцией ошибок будет более эффективен (повысится надежность передачи) приувеличении размера передаваемого блока, что делает код Рида-Соломона более привлекательным, если желательна большая длина блока. Это можно оценить по семейству кривых, показанному на рис. 3.2, где степень кодирования взята равной 7/8, при этом длина блока возрастает с n = 32 символов (при т = 5 бит на символ) до n = 256 символов (при m = 8 бит на символ). Таким образом, размер блока возрастает с 160 бит до 2048 бит.

По мере увеличения избыточности кода (и снижения его степени кодирования), сложность реализации этого кода повышается (особенно для высокоскоростных устройств). При этом для систем связи реального времени должна увеличиться ширина полосы пропускания. Увеличение избыточности, например увеличение размера символа, приводит к уменьшению вероятности появления битовых ошибок, как можно видеть на рис. 3.3, где кодовая длина п равна постоянному значению 64 при снижении числа символов данных с k = 60 до k = 4 (избыточность возрастает с 4 до 60 символов).

Рис. 3.1. Блок данных, искаженный 25- битовым пакетом ошибок

Рис. 3.2. Характеристики декодера Рида-Соломона как функция размера символов (степень кодирования = 7/8)

На рис. 3.3 показана передаточная функция (выходная вероятность появления битовой ошибки, зависящая от входной вероятности появления символьной ошибки) гипотетических декодеров. Поскольку здесь не имеется в виду определенная система или канал (лишь вход-выход декодера), можно заключить, что надежность передачи является монотонной функцией избыточности и будет неуклонно возрастать с приближением степени кодирования к нулю. Однако это не так, если отношение фиксировано. По мере изменения степени кодирования кода от максимального значения до минимального (от 0 до 1), полезно было бы понаблюдать за эффектами, показанными на рис. 3.4. Здесь кривые рабочих характеристик показаны при модуляции BPSK и кодах (31, k) для разных типов каналов. На рис. 3.4 показаны системы связи реального времени, в которых за кодирование с коррекцией ошибок приходится платить расширением полосы пропускания, пропорциональным величине, равной обратной степени кодирования. Приведенные кривые показывают четкий оптимум степени кодирования, минимизирующий требуемое значение . Для гауссова канала оптимальное значение степени кодирования находится где-то между 0,6 и 0,7, для канала с райсовским замиранием -- около 0,5 (с отношением мощности прямого сигнала к мощности отраженного К = 7 дБ) и 0,3 -- для канала с релеевским замиранием.

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

Рис. 3.4. Характеристики декодера Рида-Соломона (31, k) как функция степени кодирования (модуляция BPSK)

3.4 Конечные поля

Для понимания принципов кодирования и декодирования недвоичных кодов, таких как коды Рида-Соломона, нужно ввести в понятие конечных полей, известных как поля Галуа. Для любого простого числа р существует конечное поле, которое обозначается GF(p) и содержит р элементов. Понятие GF(p) можно обобщить на поле из р^т элементов, именуемое полем расширения GF(p); это поле обозначается GF(p^m), где т -- положительное целое число. Заметим, что GF(p^m) содержит в качестве подмножества все элементы GF(p). Символы из поля расширения GF(2^m) используются при построении кодов Рида-Соломона.

Двоичное поле GF(2) является подполем поля расширения GF(2^m), точно так же как поле вещественных чисел является подполем поля комплексных чисел. Кроме чисел 0 и 1, в поле расширения существуют дополнительные однозначные элементы, которые будут представлены новым символом . Каждый ненулевой элемент в GF(2^m) можно представить как степень . Бесконечное множество элементов, F, образуется из стартового множества {0,1, } и генерируется дополнительными элементами путем последовательного умножения последней записи на .

(3.9)

Для вычисления из F конечного множества элементов GF(2^m) на F нужно наложить условия: оно может содержать только 2^т элемента и быть замкнутым относительно операции умножения. Условие замыкания множества элементов поля по отношению к операции умножения имеет вид нередуцируемого полинома

или, что то же самое, (3.10)

С помощью полиномиального ограничения любой элемент со степенью, большей или равной 2^т-1, можно следующим образом понизить до элемента со степенью, меньшей 2^т-1:

(3.11)

Таким образом, как показано ниже, уравнение (3.10) можно использовать для формирования конечной последовательности F* из бесконечной последовательности F.

(3.12)

Следовательно, из уравнения (3.12) можно видеть, что элементы конечного поля GF(2^m) даются следующим выражением:

(3.13)

Каждый из 2^т элементов конечного поля GF(2^m) можно представить как отдельный полином степени т - 1 или меньше. Степенью полинома называется степень члена максимального порядка. Обозначим каждый ненулевой элемент GF(2^m) полиномом , в котором по крайней мере m коэффициентов ненулевые. Для i- 0, 1, 2,..., 2^т-2,

(3.14)

Рассмотрим случай т = 3, в котором конечное поле обозначается GF(2³). На рис. 3.5 показано отображение семи элементов {} и нулевого элемента в слагаемые базисных элементов {Х°, Х¹, Х²}, описываемых уравнением (3.14). Поскольку из уравнения (3.10) в этом поле имеется семь ненулевых элементов или всего восемь элементов. Каждая строка на рис. 3.5 содержит последовательность двоичных величин, представляющих коэффициенты , и из уравнения (3.14). Одним из преимуществ использования элементов {} поля расширения, вместо двоичных элементов, является компактность записи, что оказывается удобным при математическом описании процессов недвоичного кодирования и декодирования. Сложение двух элементов конечного поля, следовательно, определяется как суммирование по модулю 2 всех коэффициентов при элементах одинаковых степеней.

(3.15)

Класс полиномов, называемых примитивными полиномами, интересует нас, поскольку такие объекты определяют конечные поля GF(2^m), которые, в свою очередь, нужны для описания кодов Рида-Соломона. Следующее утверждение является необходимым и достаточным условием примитивности полинома. Нередуцируемый полином f(X) порядка т будет примитивным, если наименьшим положительным целым числом п, для которого делится на f(X), будет п = 2^т- 1. Заметим, что нередуцируемый полином -- это такой полином, который нельзя представить в виде произведения полиномов меньшего порядка; делимость А на В означает, что А делится на В с нулевым остатком и ненулевым частным. Обычно полином записывают в порядке возрастания степеней. Иногда более удобным является обратный формат записи (например, при выполнении полиномиального деления).

Рис. 3.5. Отображение элементов поля в базисные элементы GF(8) с помощью f(X)=1+X+

Рассмотрим пример, в котором будут задействованы примитивный полином и конечное поле, которое он определяет. В табл. 3.1 содержатся примеры некоторых примитивных полиномов. Мы выберем первый из указанных там полиномов, f(X)=1+X+, который определяет конечное поле GF(2^m), где степень полинома т=3. Таким образом, в поле, определяемом полиномом f(X), имеется 2^т = 2³ = 8 элементов. Поиск корней полинома f(X) -- это поиск таких значений X, при которых f(X) = 0. Привычные нам двоичные элементы 0 и 1 не подходят полиному f(X)=1+X+(они не являются корнями), поскольку f(1) = 1 и f(0) = 1 (в рамках операций по модулю 2). Кроме того, основная теорема алгебры утверждает, что полином порядка т должен иметь в точности т корней. Следовательно, в этом примере выражение f(X) = 0 должно иметь 3 корня. Возникает определенная проблема, поскольку 3 корня не лежат в том же конечном поле, что и коэффициенты f(X). А если они находятся где-то еще, то, наверняка, в поле расширения GF(2³). Пусть , элемент поля расширения, определяется как корень полинома f(X). Следовательно, можно записать следующее:

(3.16)

Поскольку при операциях над двоичным полем +1=-1, то можно представить следующим образом:

(3.17)

Таблица 3.1. Некоторые примитивные полиномы

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

(3.18)

А теперь взглянем на следующий случай:

(3.19)

Из уравнений (3.17) и (3.18) получаем следующее:

(3.20)

Используя уравнение (3.20), получаем следующее:

(3.21)

А теперь из уравнения (3.21) вычисляем

(3.22)

Заметим, что и, следовательно, восемью элементами конечного поля GF(2³) будут

(3.23)

Отображение элементов поля в базисные элементы, которое описывается уравнением (3.14), можно проиллюстрировать с помощью схемы линейного регистра сдвига с обратной связью (рис. 3.6). Схема генерирует (при т = 3) 2^т-1 ненулевых элементов поля и, таким образом, обобщает процедуры, описанные в уравнениях (3.17)--(3.23). Следует отметить, что показанная на рис. 3.6 обратная связь соответствует коэффициентам полинома f(X) = 1 + X + X³, как и в случае двоичных циклических кодов. Пусть вначале схема находится в некотором состоянии, например 100; при выполнении правого сдвига на один такт можно убедиться, что каждый из элементов поля (за исключением нулевого), показанных на рис. 3.5, циклически будет появляться в разрядах регистра сдвига. На данном конечном поле GF(2³) можно определить две арифметические операции -- сложение и умножение. В табл. 3.2 показана операция сложения, а в табл. 3.3 -- операция умножения, но только для ненулевых элементов. Правила суммирования следуют из уравнений (3.17) и (3.22); и их можно доказать, обратившись к рис. 3.5, поскольку сумму двух элементов поля можно рассчитать путем сложения (по модулю 2) соответствующих коэффициентов их базисных элементов. Правила умножения, указанные в табл. 3.3, следуют из обычной процедуры, в которой произведение элементов поля вычисляется путем сложения по модулю (2^т -1) их показателей степеней или, для данного случая, по модулю 7.

Рис. 3.6. Отображение элементов поля в базисные элементы можно представить с помощью схемы линейного регистра сдвига с обратной связью

Таблица 3.2. Таблица сложения для GF(8) приДХ) = 1 +Х + Х³

Таблица 3.3. Таблица умножения для GF(8) приДХ) = 1 +Х + Х³

3.5 Кодирование Рида-Соломона

В уравнении (3.2) представлена наиболее распространенная форма кодов Рида-Соломона через параметры n, k, t и некоторое положительное число т > 2. Приведем это уравнение повторно:

(3.24)

Здесь n-k=2t-- число контрольных символов, а t - количество ошибочных битов в символе, которые может исправить код. Генерирующий полином для кода Рида-Соломона имеет следующий вид:

(3.25)

Степень полиномиального генератора равна числу контрольных символов. Связь между степенью полиномиального генератора и числом контрольных символов, не является неожиданной. Поскольку полиномиальный генератор имеет порядок 2t, мы должны иметь в точности 2t последовательные степени , которые являются корнями полинома. Обозначим корни g(X) как: , , ..., . Нет необходимости начинать именно с корня , это можно сделать с помощью любой степени . Возьмем к примеру код (7, 3) с возможностью коррекции двухсимвольных ошибок. Мы выразим полиномиальный генератор через 2t = п - к = 4 корня следующим образом:

Поменяв порядок расположения членов полинома на обратный и заменив знаки "минус" на "плюс", так как над двоичным полем +1 =-1, генератор g(X) можно будет представить следующим образом:

(3.26)

Так как код Рида-Соломона является циклическим, кодирование в систематической форме аналогично процедуре двоичного кодирования. Мы можем осуществить сдвиг полинома сообщения т(Х) в крайние правые к разряды регистра кодового слова и произвести последующее прибавление полинома четности р(Х) в крайние левые п-к разряды. Поэтому мы умножаем т(Х) на X^n-k, проделав алгебраическую операцию таким образом, что m(Х) оказывается сдвинутым вправо на n-k позиций. Далее мы делим X^n-k m(X) на полиномиальный генератор g(X), что можно записать следующим образом:

(3.27)

Здесь q(X) и р(Х) -- это частное и остаток от полиномиального деления. Как и в случае двоичного кодирования, остаток будет четным. Уравнение (3.27) можно переписать следующим образом:

Результирующий полином кодового слова U(X), можно переписать следующим образом:

(3.28)

Продемонстрируем шаги, подразумеваемые уравнениями (3.27) и (3.28), закодировав сообщение из трех символов с помощью кода Рида-Соломона (7, 3), генератор которого определяется уравнением (3.26). Сначала мы умножаем (сдвиг вверх) полином сообщения на , что дает . Далее мы делим такой сдвинутый вверх полином сообщения на полиномиальный генератор из уравнения (3.26), . Полиномиальное деление даст в результате следующий полиномиальный остаток (полином четности):

Затем, из уравнения (3.28), полином кодового слова можно записать следующим образом:

Как показано на рис. 3.7, кодирование последовательности из 3 символов в систематической форме на основе кода Рида-Соломона (7, 3), определяемого генератором g(X) из уравнения (3.26), требует реализации регистра LFSR. Нетрудно убедиться, что элементы умножителя на рис. 3.7, взятые справа налево, соответствуют коэффициентам полинома в уравнении (3.26). Этот процесс кодирования является недвоичным аналогом циклического кодирования. Здесь, в соответствии с уравнением (3.24), ненулевые кодовые слова образованы 2^т- 1 = 7 символами, и каждый символ состоит из т = 3 бит.

Рис. 3.7. Кодер LFSR для кода (7, 3)

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

Переключатель I в течение первых к тактовых импульсов закрыт, для того чтобы подавать символы сообщения в (n - k) -разрядный регистр сдвига.

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

После передачи k-го символа на регистр выхода, переключатель 1 открывается, а переключатель 2 переходит в верхнее положение.

Остальные (п - к) тактовых импульсов очищают контрольные символы, содержащиеся в регистре, подавая их на регистр выхода.

Общее число тактовых импульсов равно п, и содержимое регистра выхода является полиномом кодового слова p(X) + m(X), где р(Х) представляет собой кодовые символы, а т(Х) -- символы сообщения в полиномиальной форме.

Для проверки возьмем ту же последовательность символов . Здесь крайний правый символ является самым первым и крайний правый бит также является самым первым. Последовательность действий в течение первых к = 3 сдвигов в цепи кодирования на рис. 3.7 будет иметь следующий вид.

Как можно видеть, после третьего такта регистр содержит 4 контрольных символа, а⁰, а², а⁴ и а⁶. Затем переключатель 1 переходит в верхнее положение, и контрольные символы, содержащиеся в регистре, подаются на выход. Поэтому выходное кодовое слово, записанное в полиномиальной форме, можно представить в следующем виде:

(3.29)

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

Корни полиномиального генератора g(X) должны быть и корнями кодового слова, генерируемого g(X), поскольку правильное кодовое слово имеет следующий вид:

 (3.30)

Следовательно, произвольное кодовое слово, выражаемое через корень генератора g(X), должно давать нуль. Представляется интересным, действительно ли полином кодового слова в уравнении (3.29) дает нуль, когда он выражается через какой-либо из четырех корней g(X). Иными словами, это означает проверку следующего:

Независимо выполнив вычисления для разных корней, получим следующее:

Эти вычисления показывают, что, как и ожидалось, кодовое слово, выражаемое через любой корень генератора g(X), должно давать нуль.

3.6 Декодирование Рида-Соломона

В разделе 3.5. тестовое сообщение кодируется в систематической форме с помощью кода Рида-Соломона (7, 3), что дает в результате полином кодового слова, описываемый уравнением (3.29). Допустим, что в ходе передачи это кодовое слово подверглось искажению: 2 символа были приняты с ошибкой. (Такое количество ошибок соответствует максимальной способности кода к коррекции ошибок.) При использовании 7-символьного кодового слова модель ошибки можно представить в полиномиальной форме следующим образом:

(3.31)

Пусть двухсимвольная ошибка будет такой, что

(3.32)

Другими словами, контрольный символ искажен 1-битовой ошибкой (представленной как ), а символ сообщения -- 3-битовой ошибкой (представленной как ). В данном случае принятый полином поврежденного кодового слова r(Х) представляется в виде суммы полинома переданного кодового слова и полинома модели ошибки, как показано ниже.

(3.33)

Следуя уравнению (3.33), мы суммируем U(X) из уравнения (3.29) и е(Х) из уравнения (3.32) и имеем следующее:

(3.34)

В данном примере исправления 2-символьной ошибки имеется четыре неизвестных -- два относятся к расположению ошибки, а два касаются ошибочных значений. Отметим важное различие между недвоичным декодированием r(Х), которое мы показали в уравнении (3.34), и двоичным. При двоичном декодировании декодеру нужно знать лишь расположение ошибки. Если известно, где находится ошибка, бит нужно поменять с 1 на 0 или наоборот. Но здесь недвоичные символы требуют, чтобы мы не только узнали расположение ошибки, но и определили правильное значение символа, расположенного на этой позиции. Поскольку в данном примере у нас имеется четыре неизвестных, нам нужно четыре уравнения, чтобы найти их.

Cиндром -- это результат проверки четности, выполняемой над r, чтобы определить, принадлежит ли r набору кодовых слов. Если r является членом набора, то синдром S имеет значение, равное 0. Любое ненулевое значение S означает наличие ошибок. Точно так же, как и в двоичном случае, синдром S состоит из п - к символов, {Si} (i = 1, ..., п - к). Таким образом, для нашего кода (7, 3) имеется по четыре символа в каждом векторе синдрома; их значения можно рассчитать из принятого полинома r(Х). Заметим, как облегчаются вычисления благодаря самой структуре кода, определяемой уравнением (3.30).

Из этой структуры можно видеть, что каждый правильный полином кодового слова U(X) является кратным полиномиальному генератору g(Х). Следовательно, корни g(X) также должны быть корнями U(X). Поскольку г(Х) = U(X) - е(Х), то r(Х), вычисляемый с каждым корнем g(X), должен давать нуль, только если т(Х) будет правильным кодовым словом. Любые ошибки приведут в итоге к ненулевому результату в одном (или более) случае. Вычисления символов синдрома можно записать следующим образом:

(3.35)

Здесь, как было показано в уравнении (3.32), r(Х) содержит 2-символьные ошибки. Если r(Х) окажется правильным кодовым словом, то это приведет к тому, что все символы синдрома S, будут равны нулю. В данном примере четыре символа синдрома находятся следующим образом:

(3.36)

(3.37)

(3.38)

(3.39)

Результат подтверждает, что принятое кодовое слово содержит ошибку (введенную нами), поскольку S 0.

Допустим, в кодовом слове имеется ошибок, расположенных на позициях

Х^j1, Х^j2 ..., Х^j . Тогда полином ошибок, определяемый уравнениями (3.31) и (3.32), можно записать следующим образом:

(3.40)

Индексы 1, 2, ..., обозначают 1-ю, 2-ю, ..., -ю ошибки, а индекс j -- расположение ошибки. Для коррекции искаженного кодового слова нужно определить каждое значение ошибки е_j и ее расположение X^Jl, где l= 1, 2, ..., . Обозначим номер локатора ошибки как . Далее вычисляем n - k=2t символа синдрома, подставляя в принятый полином при i = 1,2, ..., 2t.

(3.41)

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

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

(3.42)

Корнями будут 1/, l/, …, l/. Величины, обратные корням , будут представлять номера расположений моделей ошибки е(Х). Тогда, воспользовавшись авторегрессионной техникой моделирования, составим из синдромов матрицу, в которой первые t синдромов будут использоваться для предсказания следующего синдрома:

(3.43)

Мы воспользовались авторегрессионной моделью уравнения (3.43), взяв матрицу наибольшей размерности с ненулевым определителем. Для кода (7, 3) с коррекцией двухсимвольных ошибок матрица будет иметь размерность 2 х 2, и модель запишется следующим образом:

(3.44)

(3.45)

Чтобы найти коэффициенты и полинома локатора ошибок , сначала необходимо вычислить обратную матрицу для уравнения (3.45). Обратная матрица для матрицы [А] определяется следующим образом:

Следовательно,

(3.46)

(3.47)

(3.48)

Проверка надежности

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

(3.49)

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

(3.50)

Из уравнений (3.42) и (3.50)

(3.51)

Корни являются обратными числами к положениям ошибок. После того как эти корни найдены, мы знаем расположение ошибок. Вообще, корни могут быть одним или несколькими элементами поля. Определим эти корни путем полной проверки полинома со всеми элементами поля, как будет показано ниже. Любой элемент X, который дает = 0, является корнем, что позволяет нам определить расположение ошибки.

Как видно из уравнения (3.42), расположение ошибок является обратной величиной к корням полинома. А значит, означает, что один корень получается при 1/= . Отсюда . Аналогично означает, что другой корень появляется при , где (в данном примере) l и l' обозначают 1-ю и 2-ю ошибки. Поскольку мы имеем дело с 2-символьными ошибками, полином ошибок можно записать следующим образом:

(3.52)

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

Мы обозначили ошибки e_Jl, где индексу обозначает расположение ошибки, а индекс l - l -ю ошибку. Поскольку каждое значение ошибки связано с конкретным месторасположением, систему обозначений можно упростить, обозначив е_jl просто как e_l.Теперь, приготовившись к нахождению значений ошибок е₁ и е₂, связанных с позициями и , можно использовать любое из четырех синдромных уравнений. Выразим из уравнения (3.41) S₁ и S₂.

(3.53)

Эти уравнения можно переписать в матричной форме следующим образом:

(3.55)

Чтобы найти значения ошибок е₁ и е₂ нужно определить обратную матрицу для уравнения (3.55).

(3.56)

Теперь мы можем найти из уравнения (3.55) значения ошибок.

(3.57)

Из уравнений (3.52) и (3.57) мы находим полином ошибок.

(3.58)

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

(3.59)

(3.6

Поскольку символы сообщения содержатся в крайних правых к = 3 символах, декодированным будет следующее сообщение:

Это сообщение в точности соответствует тому, которое было выбрано для этого примера.

3.7 Контрольные вопросы

1. Какие коды называют недвоичными циклическими кодами?

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

3. От каких параметров зависят рабочие характеристики кода Рида-Соломона?

4. Почему при малой степени кодирования число ошибок увеличивается?

5. Дайте определение поля Галуа?

6. Дайте определение нередуцируемому полиному?

7. Чем отличается операция над элементами поля Галуа по сравнению с операциями над обычными степенными полиномами?

8. Каков принцип образования кода Рида-Соломона?

9. Каковы основные шаги кодирования?

10. В чем особенности алгоритма декодирования?

11. От чего зависит сложность алгоритмов декодирования?

3.8 Проектное задание

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

Список литературы

Основная

1. Берлин А.Н. Цифровые сотовые системы связи. -М. : Эко-Треидз, 2007 -296 с.

2. Скляр Б. Цифровая связь. -М. : Издательский дом «Вильямс», 2003 -1104 с.

3. Григорьев В.А. и др. Сети и системы радиодоступа -М. :Эко-Трейдз, 2005 -384 с.

4. Гармонов А.В. и др. Технический обзор стандарта 802.16 // Мобильные системы, 2005, №11.

Дополнительная

5. Галкин В.А. Цифровая мобильная радиосвязь. -М. :Горячая линия - Телеком, 2007 -432 с.

6. Зюко А.Г. и др. Теория электрической связи. -М: Радио и связь,1999 -433 с.

7. Прокис Дж. Цифровая связь. -М. :Радио и связь, 2000 -797 с.

8. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. -М. :Техносфера, 2006 -320 с.

Размещено на Allbest.ru

...