Содержание к диссертации
Введение
Глава 1. Применение помехоустойчивого кодирования в системах цифрового телевидения 15
1.1 Цифровые технологии 15
1.2 Структурная схема системы передачи цифровой информации 17
1.3 Модель каналов связи 19
1.4 Виды модуляции 22
1.5 Характеристики методов помехоустойчивого кодирования 23
1.6 Классификация помехоустойчивых кодов 24
1.7 Методы коррекции ошибок в системах цифрового телевидения 29
1.8 Проблемы в области помехоустойчивого кодирования 31
1.9 Многопороговый декодер 34
1.10 Проблематика использования многопорогового декодера 38
1.11 Выводы по первой главе 40
Глава 2. Разработка метода оценивания эффективности работы многопороговых декодеров 41
2.1 Анализ работы МПД 41
2.2 Проблема получения оценок эффективности многопорогового декодера 48
2.3 Комбинированный имитационно-аналитический метод оценки вероятности ошибки в системе передачи цифровой информации с многопороговым декодером 53
2.3.1 Концепция комбинированного имитационно-аналитического метода 53
2.3.2 Адаптация комбинированного имитационно-аналитического метода для сверточного кода 62
2.4 Выводы по второй главе 64
Глава 3. Разработка алгоритмов повышения эффективности работы многопороговых декодеров 65
3.1 Уменьшение вероятности ошибки в области оптимального декодирования самоортогонального кода 65
3.2 Применение многопороговых декодеров в системах с адаптивным кодированием 71
3.2.1 Алгоритм организации адаптивного кодирования для повышения эффективности использования систем передачи информации 71
3.2.2 Алгоритм для оценивания отношения сигнал-шум в канале связи
3.3 Выводы по третьей главе 81
Глава 4. Разработка модели системы передачи информации с многопороговым декодированием с использованием массивно-параллельных вычислений 82
4.1 Пути увеличения скорости моделирования 82
4.2 Поиск путей получения вычислительной мощности персонального компьютера 84
4.3 Технология OpenCL 87
4.4 Моделирование системы передачи информации с использованием вычислительных ресурсов графического процессора
4.4.1 Порядок вычислений в рабочей группе 94
4.4.2 Порядок доступа к памяти 97
4.4.3 Результаты моделирования
4.4.4 Анализ объема исполняемых операций на графическом процессоре 100
4.4.5 Общие вычислительные затраты системы 107
4.4.6 Уменьшение вычислительных затрат 109
4.4.7 Результаты моделирования после уменьшения числа операций .
4.5 Выводы по четвертой главе 117
Заключение 119
Список литературы
- Модель каналов связи
- Комбинированный имитационно-аналитический метод оценки вероятности ошибки в системе передачи цифровой информации с многопороговым декодером
- Применение многопороговых декодеров в системах с адаптивным кодированием
- Поиск путей получения вычислительной мощности персонального компьютера
Введение к работе
Актуальность темы. Одной из основных проблем, с которой сталкиваются при разработке систем передачи и хранения информации, является проблема обеспечения безошибочности передачи информации по каналам с шумом. Для решения данной проблемы обычно применяются методы помехоустойчивого кодирования, в разработке которых в последние десятилетия появились значительные успехи. Одними из наиболее эффективных алгоритмов с точки зрения соотношения эффективности и сложности реализации являются многопороговые декодеры (МПД) самоортогональных кодов (СОК), которые всего лишь с линейной вычислительной сложностью обеспечивают близкое к оптимальному декодирование даже очень длинных кодов. Материалы более двухсот научных работ в области многопорогового декодирования позволяют считать, что МПД для многих современных высокоскоростных систем передачи информации обеспечивает предельно возможный уровень энергетического выигрыша и обладает очень высоким быстродействием. Вместе с тем перед практическим использованием МПД в конкретных условиях, в частности в системах цифрового телевидения, при необходимости получения наилучших вероятностно-энергетических характеристик нужно проделать огромный объем работ.
Необходимо выбрать или построить применяемый самоортогональный код. Данный код должен быть в наименьшей степени подвержен эффекту размножения ошибок, проявляющегося в том, что при совершении декодером первой ошибки вероятность появления последующих ошибок существенно возрастает. Это значительно ухудшает характеристики итеративной схемы декодирования, к которой относится МПД. Отметим, что при построении «хорошего» в плане устойчивости к размножению ошибок самоортогонального кода необходимо выполнить ряд оптимизационных процедур, в частности выбрать наилучшую структуру кода с параллельным каскадированием. При этом требуется проведение компьютерного моделирования огромного объема, на выполнение которого могут потребоваться недели работы обычного персонального компьютера.
После построения кода необходимо настроить параметры декодера, для чего снова выполняется процедура оптимизации, в процессе которой настраиваются десятки, а в некоторых случаях даже сотни параметров МПД. Это также достаточно затратная с вычислительной точки зрения операция.
На заключительном этапе необходимо убедиться, что разработанный МПД отвечает предъявляемым требованиям, оценив его вероятностно-энергетические характеристики. В случае если целевая вероятность ошибки на бит является не очень малой (до 10–10), то подобная оценка легко выполняется с помощью компьютерного моделирования за несколько часов работы персонального компьютера. Отметим, что известные аналитические оценки эффективности МПД являются сильно заниженными при большом уровне шума и слабо подходят для данной цели. В случае же если целевая вероят-
ность ошибки, как в современных и перспективных системах цифрового телевидения, очень мала (10–11 и менее), то процесс получения подобных оценок с приемлемой точностью может затянуться на недели, месяцы и даже годы работы компьютера. Все это делает задачу уменьшения времени получения оценок эффективности МПД актуальной. Данную задачу можно решать как за счет увеличения скорости работы компьютерных моделей МПД, так и за счет разработки более эффективных аналитических методов оценки его характеристик, что и будет выполнено в рамках диссертационной работы.
Кроме этого, в ряде систем передачи различного рода информации, особенно в системах цифрового телевидения, для повышения эффективности использования канала связи часто применяется так называемое адаптивное кодирование и модуляция, когда в зависимости от состояния канала используются код с одной или другой кодовой скоростью и модуляция большего или меньшего порядка. Для МПД вопросы его применения в подобных схемах раньше не решались. Еще одна сложность применения самоортогональных кодов в подобных системах связана с тем, что на практике они обладают не очень большим кодовым расстоянием и, следовательно, для них характерно наличие так называемой области насыщения вероятности ошибки. Это усложняет задачу получения очень малых вероятностей ошибки, требуемых в современных системах цифровой передачи информации. Следовательно, актуальной также является задача уменьшения вероятности ошибки при использовании самоортогональных кодов в области их субоптимального декодирования.
Степень разработанности темы. Помехоустойчивое кодирование как отдельное научное направление ведет свой отсчет с работы К. Шеннона, которая была опубликована в 1948 году. В этой работе анализировалась пропускная способность канала и делалось заключение, что если скорость передачи информации меньше пропускной способности канала, то существует возможность подобрать такие помехоустойчивые коды и алгоритмы их декодирования, которые позволят восстановить искаженную информацию со сколь угодно высокой точностью. Отметим, что К. Шеннон не предлагал конкретных кодов и алгоритмов их декодирования, а лишь доказал их существование. Однако именно после этой работы начались активные исследования в области помехоустойчивого кодирования. Стали предлагаться различные коды и алгоритмы их декодирования. Из наиболее ярких отечественных представителей этой области можно отметить В.А. Котельникова, Л.Е. Назарова, В.Д. Колесника, Э.Л. Блоха, С.И. Егорова, А.Н. Колмогорова, В.В. Зяб-лова, В.В. Золотарева и др. Среди зарубежных ученых большой вклад внесли работы Дж. Месси, Дж. Возенкрафта, A. Витерби, Р. Галлагера, У. Питерсо-на, Т. Кассами, Р. Блейхута и др.
За последние годы было разработано большое число помехоустойчивых кодов и алгоритмов их декодирования. Однако лишь некоторым из них удалось приблизиться к главной цели – обеспечению работы вблизи пропускной способности канала. Среди таких кодов можно выделить турбо- и турбопо-добные коды, низкоплотностные коды (LDPC), полярные коды. Стоит отме-
тить, что даже самые последние варианты этих методов обладают относительно высокой вычислительной сложностью, что значительно осложняет их практическое применение в высокоскоростных системах передачи информации, к которым относятся и системы цифрового телевидения. В связи с этим возникает задача поиска более простых и более надежных при практической реализации методов кодирования/декодирования.
В процессе решения данной задачи исследователи также сталкиваются с проблемой получения оценок эффективности разрабатываемых ими методов за минимальное время. В случае большой вычислительной сложности алгоритма декодирования или необходимости проведения большого объема эксперимента традиционно наиболее сложные узлы модели системы передачи информации (кодер, декодер) реализовывались на интегральных схемах специального назначения (ASIC) или на программируемых логических интегральных схемах (ПЛИС), обеспечивающих высокое быстродействие. Но данный подход, во-первых, требует проведения большого объема работ по реализации этих узлов на интегральных схемах и, во-вторых, плохо подходит, когда в процессе исследования нужно изменять алгоритм работы узла, например декодера. В этих случаях целесообразно реализовать модель в виде программы для ЭВМ, но при этом нужно обеспечить требуемое быстродействие. В последнее время для этого стали использовать вычислительные возможности графических процессоров (GPU), которые оснащаются тысячами ядер. В этой области известны работы таких специалистов, как J.R. Cavallaro, L. Sousa, G. Wang, G. Falcao, S. Kang. Вместе с тем в процессе реализации модели системы передачи информации с использованием GPU для получения наибольшей производительности всегда нужно решать задачи, связанные с необходимостью учитывать специфику, определяемую составляющими элементами модели, в особенности кодером и декодером. Для МПД подобные задачи ранее не решались.
Для уменьшения вероятности ошибки МПД в области его субоптимальной работы был предложен ряд подходов, основанных на каскадировании применяемых с МПД СОК с простыми для декодирования кодами, такими как коды с контролем четности или коды Хэмминга, а также с другими СОК. Подобные схемы за счет применения внешнего кода позволили уменьшить вероятность ошибки декодирования на 1..4 десятичных порядка, однако их применение приводит к необходимости использования дополнительных проверочных бит. Это уменьшает кодовую скорость применяемого кода, что не всегда допустимо.
Цель и задачи исследования. Цель диссертации заключается в разработке методов и алгоритмов повышения эффективности и исследования многопороговых декодеров самоортогональных кодов в высокоскоростных системах передачи цифровой информации, позволяющих обеспечивать и оценивать вероятности ошибки декодирования порядка 10–11 и менее.
Для достижения поставленной цели необходимо решить задачи:
- разработать и исследовать схему кодирования, основанную на самоортогональных кодах, позволяющую уменьшить вероятность ошибки де-
кодирования в области субоптимальной работы декодеров самоортогональных кодов;
разработать и исследовать метод имитационно-аналитической оценки эффективности МПД, обеспечивающий оценку низких целевых вероятностей ошибки с лучшей по сравнению с известными аналитическими методами точностью;
разработать методику применения многопороговых декодеров в системах с адаптивным кодированием;
разработать и реализовать модель цифровой системы передачи информации с многопороговым декодером, использующей ресурсы центрального и графического процессоров.
Методы исследований. В диссертационной работе используются теории вероятностей, математической статистики, математического и имитационного моделирования.
Научная новизна. В рамках диссертационной работы были получены следующие новые научные результаты:
обоснован новый метод оценки эффективности многопороговых декодеров как блоковых, так и сверточных самоортогональных кодов, отличающийся от известных сочетанием в себе элементов аналитического и имитационного моделирования;
предложена новая методика применения многопороговых декодеров в системах с адаптивным кодированием;
обоснован алгоритм оценивания уровня шума в канале, основанный, в отличие от известных, на анализе содержимого синдромного регистра многопорогового декодера;
предложена каскадная схема кодирования, основанная на самоортогональных кодах, в которой в отличие от известных каскадных схем во внутреннем каскаде только для проверочных символов самоортогонального кода применяется безызбыточный код накопления;
разработаны архитектура, алгоритм выбора параметров и создана программная модель системы передачи информации с многопороговым декодированием, использующая в отличие от известных при вычислениях ресурсы графического процессора.
Теоретическая и практическая значимость работы. Теоретическая значимость заключается в разработке новых методов и алгоритмов повышения и исследования эффективности МПД, позволяющих обеспечить и оценить вероятности ошибки декодирования порядка 10–11 и менее, новой методики использования многопороговых декодеров в системах адаптивного кодирования, позволяющей лучше использовать частотный ресурс канала, а также новой каскадной схемы кодирования, позволяющей существенно уменьшить вероятность ошибки декодирования в области эффективной работы декодера самоортогональных кодов.
Практическая значимость работы заключается в разработке новых схем кодирования, основанных на самоортогональных кодах, обеспечивающих
улучшение их вероятностных характеристик на 4 и более порядков, а также в создании программных средств моделирования, позволяющих в десятки раз увеличить скорость моделирования по сравнению с известными. Использование программных средств позволит исследователям быстрее получать новые научные результаты и разрабатывать многопороговые декодеры, обеспечивающие получение большего энергетического выигрыша кодирования, что улучшит эффективность работы перспективных цифровых систем передачи и хранения информации. Результаты диссертационной работы использованы при выполнении ряда НИР, проводимых в РГРТУ: грант РФФИ 15-07-06348 «Разработка оптимальных алгоритмов декодирования для повышения достоверности передаваемой информации в современных системах передачи данных», грант РФФИ 14-07-00824 «Алгоритмы повышения энергетического выигрыша кодирования при использовании декодеров многопорогового типа», грант РФФИ 13-07-00391 «Разработка эффективных и быстродействующих декодеров помехоустойчивых кодов для перспективных сетей передачи данных», грант Президента Российской Федерации МД-639.2014.9 «Разработка адаптивных методов повышения достоверности передачи и хранения данных для систем с большим уровнем шума с применением многопороговых алгоритмов декодирования помехоустойчивых кодов». На защиту выносятся следующие положения:
каскадная схема кодирования, состоящая из внешнего самоортогонального кода и безызбыточного внутреннего кода накопления, позволяющая на 4 и более десятичных порядков уменьшить вероятность ошибки декодирования по сравнению с вероятностью ошибки декодирования, обеспечиваемой внешним самоортогональным кодом;
комбинированный имитационно-аналитический метод оценки характеристик многопороговых декодеров, обеспечивающий получение оценок вероятности ошибки декодирования порядка 10–11 и менее до ста раз быстрее по сравнению с применением только компьютерного моделирования;
модель системы передачи информации по радиоканалу с многопороговым декодированием, которая использует при работе вычислительные ресурсы графического процессора, и алгоритм выбора ее параметров, позволяющие в десятки раз увеличить скорость моделирования по сравнению с моделью, использующей для вычислений только центральный процессор.
Внедрение научных результатов диссертационной работы. Результаты работы внедрены в ООО НПП «Этра-Плюс» (г.Москва) при разработке аппаратуры систем передачи данных, не связанных с действующими стандартами; в АО «Корпорация «Фазотрон-НИИР» при разработке каналов передачи цифровой информации радиолокационных станций с целью обеспечения высокой достоверности хранения; в учебный процесс ФГБОУ ВО «Рязанский государственный радиотехнический университет» по направлениям 09.04.04 – «Программная инженерия» и 09.04.03 – «Прикладная информатика» в рамках дисциплин «Сети ЭВМ», «Вычислительные системы, сети и телекоммуникации», «Цифровая обработка сигналов», «Компьютерное моде-
лирование»; в АО «Государственный Рязанский приборный завод» при реализации программ целевой подготовки по линии Центра развития персонала.
Достоверность полученных результатов подтверждается корректным использованием математического аппарата, тестированием разработанных программ моделирования, согласованием результатов диссертационной работы в частных случаях с ранее известными данными.
Апробация работы проведена в форме научных докладов по основным результатам диссертационной работы и дискуссий, которые проходили на следующих конференциях: Всероссийская научно-техническая конференция «Интеллектуальные и информационные системы» (г. Тула, 2015 г.); 20-я юбилейная Всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях» (г. Рязань, 2015 г.); Международная научная конференция «Математические методы в технике и технологиях - ММТТ-28» (г. Саратов, 2015 г.); 18-я Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (г. Рязань, 2015 г.), Международная конференция по компьютерным технологиям в физических и инженерных приложениях – ICCTPEA (г. Санкт-Петербург, 2015 г.).
Личный вклад автора. Все основные результаты диссертации получены автором лично.
Публикации. По теме диссертации опубликовано 15 научных работ, в том числе 4 статьи в изданиях, входящих в список ВАК РФ, 1 работа, индексируемая в базе Scopus, 4 тезисов докладов на конференциях различного уровня, 5 статей в сборниках научных трудов. Получено 1 свидетельство о государственной регистрации программы для ЭВМ.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и трех приложений. Общий объем диссертационной работы с приложениями составляет 141 страницу. Работа содержит 56 рисунков, 9 таблиц, список используемой литературы состоит из 135 наименований.
Модель каналов связи
Для построения эффективного алгоритма помехоустойчивого кодирования необходимы характеристики, по которым можно судить об эффективности или неэффективности работы того или иного кода.
Очевидно, что самым распространенным критерием оценки эффективности помехоустойчивого кода является средняя вероятность появления ошибки после декодирования на бит Рь(е) или на информационную последовательность бит Рв(е). Для оценки вероятности появления ошибки можно воспользоваться аналитическими формулами [44]: Рвф/(), (1.8) Pb Yj-NjPc(j), (1.9) j=1 k где Nj - число кодовых слова весау; п - длина кода; к - количество информационных символов кода; PC(J) - вероятность искажения у символов в физическом канале.
Отметим, что непосредственное применение этих формул для реально используемых кодов связано со сложностью определения спектра кода. В силу этого для получения оценок данных вероятностей обычно используют моделирование.
Понятие средней вероятности появления ошибки эквивалентно понятию коэффициента неисправляемых битовых ошибок - bit error rate (BER).
Также широко используется критерий энергетического выигрыша кодирования (ЭВК). Энергетический выигрыш определяется как разница отношений сигнал-шум при отсутствии и наличии кодирования при одинаковой вероятности ошибки. Также этот критерий позволяет учитывать, насколько близко разрабаты 24 ваемая система связи может приблизиться к границе, определяемой основным теоретическим ограничением R C, где C – пропускная способность канала, R – скорость передачи сообщений [84]. Физический смысл ЭВК заключается в следующем: при передаче информации по каналу связи вероятность ошибки зависит от отношения сигнал-шум. Следовательно, при постоянном уровне шума решающее значение имеет мощность передатчика. Применение кодирования позволяет получить требуемую достоверность передачи при использовании передатчика с гораздо меньшей мощностью по сравнению со случаем без кодирования. Очевидно, что во всех системах cвязи важен вопрос экономии энергии, поэтому каждый децибел ЭВК оценивался в миллионы долларов еще 35 лет назад [4]. А в современных условиях развития ЦСТ один децибел в ЭВК имеет еще более высокую стоимость.
Кроме того, важной характеристикой является сложность реализации алгоритма помехоустойчивого кодирования. Данная характеристика важна, так как путем усложнения алгоритмов можно получить низкие значения вероятности появления ошибки, тем самым повысив достоверность передаваемой информации, но стоимость оборудования и временные затраты на процесс кодирования и декодирования могут оказаться неприемлемо большими. Поэтому поиск алгоритмов кодирования и декодирования, имеющих малую сложность и обеспечивающих высокий ЭВК, является важной задачей.
За десятилетия исследований появилось большое количество алгоритмов помехоустойчивого кодирования, которые отличаются друг от друга назначением, характеристиками и прочим. Рассмотрим основные подходы классификации кодов, представленные на рис. 1.5. [70]. Рисунок 1.5 - Классификация помехоустойчивых кодов
Первый подход предлагает разделение кодов на блоковые и древовидные (сверточные). Главное отличие между ними заключается в том, что в блоковых кодах процесс кодирования происходит в пределах блока, где каждому сообщению из к символов на входе кодера будет соответствовать кодовое слово из п символов на выходе кодера [70]. При этом кодирование и декодирование текущего блока не зависят от предыдущих. Основными параметрами блокового кода являются: длина кодового слова п, длина информационной последовательности к, длина проверочной последовательности т = п-к, кодовая скорость R = к/п и минимальное кодовое расстояние dmi„, которое определяется минимальным расстоянием Хэмминга между любыми двумя различными кодовыми словами. Данный показатель определяет минимальное гарантированное число исправляемых кодом ошибок, равное ,= 4mi 1 . (1.10) 2 Сверточный кодер является устройством с памятью, которое вводит избыточность в последовательность входных символов без разбивки ее на отдельные блоки [59]. На каждом такте работы кодера блок из к символов входного сообщения отображается в п символов кодового слова с учетом т предыдущих символов сообщения. Процессы кодирования и декодирования идут непрерывно. Кодер обычно формируется из к0 регистров сдвига, чьи связи с выходными символами будут определяться порождающими полиномами g(ij)(x), где / = 0,1,…,&0-1 - номер входного потока, аj = 0,1,… ,п0-1 - номер выходного потока. Обычно используется архитектура с одним входным потоком. Пример схемы кодера с к0=1 и щ=2 и образующими полиномами
Комбинированный имитационно-аналитический метод оценки вероятности ошибки в системе передачи цифровой информации с многопороговым декодером
Как уже было описано в первой главе, МПД является развитием простейшего порогового декодера Месси [54]. МПД дает возможность проводить декодирование длинных кодов с линейной сложностью. В то же время МПД обеспечивает высокое качество декодирования, которое заключается в приближении к эффективности оптимального декодера. Подобная эффективность МПД может быть обеспечена при различных значениях кодовых скоростей и уровней шума в канале передачи информации. Также нельзя не отметить тот факт, что при столь высоких показателях эффективности МПД прост в реализации и предоставляет высокое быстродействие как при программной, так и при аппаратной реализации [32, 33]. Сочетание этих двух факторов делает МПД хорошим кандидатом для использования в перспективных и существующих системах хранения и передачи информации, в частности в ЦСТ, так как именно ЦСТ требует обработки больших объемов информации в ограниченное время, что подробно описывалось в первой главе.
Рассмотрим более подробно принципы кодирования и декодирования самоортогонального кода с помощью МПД.
Самоортогональным кодом (СОК) называется такой код, у которого совокупность символов синдромов, контролирующих каждый информационный символ, ортогональна относительно этого символа. Такие коды допускают полную самоортогональность, при которой с помощью мажоритарного декодирования будут исправлены все ошибки, исправление которых гарантируется минимальным кодовым расстоянием. Впервые подобные коды начал исследовать Месси [54]. Для того чтобы задать СОК, обычно используется образующий полином g(x), разностный треугольник которого не содержит одинаковых элементов. Пример схемы реализации кодера СОК для полинома (1.21) представлен на рис. 1.7. Отметим, что кодер состоит только из сумматоров по модулю два и регистра сдвига, которые являются наиболее простыми элементами схемотехники.
Для СОК длину регистра сдвига z будет определять неравенство, гарантирующее сохранение самоортогональности: z 2//+1, (2.1) где ju - максимальная ненулевая степень в образующем полиноме. В том случае, если кодовая скорость R=1/2, т.е. кодер имеет одну информационную и одну проверочную ветвь, то длина кода равна «=27, длина информационной части k=z.
Однако на практике чаще используются случаи СОК, который имеет по нескольку проверочных и информационных ветвей. Такие СОК существенно более устойчивы к размножению ошибок при декодировании и, следовательно, позволяют обеспечить лучшие вероятностно-энергетические характеристики. К примеру, СОК с несколькими информационными и проверочными ветвями может задаваться следующими полиномами: g11(jc) = 1 + jc; g12(x) = 1 + x5; (2.2) g21(jc) = 1 + jc3 ; g22(x) = x + x11.
В данном случае СОК задан четырьмя полиномами и имеет пи=2 информационные и nv=2 проверочные ветви. Это означает, что к первой проверочной ветви будут вести ответвления от первой информационной ветви (связи, соответствующие полиному g11) и от второй информационной ветви (связи, соответствующие полиному g12). При этом длина каждого регистра сдвига должна быть не меньше, чем zmax 2//max + 1, (2.3) где jimax - максимальная степень порождающих полиномов из формулы (2.2). Кодер для этого СОК будет выглядеть так, как представлено на рис. 2.1. Длина СОК в общем случае равна n=zmax(nu+nv), длина информационной части k=zmaxnu, длина проверочной части m=zmaxnv, кодовая скорость пи R (2.4) пи +nv Примеры структуры кодовых слов для различного числа информационных и проверочных ветвей представлены на рис. 2.2.
Примеры структуры кодовых слов для различного числа информационных и проверочных ветвей При известном порождающем полиноме g(x) систематического блокового СОК можно легко сформировать его проверочную матрицу Н. Проверочная матрица будет состоять из двух частей: Н = [Р%]. (2.5) Первая часть Рг для кода со скоростью R=1/2 представляет из себя матрицу, образованную из столбцов, являющихся циклическим сдвигом столбца, который имеет единицы на позициях ненулевых коэффициентов порождающего полинома и нули на остальных позициях.
МПД кроме блоковых может декодировать сверточные СОК, которые также задаются с помощью порождающих полиномов, определяющих связи между информационными и проверочными ветвями кода. В отличие от блоковых СОК в сверточных длина кодирующего регистра должна быть не менее увеличенной на единицу максимальной степени порождающего полинома. Пример схемы кодера сверточного СОК для полинома, заданного выражением (1.21), представлен на рис. 1.8.
Применение многопороговых декодеров в системах с адаптивным кодированием
В первой главе диссертации было показано, что для систем цифрового телевидения и многих других систем передачи информации требуются очень малые вероятности ошибки. Вместе с тем достижение таких вероятностей с помощью декодеров СОК сопряжено с некоторыми сложностями, связанными с тем, что для них характерно наличие области насыщения вероятности ошибки. Это иллюстрировалось в параграфе 2.3 на рис. 2.6 при описании комбинированного имитационно-аналитического метода оценивания вероятности ошибки МПД. В связи с этим для получения малых вероятностей ошибки декодирования требуется применять коды с большим кодовым расстоянием, которые имеют большую длину, большую сложность декодирования по сравнению с кодами с меньшим кодовым расстоянием, и, кроме этого, МПД выполняет близкое к оптимальному декодирование этих кодов при большем отношении сигнал-шум по сравнению с кодами с меньшим кодовым расстоянием. Применение кодов с большим кодовым расстоянием не всегда допустимо. Поэтому актуальной является задача уменьшения вероятности ошибки декодирования для СОК в области их почти оптимального декодирования.
Известные решения в этой области связаны с использованием каскадных схем кодирования, состоящих из СОК и простых для декодирования внешних кодов, таких как коды с контролем четности или расширенные коды Хэмминга [41, 42, 43, 67]. Но применение каскадирования приводит к необходимости передачи по каналу дополнительных проверочных битов, что уменьшает итоговую кодовую скорость полученного кода. В данной работе предложена схема каскадирования СОК с безызбыточным внутренним кодом [26]. В качестве такого кода применяется код накопления с кодовой скоростью 1. Такой код на сегодняшний день применяется в кодах повторения накопления [101, 111, 133] и в кодах накопления-повторения-накопления [88]. Схема организации каскадирования, предложенная в данной диссертации, представлена на рис. 3.1. За счет использования кода накопления удается в несколько раз увеличить кодовое расстояние самоортогонального кода, малое значение которого приводило к появлению области насыщения вероятности ошибки при достаточно высоких вероятностях ошибки декодирования. Отметим, что кодированию кодом накопления подвергаются только проверочные биты СОК для того, чтобы код остался систематическим. Кроме этого, между кодером СОК и кодером кода накопления установлен перемежитель для того, чтобы ошибки, возникающие в процессе декодирования каждого из составляющих кодов, для другого кода оказывались независимыми.
Для декодирования данного кода можно использовать методы декодирования низкоплотностных кодов, работающие с графом Таннера кода. В работе [68] было показано, что СОК можно рассматривать как низкоплотностный код, для которого легко построить граф Таннера. Добавление кода накопления для проверочной части СОК приводит к тому, что к графу Таннера СОК добавляется зигзагообразный граф Таннера кода-аккумулятора. Итоговый граф каскадного кода, основанного на блоковом СОК длиной 28 бит, заданном порождающим полиномом (1.21), имеет вид, показанный на рис. 3.2. Здесь yi представляют мягкие решения относительно принятых из канала битов. CD W
В процессе декодирования каскадного кода выполняется ряд итераций декодирования, на каждой из которых осуществляется вычисление сообщений от битовых узлов к проверочным, от проверочных к проверочным и обратно. Эти сообщения могут вычисляться в соответствии c любым алгоритмом декодирова 68 ния, работающим с графом Таннера кода [91, 132]. Наиболее простым из них с точки зрения вычислительной сложности является min-sum алгоритм. В соответствии с данным алгоритмом сообщения, посылаемые і-м битовым узлом ку-му проверочному, определяются как сумма всех сообщений, поступивших от других проверочных узлов, и канального решения для кодового бита: чи=ц+ Y.rk,i, (3.1) keCt,k j где Яу - сообщение от /-го битового к у-му проверочному узлу; Д - мягкое решение демодулятора относительно /-го канального бита; Q- множество номеров проверочных узлов, связанное с і-м битовым узлом; г - - сообщение от к-го проверочного к /-му битовому узлу (данные сообщения на первой итерации декодирования инициализируются нулями). Сообщения, посылаемые j-м проверочным узлом к /-му битовому, определяются как rJt= Ylsign(qkj)- min (qkJ), (3.2) keRj,k i , к Кгкфі где Rj - множество номеров битовых узлов, связанное су-м проверочным узлом. Процесс обмена сообщениями между битовыми и проверочными узлами повторяется многократно, несколько десятков или даже сотен раз. После этого результатом работы декодера будут мягкие решения, определяемые в соответствии с выражением bt=Li+Y.\i. (3.3) кєСі Знак получаемых решений будет определять значения декодируемых битов, а модуль - их надежность. Далее представим результаты исследования предложенной каскадной схемы, полученные при помощи компьютерного моделирования. На рис. 3.3 представлены графики зависимости вероятности ошибки декодирования от отношения сигнал-шум в канале с АБГШ при использовании модуляции типа BPSK и демодулятора, формирующего мягкие решения.
Поиск путей получения вычислительной мощности персонального компьютера
Физический канал моделирует искажение передаваемых символов. Для моделирования АБГШ необходима случайная величина с нормальным законом распределения. Для ее получения используются ГПСЧ, который сгенерирует нормально распределенную случайную величину, и метод Марсальи и Брея [64], который преобразует ее в нормально-распределенную величину с заданной дисперсией.
Работа ГСЧП - это 11 элементарных вычислительных операций. Алгоритм работы метода Марсальи и Брея подробно описан в [64]. Отличительной особенностью этого метода является что он генерирует сразу две величины. Из алгоритма работы этого метода очевидно, что число элементарных операций, затрачиваемых на генерирование двух случайных величин, состоит из двух слагаемых. Первое слагаемое - постоянное, равное 11 элементарным операциям. Второе слагае мое – это значение, которое может меняться случайным образом. Оно складывается из двух вызовов ГПСЧ, что дает 22 элементарных операции и дополнительно 10 элементарных операций, которые и реализуют основную часть метода Марса-льи и Брея. Таким образом, вторая составляющая объема операций метода Марса-льи и Брея состоит из 32 операций. Далее, если сумма квадратов значений двух равномерно распределенных на интервале [–1; 1) величин больше единицы, то следует повторить еще раз эти 32 операции. Количество раз, которое необходимо повторить выполнение 32 операций, будет обратно пропорционально вероятности того, что сумма двух равномерно распределенных случайных величин на интервале [–1; 1) меньше единицы. Данная вероятность определяется отношением площади окружности и площади квадрата, в который вписана эта окружность, что наглядно видно из рис. 4.9.
Таким образом, в среднем вторая составляющая объема операций физического канала будет равна 48/ операций. А общая сумма всех элементарных опе 104 раций на выполнение метода Марсальи и Брея составит (11 + 48/) операций. Замечательно, что этот объем операций потребуется на генерирование двух случайных нормально распределенных величин, которые и будут использоваться для искажения одного передаваемого символа. Число же элементарных операций в физическом канале на один передаваемый бит будет определяться выражением V =11 + — . . (4.8) ch bps 44 2
Число операций обращения к памяти будет также зависеть от числа бит на символ и определяться формулой
В отличие от случая с модуляцией, число элементарных операций и число операций обращения к памяти будут зависеть от типа модуляции. Число элементарных операций может быть оценено формулой Декодер является самым затратным с вычислительной точки зрения узлом системы передачи информации. Для корректной оценки затрат на декодирование, оценку необходимо разделить на три этапа: заполнение синдрома, работа порогового элемента и коррекция возможных ошибок.
Процесс заполнения синдромного регистра аналогичен процессу кодирования с небольшими изменениями. Также по сравнению с процессом кодирования нам понадобится одна дополнительная операция обращения к памяти. Это отражено в формуле (4.13). В результате количество элементарных операций будет вычисляться по формуле
На пороговом элементе происходит суммирование необходимых элементов из синдромных регистров и сравнение полученных сумм с порогом. На это потребуется количество элементарных операций, определяемых выражением:
Если количество отводов от каждой информационной ветви постоянно и равно С, то формула (4.17) примет вид VT =I(Cnr +1) = Id. (4.18) При определении количества операций обращения к памяти помимо обычных обращений к массиву индексов следует учитывать операцию обращения к разностному регистру. В результате выражение для определения числа обращений к памяти примет вид
Если количество отводов от каждой информационной ветви постоянно и равно С, то формула (4.19) примет вид
UT = 1(2Сп Г + 2) = 2И . (4.20)
В процессе коррекции ошибок необходимо инвертировать все элементы синдрома, участвовавшие в вычислении суммы на пороговом элементе, исправить информационный символ и соответствующий ему элемент разностного регистра.
Необходимо отметить, что этап коррекции, в отличие от первых двух, выполняется не для каждого декодируемого бита, а только в случае необходимости его коррекции. Очевидно, что это происходит с вероятностью/?, не большей вероятности ошибки в канале. Учитывая область отношений сигнал-шум, в которой МПД может эффективно исправлять ошибки, можно предположить, что коррекция осуществляется не более чем на 10 % битов. Это позволяет утверждать, что для используемых на практике параметров кода число арифметических операций и число обращений к памяти в расчете на один информационный бит можно сверху оценить как 21 (здесь / - число итераций декодирования). При этом данная оценка является существенно завышенной, поскольку на последних итерациях декодирования обычно осуществляется много меньше исправлений битов, чем на первых.