Содержание к диссертации
Введение
1 Алгоритмы обнаружения и оценки внешних параметров сверточных помехоустойчивых кодов 10
1.1 Вводные замечания 10
1.2 Обоснование алгоритма предварительной обработки анализируемой двоичной последовательности на основе расчета матриц перехода 11
1.3 Обоснование алгоритма обнаружения сверточных кодов с известными внешними параметрами на фоне несверточных помехоустойчивых кодов
1.3.1 Алгоритм обнаружения неперфорировапиых сверточных кодов с известными параметрами на фоне несверточных помехоустойчивых кодов 24
1.3.2 Алгоритм обнаружения перфорированных сверточных кодов с известными параметрами на фоне несверточных помехоустойчивых кодов 31
1.3.3 Экспериментальное исследование предложенных алгоритмов 33
1.3.4 Обоснование параметров алгоритма накопления решений для повышения надежности алгоритмов обнаружения сверточных кодов 36
1.4 Алгоритм распознавания вида сверточных кодов на основе числовых характеристик матриц перехода 41
1.4.1 Обоснование числовых критериев неравномерности матриц перехода 41
1.4.2 Обоснование алгоритма оценки внешних параметров сверточных кодов на основе числовых характеристик и гистограмм уровней для матриц перехода 46
1.4.3 Экспериментальное исследование алгоритма оценки внешних параметров сверточных кодов 52
1.5 Обоснование алгоритмов распознавания вида сверточных кодов на основе совместного использования алгоритмов обнаружения и оценки внешних параметров 53
1.5.1 Анализ вариантов совместного использования схем обнаружения и оценки внешних параметров сверточных кодов при различной априорной информации 53
1.5.2 Обоснование алгоритма приближенной оценки вероятности битовой ошибки в анализируемой двоичной последовательности 56
1.5.3 Экспериментальное исследование предложенного алгоритма распознавания вида сверточных кодов на основе обнаружения представителей типов 63
1.6 Выводы 65
2 Алгоритмы обнаружения и оценки внешних параметров блочных помехоустойчивых кодов 67
2.1 Вводные замечания 67
2.2 Обоснование алгоритма обнаружения и оценки внешних параметров блочных кодов 68
2.2.1 Блок-схема алгоритма обнаружения и оценки внешних параметров
блочных кодов
2.2.2 Обоснование алгоритма обнаружения и оценки параметров синхропоследовательностей 71
2.2.3 Алгоритм обнаружения отдельных блочных кодов на основе законов распределения вероятности весов в сегментах анализируемой двоичной последовательности 80
2.2.4 Алгоритм обнаружения и предварительной оценки параметров блочных кодов 86
2.3 Процедуры распознавания блочных кодов различного класса на основе их множественных свойств 89
2.3.1 Процедура обнаружения и оценки внешних параметров циклических блочных кодов над полями Галуа различного расширения 89
2.3.2 Процедуры обнаружения и оценки параметров нециклических блочных кодов
2.4 Модифицированная блок-схема алгоритма распознавания вида блочных кодов 96
2.5 Экспериментальное исследование предложенного алгоритма распознавания блочных кодов 99
2.6 Выводы 101
3 Алгоритм оценки порождающих элементов помехоустойчивых кодов в интересах распознавания вида составных кодов 102
3.1 Вводные замечания 102
3.2 Алгоритмы обнаружения и оценки параметров различных составных помехоустойчивых кодов
3.2.1 Блок-схема алгоритма распознавания вида составных помехоустойчивых кодов... 103
3.2.2 Алгоритм распознавания турбо-кодов на основе алгоритма распознавания вида сверточных кодов. 106
3.2.3 Алгоритм распознавания каскадных помехоустойчивых кодов на основе алгоритмов распознавания сверточных и блочных кодов 108
3.2.4 Экспериментальные исследования предложенного алгоритма распознавания вида составных помехоустойчивых кодов
3.3 Алгоритм оценки порождающих элементов для помехоустойчивых кодов из известного множества на основе схемы декодер-кодер 112
3.3.1 Обоснование схемы декодер-кодер 112
3.3.2 Алгоритм оценки порождающих элементов на основе схемы декодер-кодер /18
3.3.3 Экспериментальные исследования алгоритма оценки порождающих элементов... 120
3.4 Выводы 121
4 Практически е аспекты реализации алгоритмов в составе системы распознавания вида помехоустойчивых кодов на основе современной элементной базы 123
4.1 Вводные замечания 123
4.2 Обоснование общей структуры системы распознавания вида помехоустойчивых кодов на основе совместного использования алгоритмов обнаружения и оценки параметров помехоустойчивых кодов различного класса 124
4.2.1 Варианты построения системы распознавания вида помехоустойчивых кодов на основе совмещения предложенных алгоритмов классификации, оценки параметров и порождающих элементов 124
4.2.2 Обоснование наиболее эффективного варианта построения системы распознавания вида помехоустойчивых кодов
4.3 Режимы функционирования системы распознавания вида помехоустойчивых кодов при различной априорной информации 139
4.4 Анализ вычислительных затрат на реализацию отдельных блоков в составе системы распознавания вида помехоустойчивых кодов
4.4.1 Вычислительные затраты на реализацию алгоритма распознавания сверточных кодов. 143
4.4.2 Вычислительные затраты на реализацию алгоритма распознавания блочных кодов 146
4.4.3 Вычислительные затраты на реализацию алгоритма распознавания вида составных помехоустойчивых кодов 149
4.5 Аппаратная архитектура и выбор элементной базы для реализации системы распознавания вида помехоустойчивых кодов 150
4.5.1 Обоснование аппаратной архитектуры системы распознавания вида помехоустойчивых кодов. 150
4.5.2 Требования к элементной базе с учетом вычислительных затрат 155
4.5.3 Выбор моделей ЦСП и ПЛИС с учетом требований к элементной базе 156
4.6 Выводы 157
Заключение 159
Список литературы
- Обоснование алгоритма обнаружения сверточных кодов с известными внешними параметрами на фоне несверточных помехоустойчивых кодов
- Обоснование алгоритма обнаружения и оценки параметров синхропоследовательностей
- Экспериментальные исследования предложенного алгоритма распознавания вида составных помехоустойчивых кодов
- Режимы функционирования системы распознавания вида помехоустойчивых кодов при различной априорной информации
Введение к работе
Актуальность темы. В настоящее время широкое распространение во многих радиосистемах передачи информации (РСПИ) получили помехоустойчивые коды (ПК) различного класса, типа и параметров, позволяющие обнаруживать и исправлять ошибки в цифровых данных, передаваемых по радиоканалу. К основным типам линейных ПК, которые используются в большинстве РСПИ, относятся сверточные (СК), блочные (БК) и составные коды (СсК). При этом к классу СК принадлежат перфорированные и неперфорированные коды, к БК - циклические ПК и коды с низкой плотностью проверок на четность, а к СсК - каскадные коды и такие высокоэффективные ПК, как турбо-коды.
При этом возможны ситуации, когда необходимо определить, ПК какого класса и с какими параметрами используется в радиоканале передачи интегрированных цифровых информационно-управляющих потоков некоторой РСПИ.
К настоящему моменту в области решения задач распознавания вида ПК и анализа дискретных структур известны работы таких отечественных ученых, как: А. П. Алферов, СМ. Авдошин, С. Г. Баричев, В. М. Сидельников, а также таких зарубежных ученых, как: Б. Шнайер, Н. Смарт, Д. Ф. Зиглер.
При этом наибольший вклад в теорию помехоустойчивого кодирования внесли следующие отечественные ученые: Ю. Л. Васильев, Л. М. Финк, К. Ш. Зигангиров, В. В. Золотарев, В. В. Зяблов, В. М. Дорофеев, В. Д. Колесник, а также зарубежные ученые: К. Е. Шеннон, Р. У. Хемминг, И. С. Рид, Г. Соломон, Р. К. Боуз, Д. К. Рой-Чоудхури, Э. Р. Хоквингем, Э. Д. Витерби, Э. Берликемп, Д. Месси, У. Питерсон, Э. Уэлдон, Т. Кассами, Е. Ивадари, М. Голей и др.
Так, при решении задач радиомониторинга может возникнуть необходимость извлечения первичной информации на основе анализа принятых радиосигналов от передающей аппаратуры, анализируемой РСПИ. При этом одним из этапов обратного преобразования сигналов в общей структуре РСПИ, является декодирование ПК, для выполнения которого необходимо знание его внешних параметров, а также порождающих элементов (ПЭ).
В случае использования РСПИ с адаптацией ПК к уровню помех также требуется устранить кратковременную неопределенность о текущих параметрах системы помехоустойчивого кодирования.
При этом в задачах распознавания вида ПК объем априорной информации о системе помехоустойчивого кодирования может быть различным: от списка возможных типов, до полного отсутствия информации о характеристиках кодов, которые могут быть представлены в анализируемой двоичной последовательности (АДП), получаемой при демодуляции сигналов РСПИ.
Главными недостатками существующих алгоритмов являются необходимость использования крайне большого объема статистического материала, невозможность распознавания ПК большой длины, а также принятия решения в реальном масштабе времени.
При этом существующие алгоритмы, позволяют обнаружи-
вать лишь полностью известные ПК, что не обеспечивает возможности распознавания ПК в случае большого числа гипотез о классе и параметрах кода, а также при наличии мешающих факторов (шумов и помех в радиоканале РСПИ), приводящих к ошибкам в АДП.
Таким образом, актуальной является задача разработки алгоритмов распознавания вида ПК при действии мешающих факторов в близком к реальному масштабу времени.
Цель и задачи работы. Основной целью работы является разработка алгоритмов обнаружения, оценки внешних параметров и ПЭ для ПК в интересах построения высоконадежной системы распознавания вида ПК в близком к реальному масштабу времени при действии мешающих факторов.
Поставленная цель работы включает решение следующих задач:
обоснование алгоритмов предварительной обработки АДП в интересах выделения информативных статистических характеристик, позволяющих обнаружить и оценить внешние параметры ПК различного класса.
разработка алгоритмов обнаружения, оценки внешних параметров и ПЭ для ПК различного класса на фоне других кодов и случайных двоичных последовательностей (СДП), при действии мешающих факторов;
обоснование общей структуры системы распознавания вида ПК на основе совместного использования алгоритмов обнаружения, оценки внешних параметров и ПЭ, позволяющей достичь компромисса между надежностью решений системы и аппаратно-вычислительными ресурсами, требуемыми на ее реализацию в близком к реальному масштабу времени;
анализ вычислительных затрат на реализацию системы распознавания вида ПК для выбора элементной базы, обеспечивающей близкое к реальному масштабу времени функционирование.
Методы исследований. В работе использовались методы математической статистики и статистической радиотехники, кодирования в полях Галуа, математический аппарат теории вероятностей, математический аппарат теории Марковских процессов, матричного исчисления, вычислительной математики, а также новейшие достижения в области цифровой обработки информации.
Научная новизна. В рамках диссертационной работы получены следующие новые научные результаты:
-
Алгоритм предварительной обработки АДП на основе расчета матриц перехода (МП), позволяющий компактно представить данную последовательность и выявить ее статистически особенности.
-
Устойчивые к мешающим факторам алгоритмы распознавания видов СК и БК на основе совместного использования алгоритмов обнаружения и оценки внешних параметров ПК в масштабе нереального времени.
-
Алгоритмы обнаружения и оценки внешних параметров БК различного типа на основе автокорреляционной функции (АКФ) и закона распределения вероятности весов (ЗРВВ) для АДП, а также множественных свойств БК, позволяющие распознать такие блочные ПК, как: коды Рида-Соломона (PC),
Боуза-Чоудхури-Хоквингема (БЧХ), Голея (КГ), Рида-Маллера (РМ),
Хемминга (КХ) и низкоплотностные коды (LDPC) в близком к реальному масштабу времени.
4 Устойчивый к мешающим факторам алгоритм распознавания СсК,
включающий алгоритмы распознавания турбо-кодов и каскадных ПК,
функционирующий в близком к реальному масштабу времени.
5 Устойчивый к мешающим факторам алгоритм оценки ПЭ различных ПК
на основе схемы декодер-кодер, позволяющий в реальном масштабе времени
принимать решения о виде ПК, при условии, что его ПЭ принадлежит
известному множеству.
Практическая значимость и внедрения результатов работы. Предложенная в работе система распознавания вида ПК может быть использована при решении задач радимониторинга, как для принятия оперативных решений, так и для пополнения априорной информации о возможных ПК, а также в радиосистемах с адаптацией ПК. Результаты диссертационной работы были внедрены в рамках НИОКР с ОАО «Калужский научно-исследовательский радиотехнический институт».
Основные положения, выносимые на защиту
1 Алгоритм предварительной обработки анализируемой двоичной
последовательности, позволяющий компактно представить данную
последовательность посредством матрицы переходов в интересах построения
высоконадежного алгоритма распознавания вида сверточных кодов.
2 Устойчивые к мешающим факторам алгоритмы распознавания вида
сверточных, блочных и составных помехоустойчивых кодов, обеспечивающие
вероятность правильного распознавания Рп >0,94, Рп > 0,91 и Рп >0,89
соответственно при вероятности ошибок в радиоканале передачи информации iL.^0,01.
3 Алгоритм оценки порождающих элементов на основе схемы декодер-
кодер, позволяющий распознать вид помехоустойчивого кода из известного
множества в реальном масштабе времени при наличии мешающих факторов и
обеспечивающий вероятность правильных решений Рп > 0,82 при вероятности
ошибок в радиоканале передачи информации Рош б < 3 10~3.
Апробация работы. Результаты работы докладывались и обсуждались на следующих научно-технических конференциях (НТК): 15-й, 17-й ВНТК «Новые информационные технологии в научных исследованиях», РГРТУ (г. Рязань 2010, 2012); 15-й, 17-й МНТК "Проблемы передачи и обработки информации в сетях и системах телекоммуникаций", РГРТУ (г. Рязань 2010, 2012); 13-й, 14-й, 15-й, МНТК "Цифровая обработка сигналов и ее применение" (г. Москва 2011, 2012, 2013); 16-й, 17-й ВНТК студентов, молодых ученых и специалистов "Биотехнические, медицинские и экологические системы и комплексы" РГРТУ (г. Рязань 2011, 2012); 20-й МНТК «Современное телевидение и радиоэлектроника», (г. Москва 2012); X МНТК «Перспективные технологии в средствах передачи информации» (г. Владимир 2013); 6-й МНТК
«Космонавтика. Радиоэлектроника. Геоинформатика» имени В. Ф.
Уткина (г. Рязань 2013 г).
Публикации. По теме диссертации опубликовано 19 работ. Из них 8 статей в научно-технических журналах и межвузовских сборниках, 3 из которых в журналах рекомендованных ВАК, а также 11 тезисов докладов на МНТК и ВНТК.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 103 наименований и 9 приложений. Диссертация содержит 149 с. основного текста и 60 рисунков.
Обоснование алгоритма обнаружения сверточных кодов с известными внешними параметрами на фоне несверточных помехоустойчивых кодов
Одними из наиболее распространенных ПК на сегодняшний день являются СК. При этом на основе анализа различных РСПИ [ 1... 8] можно выделить множество основных видов СК, которое включает: - несистематические и нерекурсивные СК без перфорации с максимальной длиной регистров сдвига от 3 до 9 и кодовой скорости 1/4, 1/3, 1/2, 2/3, 3/4, 3/5; - несистематические и нерекурсивные СК с перфорацией, аналогичные предыдущим и обеспечивающие дополнительно кодовые скорости 5/6, 7/8; - систематические рекурсивные СК (возможно перфорированные) со значениями кодовой скорости 1/4, 1/3, 1/2, 2/3, 3/4, 3/5, 5/6, 7/8.
В результате получен список гипотетических СК, приведенных в таблице С.1 Приложения С, где задана априорная информация о внешних параметрах ПК различного класса. При этом под внешними параметрами ПК понимаются размеры ПЭ кода над полем Галуа заданного расширения, а в случае СК параметры кодера.
Исходя из вышесказанного, для решения задачи обнаружения и оценки внешних параметров различных СК в первой главе необходимо: 1 Обосновать алгоритм предварительной обработки АДП. 2 Обосновать алгоритм обнаружения СК с известными внешними параметрами на фоне несверточных ПК, к которым относятся СДП, БК и турбо-коды. 3 Разработать алгоритм оценки внешних параметров СК. Обосновать алгоритм распознавания вида СК на основе совместного использования алгоритмов обнаружения и оценки внешних параметров таких ПК. Исследования в рамках решения указанных задач необходимо проводить с учетом возможных ошибок в АДП, вероятность которых может быть достаточно высокой. Допустимая вероятность битовых ошибок в АДП при этом не должна превышать некоторого предельного значения, которое будет уточнено в ходе исследований.
Для обоснования структуры алгоритма обнаружения СК важно, что содержание битовых потоков на выходе сверточных и несверточных ПК существенно различается. Так в случае БК структура АДП выглядит как совмещение непересекающихся независимых блоков большой длины, в то время как кодовые слова СК накладываются и состоят из кодовых комбинаций длиной п двоичных символов. Также существенны различия в способе синхронизации сверточных и несверточных ПК [1, 2, 37, 45]. Указанные различия позволяют на основе предварительной обработки АДП сузить априорное множество ПК до списка гипотетических СК, в случае наличия такого кода в анализируемом потоке.
Рассмотрим особенности задачи обнаружения СК на фоне несверточных ПК, которые могут быть представлены в АДП - В. При этом в качестве начальных условий принимается, что сверточный ПК, который может быть представлен в АДП, имеет известные внешние параметры (т0,п0,к0), где т0 - максимальная длина регистров сдвига в составе кодера, п0 - длина выходного и кд - длина входного кадров. Также принимается допущение, что если в АДП представлен известный СК, то заданы моменты смены состояний сверточного кодера, т.е. установлена узловая синхронизация с кодовой решеткой данного СК [37,45].
Далее внешние параметры в рамках данного пункта будут называться параметрами СК. Отметим, что при решении задачи обнаружения СК, наличие рекурсивных связей в составе кодера не существенно, так как для большинства используемых рекурсивных СК можно найти нерекурсивный аналог, при этом множества кодовых слов (КС) данных кодеров будут совпадать. Меняется лишь соответствие между информационными комбинациями и КС, что требует учета лишь при оценки порождающей матрицы СК - GCK (глава 2).
Предлагается представить АДП в виде МП [46, 47], элементы которой показывают вероятность последовательного появления в данном потоке определенных кодовых комбинаций длиной т0 п0 символов, что соответствует выбору кодовых слов СК, равных длине кодового блока (ДКБ) СК. При этом понятие МП заимствовано из теории конечных автоматов Маркова, где посредством данной математической модели описывается вероятность изменения состояния определенной конечной системы, которой в рассматриваемом случае является сверточный кодер [35...45].
Использование МП позволяет компактно описать АДП, которая является одномерным массивом большой длины (до 1010 символов). При этом в МП отражаются основные свойства сверточного кодера, которые в явном виде сложно отразить в алгоритме на основе Марковских процессов [46, 47].
Рассмотрим процесс получения МП для АДП, в которой предположительно представлен СК с заданными параметрами (т0,п0,к0).
Для оценки МП - WiN N.) осуществляется разбиение АДП, представляющей собой бинарный поток В, на пары сегментов длиной X = т0-п0, разнесенных на / символов. При этом пары таких сегментов выбираются с шагом 5, как показано на рисунке 1.1.
Обоснование алгоритма обнаружения и оценки параметров синхропоследовательностей
Подробная иллюстрация зависимостей Кш{1) для всех указанных ситуаций приведена в Приложении F, при этом наиболее показательные зависимости представлены на рисунках 1.21, а, б.
Здесь зависимость 1 имеет место, когда предполагается СК (5,2,1), а в АДП представлен СК (3,3,1). Зависимости 2 и 3 имеют место, когда СК (3,2,1) и СК (3,3,1) поочередно используются как истинные и гипотетические. Зависимость 4 имеет место, когда предполагается СК (2,3,2), а истинным является СК (5,2,1). Зависимости 5 и б получаются при наличии в АДП соответственно кода Рида -Соломона (255,223) и случайной последовательности притом, что предполагается наличие СК (5,2,1).
Из анализа зависимостей, полученных в ходе экспериментальных исследований, следует, что при совпадении истинных и гипотетических параметров СК к.ш(і) 1 1 1 1 ! 1 і
КМП(І) а) при совпадении истинных и гипотетических параметров СК, б) при несовпадении истинных и гипотетических параметров СК а также классов ПК зависимость Кмп(1) всегда имеет монотонно убывающий характер и входит в насыщение при /0 = тист -1. С учетом структуры сверточного кодера [1, 2, 35, 37] и потока на его выходе (рисунки 1.1, 1.20) при совпадении пгт = пист имеет место общая зависимость положения точки насыщения зависимости КМ11{1), которая определяется как: /o = 2 c,„-w,„-l, (1-24) откуда зная /0 можно вычислить тист. Также видно, что при достаточно высокой вероятности битовой ошибки в АДП Р в = Ю 2 зависимость Кмп{1) для заданного СК существенно снижается, при этом общий вид зависимости сохраняется.
Подобное смещение вниз зависимости Кмп{1) наблюдается также в случае частичного несовпадения истинных и гипотетических параметров СК, что вид но из сравнения зависимостей для СК с параметрами (3.3.1) (рисунок 1.21, и зависимость 3 на рисунке 1.21 б).
В случае полного несовпадения истинных и гипотетических параметров СК (в основном при п п Ф пист) даже в отсутствие ошибок указанные особенности зависимости Кмп(1) не проявляются. При этом появляются всплески данной зависимости, что вызвано изменением интервала между выбираемыми сегментами АДП.
В случае перфорированного СК данная зависимость имеет другой вид. Так для фиксированной матрицы перфорации Рск, имеющей размер х nucm х Н разбиение АДП, как показано ранее, производится на сегменты длиной у-Н, где у = mQnQ Iхпй =т0/х, yeZ. При этом интервал / между такими сегментами выбирается не кратным значению n n, а с переменным значением соответственно числу единиц в столбце матрицы перфорации, для которого получен текущий символ: It=2І =1[РСА.(1,У) + РСА-(2,7 )]- Тогда интервал между сегментами неперфорированного СК также претерпевает соответствующие изменения и в результате координата точки насыщения h.neP. перфорированного СК определяется как: 1о.пер. = YJJVCK&J) + скО-,Л\ где і = 2тистпист - уН -R(yli)[2mucmnucm], (1.25) где 1о.„еР. показывает длину интервала в отдельных символах, а не в кадрах, и ЯЬ)[а] оператор вычисления остатка от деления a nab.
При этом как для перфорированных, так и для неперфорированных СК наличие ошибок в АДП вероятности Рош6 \О 2 приводит к появлению значительных всплесков в зависимости Кт (I) и потере ее монотонности.
В случае полного несовпадения истинных и гипотетических параметров СК (в основном при пгип Ф пист) даже в отсутствие ошибок указанные особенно сти зависимости Кмп (/) не проявляются, а в случае, когда в АДП представлен несверточный ПК, зависимость Кмп(1) имеет практически равномерный характер со случайными колебаниями.
Также в ходе предварительных экспериментальных исследований получено, что при полном или частичном совпадении истинных и гипотетических параметров СК пист =пат, ГУ для МП (при Кмп{1 = 0)) всегда имеет две выраженные моды, разнесенные по краям области определения ГУ. В случае несовпадения пист Ф п№П ГУ имеет три и более компоненты, равномерно распределенные в области ее определения, как показано на рисунке 1.7. Отметим, что при анализе турбо-кодов, основанных на параллельном совмещении сверточных СК, получаются подобные ГУ.
Это свойство может быть использовано для оценки параметра пист для СК, если такой код представлен в АДП.
С учетом полученных экспериментальных результатов структура алгоритма оценки внешних параметров СК имеет следующий вид (рисунок 1.22).
СК На первом этапе работы данного алгоритма выполняется оценка и нормировка МП для всех конфигураций гипотетических параметров из множества Аск при 10 = О, а затем для каждой из полученных МП вычисляется ГУ.
Далее для полученных ГУ в соответствии с алгоритмом, приведенным на рисунке G.1 в Приложении G, оценивается число мод и анализируется их положение в области определения ГУ, в результате чего методом исключения
формируется оценка внешнего параметра пист - пист, при этом может быть выделено несколько значений данного параметра.
Наличие блока анализа числа мод ГУ позволяет выделить конфигурации гипотетических параметров СК, для которых пист = пгт и не выполнять вычисления Wj(Nt,Nj),I 0 для случаев пистФпгия. Это позволяет снизить общее время работы алгоритма распознавания СК.
По окончанию анализа ГУ, конфигурации параметров гипотетических СК, для которых число мод ГУ более 2-х (соответственно оценке Пист), отбрасываются и выделяется суженное относительно исходного множество Аск. Если ни одна конфигурация параметров из Аск не дала ГУ с удовлетворительными
свойствами, то Аск = 0 и алгоритм останавливается. В противном случае для каждой і-й конфигурации из АСА- выполняется построение зависимости K[m{I),I = 0,2-m[un.
Затем для каждой из зависимостей оценивается координата точки насыщения Г0 и отбрасываются конфигурации параметров, в которых для т гип не выполняется соотношение (1.24).
Экспериментальные исследования предложенного алгоритма распознавания вида составных помехоустойчивых кодов
С учетом возможных ошибок в АДП, вероятность которых равна Рошб 0, выделяемые КС могут отличаться, даже если в неискаженном виде они равны. Следовательно, при сравнении выделяемых и подвергаемых циклическому сдвигу сегментов АДП, играющих роль КС, тождественными должны признаваться не только равные последовательности, но и те, расстояние Хемминга между которыми не превышает /zmax. При этом hmax определяется исходя из гипотетических параметров анализируемого БК «L« Li wi«i на основе теоремы Синглтона [35, 45], из корой следует, что минимальное кодовое расстояние в множестве КС предполагаемого БК jvj не превышает: тт п гип-к гип + \.
Следовательно, при кратности ошибки гош (п гт -к гт)12 искаженное КС остается внутри сферы декодировании кода. Таким образом, максимально значение hmax, при различии на которое сегменты АДП признаются тождественными, определяется, как /jraax («L- L)/2. В случае недвоичных БК необходимо анализировать распределение ошибок внутри КС, при этом несколько двоичных ошибок внутри символа длиной т „ 2 бит рассматриваются как одиночная ошибка.
Для принятия решения о состоятельности одной из гипотез HQ или //, необходимо сравнение оценки рБК с пороговым значением , соответствующим схеме принятия решения по критерию Байеса [52 ... 56]. Значение данного по рога эмпирически обосновано в ходе предварительных экспериментальных исследований в рамках обоснования алгоритма обнаружения циклических БК и составляет % =0,94. В результате, с учетом рассмотренных процедур, общая процедура обнаружения и оценки параметров циклического БК, если такой код представлен в АДП, содержит следующие шаги: 1 Осуществляется выбор конфигурации гипотетических параметров гігші к гші т гші Для кода С, ЧХ или КГ, параметры которых принадлежат апри орным множествам А РС,А БЧХ,А КГ соответственно. 2 Производится разбиение АДП, как показано на рисунках 2.14 а, б, так чтобы для заданного значения расстояния между СП - Го выполнялось условие безостаточного разбиения соответственно формуле (2.1). 3 Далее для выделенных КС по правилу, показанному на рисунке 2.15, вы полняется оценка цикличности (р БК (формула (2.7)), ее нормировка и запомина ние в векторе {(рБК). При этом нормировка производится относительно предпо лагаемой длины КС ,„: Р ВК,„ = Р БК "L л J л J - 4 J 4 Затем производится выделение комбинации Пц,кц,ти, для которой рБК является максимальным среди всех элементов вектора {(рБК). 5 Для подтверждения цикличности обнаруженного БК производится срав нение значения (р БК с порогом , позволяющим определить попадает данная оценка в интервал значений, характерный для нециклических БК ((рБК ), или же срБК превышает порог: р]БК ,. 6 В случае подтверждения гипотезы Я, на основе значения оценок пч,тц определяется, какому подтипу принадлежит обнаруженный БК, соответственно следующему правилу: КГ: (пі 23; тч = 1), (пц = 24; w = 1); РС:ті 3; (2.9) БЧХ: (щ 2Ъ;тц = 1),(щ 24;ти = 1). 7 В случае подтверждения гипотезы Н0 алгоритм останавливается. 8 итоге на выходе алгоритма распознавания циклического БК выдается решение о том, цикличен данный код или нет, оценка подтипа обнаруженного БК, а также множество оценок ПБК = щ,{кБк},тБк = ти, где неопределенность в значении параметра кБК вызвана его незначительным влиянием на степень цикличности. Так, с учетом таблицы С.1 Приложения С, в которой показаны априорные параметры БК, при обнаружении циклического кода на основе оценок ПБК = щ,{кш},тБК = тц получаем оценку вектора параметров для одного из подтипов циклических БК: АБЧХ,АРС или Акт.
Пусть в результате анализа обнаруженного БК на цикличность принято решение, что код не является циклическим, тогда далее необходимо определить подтип обнаруженного БК и выполнить оценку его параметров. При этом имеет место несколько возможных ПК: код LDPC, КХ, код РМ или турбо-код (свер-точный или блочный).
Далее обоснуем процедуру обнаружения кодов LDPC различной длины и кодовой скорости RLDPC.
Введем следующие гипотезы: Н{ - в АДП представлен LDPC код, Н0 - БК не является низкоплотностным. В ходе процедуры обнаружения БК и турбо-кодов определяется оценка интервала между СП - Го. При этом для LDPC кодов, имеющих относительно большую длину, между СП помещается одно КС, следовательно, оценка параметра nLDPC определяется как: nLDPC = То.
Также, из анализа таблицы С.1 Приложения С следует, что значение оценки hLDPC должно быть не меньше 1000 символов, чтобы гипотезу Я, было целесообразно рассматривать. В противном случае принимается решение, что обнаруженный нециклический БК не является LDPC или турбо-кодом, и дальнейший анализ ведется для кодов РМ и КХ, возможные параметры которых также приведены в таблице С.1 Приложения С.
Далее обоснуем правило принятия решения о том, является БК, обнаруженный в АДП, низкоплотностным кодом или нет.
В ходе предварительных экспериментальных исследований свойств ЗРВВ (пункт 2.2.3) для БК с различными параметрами (таблица С.1) получены распределения вероятности значений МО aw числа единиц в сегментах АДП для LDPC и других кодов. Данные экспериментальные распределения P(aw IНх) и P(aw I Нй) можно использовать в алгоритме проверки гипотез Нх и Н0 при вычислении апостериорных вероятностей.
Так, для принятия решения по критерию Байеса [52, 53, 84] на основе данных одномерных апостериорных распределений область реализаций МО aw разбивается посредством порога ра на две непересекающиеся подобласти соответственно гипотезам Нх и Н0. Непосредственно проверка гипотез соответ ствует решению неравенства: aw ра, где эмпирически обоснованный порог является нормированным и составляет ра =0,36.
Режимы функционирования системы распознавания вида помехоустойчивых кодов при различной априорной информации
В случае БК основные вычислительные затраты обусловлены применением алгоритмов обнаружения и предварительной оценки параметров БК (рисунок 2.13), а также алгоритма обнаружения и оценки внешних параметров циклических БК в составе блок-схемы на рисунке 2.16.
Определим вычислительные затраты на реализацию каждого из этих алгоритмов. Алгоритм обнаружения и предварительной оценки параметров БК (рисунок 2.13) строится на базе двух основных процедур, таких как обнаружение и оценка параметров СП, а также обнаружение отдельных БК на основе ЗРВВ.
Основная процедура, реализуемая в алгоритме на рисунке 2.4, это оценка АКФ, что при заданной длине АДП L требует примерно 21} операций умножения и сложения. Как показано в [87...92], операция свертки, используемая при вычислении АКФ может быть выполнена посредством прямого и обратно преобразования Фурье, что снижает вычислительные затраты, но требует наличия АДП в полном объеме. При этом свертка может быть начата с момента приема АДП и выполняться в ходе ее поступления.
Таким образом, процедура вычисления АКФ требует около УАКФ = 2ІІ арифметических операций, что при L = 106 составляет VAK0 = 2-1012. Отметим, что вычисление всех точек АКФ не требуется, так как с учетом максимального значения интервала между СП Ттт =10000 достаточно \0Ттах точек, откуда конечный объем вычислительных затрат составляет УАКФ = 20Гтах -L =2-10и, т.е. среднее число операций на символ АДП составляет максимум у - =20Т «2-Ю5
Отметим, что вычисление АКФ можно произвести до момента получения АДП в полном объеме, для чего поступающий поток двоичных символов раз 146 бивается на сегменты, внутри которых вычисляются коэффициенты корреляции, усредняемые затем по всем сегментам АДП [90, 93, 94]. Так при длине сегментов „ =100, необходимо параллельное выполнение иАКФ=%ЛКФ вычислительных процессов, направленных на заполнение текущего вектора координат АКФ длиной Е,АКФ.
В ходе выполнения алгоритма обнаружения отдельных БК (рисунок 2.10) большое количество вычислительных затрат расходуется на получение оценок ЗРВВ и критериев % их согласия с биномиальным законом распределения вероятности [48, 58, 59].
При этом получение оценок ЗРВВ для различных гипотетических значений длины КС блочных ПК с параметрами из множества {пБК, кБК} можно распараллелить. Так, с учетом возможных БК и турбо-кодов, приведенных в таблице С.1 Приложения С, может быть сформировано до UБК =45 параллельных вычислительных процессов.
Оценка ЗРВВ является относительно простой процедурой и выполняется по мере поступления АДП в алгоритм обнаружения и предварительной оценки внешних параметров БК. При этом для вычисления единственной оценки ЗРВВ при N = п гш с учетом требования к длине АДП L 100 N необходимо выполнить порядка V3PBB -L-(N-l)/N арифметических операций. Следовательно, на каждый символ АДП приходится примерно одна операция сложения.
Вычисление оценок хг Для некоторой оценки ЗРВВ W(v,N) с биномиальным законом требует N -I сложений и столько же умножений, что в сумме дает VKcn = 2(iV -1) арифметических операций. При этом вычисление оценок %2 для каждой оценки ЗРВВ также целесообразно распараллелить, что даст соответственно UEK = 45 вычислительных процессов. В результате получим, что каждый вычислительный процесс содержит последовательное получение оценок ЗРВВ и х2 Для одного значения N = п шп.
Таким образом, реализация алгоритма обнаружения и предварительной оценки параметров БК требует параллельного выполнения около UEK, = 45 вычислительных процессов. При этом в среднем общее число вычислительных затрат в каждом таком процессе составляет: БК,\ ЗРВВ + ксп (4.10) откуда с учетом возможных значений длины КС для БК (таблица 1 Приложения С.1) получим УБК1 = 205 103 арифметических операций.
Далее рассмотрим затраты на реализацию алгоритмов распознавания типа и оценки внешних параметров БК (п. 2.3) на основе их множественных свойств, где основных затрат требует алгоритм обнаружения и оценки внешних параметров циклических БК над полями Галуа различного расширения.
Пусть в АДП представлен код БЧХ с параметрами (и = 63, к = 30) и общая длина АДП составляет L = l00-n, тогда для оценки показателя цикличности (рБК необходимо элементарных операций в сумме: УБК,2=2пъ \Ь1п-1 + \), (4.11) что для заданного ПК составляет 2.525-109. Следовательно, среднее число операций на один символ АДП составляет приблизительно 4.01 - 10s.
С учетом независимости вычисляемых показателей цикличности срБК для различных гипотетических значений длины КС кодов циклического типа, число которых равно двадцати (таблица С. 1 Приложения С), получение таких оценок можно распараллелить, что потребует UБК1 - 20 вычислителей. В таком случае общие затраты на реализацию алгоритма распознавания БК составляют: БК = АКФ + БК,\ + БК,1 (4 12) откуда с учетом ранее полученных результатов имеем VlK =2-10" + 2.525-109+205-103«2.003-10" элементарных операций. Т.е. основные вычисления требуются на оценку АКФ и показателей цикличности. При этом среднее число операций на символ АДП длиной L = 106 двоичных символов составляет примерно V K « L.
