Сверточные коды. 4 Дисер с 15 СК и Мягкое дек с 55. Программноаппаратная реализация оптимального алгоритма декодирования каскадных кодов на базе кодов рида соломона в адаптивных системах обмена данными
 Скачать 5.5 Mb.
|
Обоснованность и достоверность результатов работыРезультаты работы базируются на использовании научных положений и методов исследования, апробации созданного программно-аппаратного комплекса и подтверждаются соответствием результатов теоретических и экспериментальных исследований. Апробация работыОсновные результаты диссертационной работы докладывались на Международной конференции «Радиоэлектронные устройства и системы для инфокоммуникационных технологий» REDS, (г. Москва, 2013г., 2015г.), ХX Международной научно-технической конференции «Радиолокация. Навигация. Связь», (г. Воронеж, 2014г.), 17-ой Международной конференции «Цифровая обработка сигналов и еѐ применение» DSPA (г. Москва, 2015г.), Международной научно-технической конференции «RLNC» (г. Воронеж, 2015г., 2016г.). Результаты работы опубликованы в 17 печатных трудах, в числе которых 4 статьи в журналах, входящих в перечень ВАК, 1 патент РФ на изобретение, 12 трудов и тезисов докладов на Международных и Всероссийских научно-технических и научно-практических конференциях. Реализация результатов работыМатериалы диссертации были использованы: При выполнении ОКР «Каскад 1» (2010-2011 гг.) и НИР «Каскад 2» (2012-2013 гг.). Результаты работы используются в разработках ФНПЦ АО «НПО «Марс» для создания широкополосного помехоустойчивого канала связи в изделиях проекта «Трасса-22350». При внедрении в учебный процесс в Ульяновском государственном техническом университете по направлению 11.03.02 в курсах «Общая теория связи 2» и «Теория кодирования и защиты информации». Личный вклад автораАвтору работы принадлежат разработка и программно-аппаратная реализация алгоритма поиска полинома локаторов ошибок для адаптивных декодеров кодов РС. Диссертант участвовал в проведении лабораторных и натурных испытаний разработанной АСК. В совместных работах автор участвовал в рассуждениях, выводе аналитических соотношений, проведении расчетов, составлении математических моделей и проведении имитационных испытаний с ними. Структура и объем работыДиссертация состоит из введения, четырех глав, заключения, списка литературы и приложений, содержит 139 страниц машинописного текста, в том числе 68 иллюстраций и 8 таблиц. Список литературы включает в себя 127 наименований. В приложениях к диссертации представлены листинги программ имитационных моделей рассматриваемых систем передачи данных (СПД), листинги аппаратной реализации модулей, входящие в состав кодека, описание изобретения, а также акты внедрения результатов работы. ГЛАВА 1.ПРИМЕНЕНИЕ СРЕДСТВ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ В ИНФОКОММУНИКАЦИОННЫХ СИСТЕМАХ Современные методы помехоустойчивого кодированияСовременные методы помехоустойчивого кодирования складываются из трех основных направлений: блоковые коды, непрерывные или сверточные коды, полярные коды, а также их различные комбинации [93, 94, 103, 108]. Рассматриваемая классификация избыточных кодов в соответствии с их конструктивными свойствами представлена на рисунке 1.1. Рисунок 1.1 – Классификация основных направлений развития систем избыточного кодирования Блоковыекоды Блоковые коды – это класс помехоустойчивых кодов, которые можно описать парой чисел (n, k). В процессе кодирования блок из k символов сообщения преобразуется в больший блок из n символов кодового слова, образованного с использованием элементов данного алфавита. Если алфавит состоит только из двух элементов (0 и 1), код является двоичным и включает только двоичные разряды. В таком коде всегда можно указать начало и конец кодовой комбинации [85, 86]. Это свойство полезно в системе с переспросами и при пороговом декодировании [104, 109, 111]. Данные коды в наибольшей степени приспособлены для адаптивных систем [36]. Наиболее простым способом преобразования k информационных символов в n-мерный кодовый блок является обращение к таблице соответствий, в которой каждому набору информационных слов соответствует единственный набор из n кодовых слов. Однако при построении кодов с длинными блоками, например, кода (127, 92), построение таблицы соответствия становится слишком трудоемкой процедурой, а ее хранение в памяти кодека требует существенных аппаратных затрат. В этом случае, более эффективным методом кодирования является использование так называемой порождающей матрицы G[38].
где Vi– вектор кодового пространства, vij– компоненты этого вектора. В матричном виде генерация кодового слова примет вид:
где m – информационный вектор. Таким образом, порождающая матрица G полностью определяет кодовый вектор, при этом кодеру необходимо хранить только ее компоненты, что существенно экономит объем памяти устройства. При декодировании принятого кодового вектора, как правило, используют проверочную матрицу H. Для каждой порождающей матрицы (k × n) существует матрица H размером (n – k) × n, такая, что строки матрицы G ортогональны к строкам матрицы H [115]. Иными словами, G∙HT= 0. Представим порождающую матрицу в систематическом виде:
где P – массив четности, входящий в состав порождающей матрицы, Ik– единичная матрица, размерностью (k × k). Чтобы матрица H удовлетворяла требованиям ортогональности систематического кода, ее компоненты записываются в следующем виде:
Поскольку проверочная матрица H создана так, чтобы удовлетворять условиям ортогональности, она позволяет проверять принятые векторы на предмет их принадлежности заданному набору кодовых слов [115]. U будет кодовым словом, генерируемым матрицей G, тогда и только тогда, когда выполняется равенство:
Для определения характера ошибки в принятом векторе R необходимо вычислить синдром S. Предположим, что из канала связи поступил вектор R, содержащий ошибки:
где e – вектор ошибки, внесенной каналом связи. Тогда синдром принятого сигнала будет определяться следующим образом:
При отсутствии ошибок в принятом векторе, то есть при e = 0 R = U, синдром равен нулю. В противном случае, если S ≠ 0, переданный вектор был искажен в канале связи, а значение синдрома S позволит установить характер этого искажения. Зная характер ошибки, декодер пытается ее локализовать и исправить, либо, если его мощности недостаточно для этого, он посылает запрос на перевыдачу этого сообщения [32, 89]. Используя уравнения (1.6) и (1.7), можно представить синдром S в следующем виде [24]:
Согласно выражению (1.5) произведение кодового вектора и проверочной матрицы равно нулю, получим выражение:
Уравнение (1.9) дает взаимно однозначное соответствие между синдромным вектором S и вектором ошибки e. Зная значение вектора ошибки e, достаточно вычесть (эквивалентно сложению для двоичных символов) его из принятого вектора R, таким образом, ошибка будет исправлена [55]. Рассмотренный синдромный подход к декодированию блоковых кодов является обобщенным способом, и для декодирования некоторых кодов описанных действий будет недостаточно [112]. Так при декодировании недвоичных кодов, таких как, например, кодов Рида – Соломона, синдром позволит только локализовать ошибку, а для ее исправления потребуется вовлечение дополнительного математического аппарата [12, 113, 122]. Непрерывные (сверточные)коды Непрерывные или сверточные коды, в отличие от блоковых кодов, используют последовательную обработку информации короткими фрагментами. Такие коды обладают памятью, то есть символы на выходе такого кодера зависят не только от очередного символа на входе, но и от ранее поступивших символов, хранящихся в памяти устройства [110]. Сверточный код образуется множеством всех двоичных последовательностей, порождаемых сверточным кодером. Теоретически эти последовательности бесконечны, однако, на практике, состояние сверточного кодера периодически устанавливается в некоторое заранее известное состояние и, следовательно, порождаемый код приобретает характер блокового кода [110]. Работу кодера можно описать с помощью конечного автомата. Состояния такого автомата, на примере кода (7, 5), показаны на рисунке 1.2.
Сам кодер представляет собой сдвиговый регистр, входы которого объединены между собой определенным образом. Физические связи кодера определяются выбранными порождающими полиномами. Для рассматриваемого примера эти полиномы равны g0 = 7 ( 1 1 1 ), g1 = 5 ( 1 0 1 ). Схема кодера представлена на рисунке 1.3. В общем случае, сверточный кодер скорости k/n использует k регистров сдвига, по одному на каждый вводимый в кодер информационный символ, и n логических элементов, выполняющих операцию исключающего ИЛИ над содержимым регистров и символами на входе кодера. На практике, обычно рассматриваются только двоичные сверточные коды, то есть коды скоростью 1/n. Их параметры записывают в виде n порождающих полиномов, записанных в восьмеричном виде ( g0 , … , g1 ). Рисунок 1.3 – Структурная схема сверточного кодера (7, 5) Общая длина регистров сдвигов m называется памятью кода. Кодовое ограничение определяется как число информационных символов на входе кодера, которые влияют на кодовые символы на его выходе. Для кодеров скорости 1/2 оно равно K = m + 1. Сверточный кодер является линейной постоянной во времени системой, импульсной отклик которой задан порождающими полиномами. С помощью этих полиномов можно записать выходную последовательность кодера в следующем виде [56]:
где 0 ≤ j < n. Выходные последовательности v (j) равны дискретной свертке входной последовательности u с порождающими полиномами g0 , … , gn-1. Динамическая структура сверточного кодера позволяет развернуть во времени его диаграмму состояний и построить решетчатую диаграмму (треллис). Треллис строится следующим образом: в соответствии с диаграммой состояний кодера (рисунок 1.2) на каждом временном интервале соединяются ребрами состояния на i-ом и (i+1)-ом тактах. При этом, если на i-ом такте кодеру на вход поступает 1, то такое ребро на треллисе будет показано пунктирной линией, а при поступлении 0 – сплошной. Таким образом, при сверточном кодировании на решетчатой диаграмме формируется некий путь, по которому однозначно определяется кодовая комбинация. Построение треллис-диаграммы удобнее всего проиллюстрировать на конкретном примере. Положим, что на вход рассматриваемого сверточного кодера (7, 5) поступают символы u = (110100). Треллис данного кодера представлен на рисунке 1.4. В нижней части рисунка показана входная информационная последовательность, а в верхней – сформированный код. Кодовая комбинация строится в виде непрерывного пути, который выделен на этой диаграмме жирными линиями. Из рисунка видно, что кодер сформировал на решетке выходную последовательность v = (111010000111). Воспользовавшись формулой (1.10), нетрудно убедиться, в том, что полученная при помощи этой решетки комбинация верна.
Решетка сверточного кода имеет регулярную структуру. Повторяемость ее секций может быть эффективно использована при построении декодера. Наиболее распространенным методом декодирования сверточных кодов является алгоритм Витерби. Он применяется также для решения таких эквивалентных по сложности задач, как восстановление последовательностей по максимуму правдоподобия или прием сигналов в каналах с частичным откликом. Укороченные циклическиекоды Циклические коды составляют класс кодов, исправляющих ошибки, кодирование и декодирование которых основано на полиноминальном представлении. Простая реализация этих кодов использует регистры сдвига и логические схемы. Их свойства делают их удобными в аппаратной реализации. Одним из распространенных циклических кодов является код РС [42Ошибка! Источник ссылки не найден.]. Обозначим как C некий двоичный циклический код (n, k), u – информационное сообщение, v – соответствующее ему кодовое слово. Представить кодовый вектор v можно в полиноминальном виде:
Переменная x служит индикатором относительного положения элемента viв кодовом слове в виде монома vixiполинома v(x). Линейный код C является циклическим, если циклический сдвиг любого слова из кодового пространства C дает слово из этого же кодового пространства. В полиноминальном виде циклический сдвиг на одну позицию, обозначенный v (1) (x), соответствует умножению на x по модулю (xn– 1),
Существует множество практических задач, в которых требуются коды, исправляющие ошибки, с простыми процедурами кодирования и декодирования. Однако существующие конструкции не всегда имеют нужную длину, размерность и минимальное расстояние. Например, требуется спроектировать кодек на основе циклического, длина которого не является числом вида 2m– 1. Одним из возможных подходов является укорочение существующего циклического кода до нужного размера. Укорочение сводится к отбрасыванию информационных позиций исходного кода. Пусть S – число неиспользуемых отброшенных символов, которое называют глубиной укорочения, C – исходный циклический (n, k, d) код. Укороченное сообщение получается за счет фиксированной установки нулевых значений в некоторых информационных позициях. Остальные k - s позиций могут принимать произвольные значения. Без потери сущности, можно считать, что старшие позиции сообщения устанавливаются в нулевые состояния. Тогда информационная последовательность ux u ux ... u xk 1s преобразуется в кодовую комбинацию вида: 0 1 k1s
степень которого не превышает n – s – 1. Таким образом, укороченный код Csявляется линейным (n – s, k – s, ds) кодом с кодовым расстоянием ds≥ d. В общем случае укороченный код не является циклическим кодом. Фундаментальное свойство укороченных циклических кодов Csсостоит в том, что для их обработки могут быть использованы те же самые кодеры и декодеры. Для компьютерного моделирования гораздо проще дополнять слова нулями на старших позициях и использовать те же самые алгоритмы кодирования и декодирования, рассмотренные в этой главе. Этот способ широко используется в аппаратной реализации кодов РС. Очевидно, что нули на старших позициях сообщения не должны включаться в кодовое слово. Кроме того, декодер модифицируется таким образом, что принятое слово r(x) умножается на xn-k+sвместо умножения на xn-kпо модулю g(x) в обычном декодере. Укороченные конструкции также прекрасно подходят для реализации адаптивных кодеков. Адаптивные системы передачиданных Проблема повышения эффективности функционирования сложных систем, к которым относятся и адаптивные системы помехоустойчивого кодирования, тесно связана с обеспечением заданного уровня их качественных показателей в условиях воздействия дестабилизирующих факторов, преднамеренных и непреднамеренных помех. На этапе разработки систем передачи данных бывает сложно предсказать параметры помехоустойчивых кодов, сложно предусмотреть все возможные режимы работы системы, так как роль мешающих факторов может изменяться от сеанса к сеансу. Заданный уровень качества функционирования систем передачи данных может быть достигнут только на основе адаптивного подхода. Именно этим объясняется внедрение в современные мобильные системы связи адаптивных средств помехоустойчивого кодирования. Данные технологии призваны увеличить пиковую скорость передачи трафика, среднюю скорость передачи данных и пропускную способность канала связи в широкополосных беспроводных сетях, прежде всего, в тех условиях работы, для которых не обеспечивается прямая видимость между абонентами. При этом АСК, в которых изменению подлежат значения определенных параметров кодека, называют самонастраивающимися, а АСК, в которых изменяются алгоритмы работы кодеков, называют самоорганизующимися. Под адаптивностью системы следует понимать такой уровень ее организации, который характеризуется наличием не только обратных связей, но и устройств наблюдения, измерения и анализа, идентификации и управления, обеспечивающих возможность принимать решения на основании аналитических построений [120Ошибка! Источник ссылки не найден.]. С технической точки зрения, адаптация – это высшая степень автоматизации процесса управления. С математической точки зрения, адаптивные системы должны иметь возможность осуществлять прогноз качества функционирования и поддерживать его на заданном уровне в течение определенного временного интервала. Адаптация является частным случаем управления и заключается в изменении управляемого фактора U таким образом, чтобы поддерживать некие заданные функционалы объекта в требуемом состоянии независимо от действия всякого рода внешних и внутренних воздействий. При этом специфика объекта накладывает на управление требование:
где S – множество допустимых управлений. Структура этого множества определяется двумя факторами – целевыми ограничениями Zʹ и самим объектом. В данном случае нас будет интересовать специфика объекта, так как именно она через структуру множества определяет тип адаптации. Исходя из этого, можно классифицировать различные типы адаптации. Если объект таков, что его изменение в процессе адаптации удобно осуществлять с помощью параметров u1 , … , un, т. е.
то такую адаптацию называют параметрической.В этом случае каждый параметр ui может принимать бесконечное или конечное число значений. В первом случае U S Rqт. е. множество Sявляется континуумом, во втором – U S = D, где D – дискретное множество значений управления U. Однако очень часто адаптацию объекта удобно осуществлять не путем изменения его параметров, а модификацией его структуры, то есть, вводя структурную адаптацию. Для этого фактор управления U представляется в виде пары:
где W – структурные факторы, с помощью которых можно изменять структуру объекта адаптации, a C = ( c1 , … , ck) – адаптируемые параметры объекта (параметры (1.15), с помощью которых реализуется параметрическая адаптация). Целенаправленная вариация структурных факторов дает возможность адаптировать структуру объекта. Такая декомпозиция управления U на структурные W и параметрические C факторы позволяет более эффективно решать задачи адаптации сложных объектов, для которых параметрическая адаптация малоэффективна [102, 120]. Задачу адаптации можно записать в следующем виде:
где EW– множество допустимых структур W; ECW– множество допустимых параметров C, соответствующих структуре, определяемой W; Wʹ– оптимальная структура; Cw – оптимальные параметры этой структуры. Так как W однозначно определяет структуру объекта, то W можно условно называть структурой. Очевидно, что:
то есть множество S допустимых управлений при адаптации образуется как произведение множеств допустимых структур EWи параметров ECWэтих структур. Блок-схема решения задачи (1.17) показана на рисунке 1.5, из которого хорошо виден иерархический характер адаптации.
На верхнем уровне производится адаптация структуры W, а на нижнем – параметров C этой структуры. Очевидно, что эти два контура адаптации работают в разных временных режимах: темп параметрической адаптации (контур 2 на рисунке 1.5) значительно выше темпа структурной (контур 1). Действительно, на каждый шаг структурных изменений объекта должен приходиться весь цикл параметрической адаптации, иначе не выявится полностью эффективность реализованной структуры. Очевидно, что методы решения задач структурной и параметрической адаптации различны, что и заставляет обращаться к такой дифференциации. На рисунке 1.6 показана схема классификации различных типов адаптации.
Прежде всего, структурную адаптацию удобно подразделить на альтернативную и эволюционную. Альтернативная адаптация отличается тем, что множество допустимых структур EW невелико и содержит 2-5 альтернативных структур. Эволюционная адаптация моделирует процесс биологической эволюции. Этот алгоритм отличается введением незначительных вариаций структуры δW, моделирующих случайные мутации, которые также незначительно изменяют эффективность Q адаптируемого объекта. «Мутации» структуры δW и правило отбора, позволяющее выявлять ее благоприятные вариации, и образуют механизм эволюции, с помощью которого строится последовательность улучшающихся структур:
обладающих свойством смысл: Wn Wn1 (n = 1, 2, …), где знак предпочтения имеет
Заметим, что иногда допустимы нарушения соотношения (1.20), например, в случае, когда вариацией структуры Wiне удается получить лучшую, чем Wi, по критерию (1.20). Тогда выбирают лучшую из «мутированных» структур, что нарушает (1.20), но обеспечивает процедуре эволюции глобальные свойства, очень ценные в задачах структурной адаптации. Очевидно, что такой новый тип адаптации, как структурная, требует разработки новых подходов к решению задач. Однако не следует забывать, что существует мощный аппарат параметрической адаптации, который можно использовать и для решения задач структурной. Для этого достаточно параметризовать структуру адаптируемого объекта. |