автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Разработка и моделирование алгоритмов списочного декодирования блоковых кодов методом вычисления кластера

На правах рукописи

Шакуров Радик Шамильевич

РАЗРАБОТКА И МОДЕЛИРОВАНИЕ АЛГОРИТМОВ СПИСОЧНОГО ДЕКОДИРОВАНИЯ БЛОКОВЫХ КОДОВ МЕТОДОМ ВЫЧИСЛЕНИЯ КЛАСТЕРА

Специальности 05.13.18 - «Математическое моделирование,

численные методы и комплексы программ», 05.12.13 - «Системы, сети и устройства телекоммуникаций»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

2 9 СЕН 2011

Ульяновск - 2011

4854838

Работа выполнена в ФГБОУ ВПО «Ульяновский государственный технический университет» на кафедре «Телекоммуникации»

Научный руководитель: кандидат технических наук, доцент

Гладких Анатолий Афанасьевич

Официальные оппоненты: доктор физико-математических наук, профессор

Самохвалов Михаил Константинович,

кандидат технических наук, доцент Пятаков Анатолий Иванович

Ведущая организация: Военный учебно-научный центр Сухопутных войск

«Общевойсковой академии Вооруженных Сил РФ»

Защита состоится 12 октября 2011 г. в 15.00 на заседании диссертационного совета Д212.277.02 при Ульяновском государственном техническом университете по адресу: г. Ульяновск, ул. Северный Венец, 32, ауд. 211, гл. корпус.

С диссертацией можно ознакомиться в научной библиотеке Ульяновского государственного технического университета

Автореферат разослан «£_» сентября 2011г.

Ученый секретарь диссертационного совета, доктор технических наук,

профессор Крашенинников В.Р.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Учитывая сказанное, актуальной является задача разработки метода получения целочисленных ИДС не зависящего от свойств канала связи и в тоже время пригодного для использования в сочетании со сложными видами

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

Цель и задачи исследования

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

Для достижения поставленной цели в работе решались следующие задачи:

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

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

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

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

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

6. Разработка комплекса программ реализации предложенных алгоритмов и оценка их эффективности методом имитационного моделирования.

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

Научная новизна результатов выносимых на защиту:

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

2. Предложен способ формирования целочисленных ИДС, не зависящий от параметров канала связи и отвечающий требованиям быстрой сортировки

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

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

4. Предложен алгоритм составления списка на основе оценки номера кластера и старших разрядов координат кодового вектора с их дополнительной защитой методом циклических сдвигов и проверок четности.

5. Разработан алгоритм списочного декодирования блоковых кодов на основе процедуры составления списка по признаку кластера. Проведено статистическое испытание модели декодера с составлением списков по кластерам (патент РФ на изобретение № 2344556 от 20.01.2009 г.).

Практическая ценность результатов работы

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

Реализация результатов работы

Результаты диссертационной работы приняты для практического использования в разработках ОАО «Ульяновский механический завод», а также в учебном процессе Филиала Военной академии связи (г. Новочеркасск) и Ульяновского государственного технического университета.

Достоверность результатов, представленных в диссертации подтверждается корректностью применения математического аппарата, непротиворечивостью фундаментальным положениям теории информации и общей теории связи, определяется близостью теоретических расчетов и экспериментальных данных, полученных на ЭВМ.

Апробация результатов исследования. Основные положения диссертационной работы докладывались и обсуждались на научных конференциях Ульяновского ВВИУС (военный институт), 2005-2007 годах; на XIII военной научно - технической конференции 29 ИП МО РФ, г. Ульяновск, 2007 г.; на 40-й научно-технической конференции // «Вузовская наука в современных условиях УлГТУ», 2007 г.; на XIV военной научно — технической конференции 29 ИП МО РФ, г. Ульяновск, 2007 г.; на 29-ой научно -теоретической конференции, Тамбовский ВВАИУРЭ (военный институт), г. Тамбов, 2007 г., на седьмой международной конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов», Ульяновск, 2009., на научно-технической конференции // «Интегрированные автоматизированные системы управления» г. Ульяновск, 2011 г., а также на 66-ой Всероссийской конференции посвященной Дню радио «Научная сессия» г. Москва, 2011 г.

Публикации. По теме диссертации опубликовано 17 работ, в том числе 16 статей в сборниках научных трудов и материалов конференций, две из

которых опубликована в издании, рекомендованном ВАК РФ, и в одном патенте РФ на изобретение.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 116 работ отечественных и зарубежных авторов, содержит 43 рисунка и 12 таблиц. Общий объем диссертации составляет 139 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Формирование логарифмического отношения правдоподобия в модели гауссовского канала обеспечивает получение ИДС по правилу

= (1) сг

где г - случайное значение принятого сигнала, Е - энергия сигнала, приходящаяся на бит, а <т2 - дисперсия для г. Известно, что о2 =М0/2, тогда выражение (1) представляет линейную зависимость, угловой коэффициент которой задается фиксированным параметром сг2, здесь Ы0- спектральная плотность гауссовского шума. Это обстоятельство приводит к изменениям динамического диапазона, вырабатываемых ИДС, вызванных стохастическими

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

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

Для исключения указанных недостатков в решающей схеме приемника двоичных сигналов предлагается ввести очень широкий интервал стирания. Всем значениям сигналов, принятых за пределами этой зоны, присваивать максимальную градацию надежности Хтах, а интервал стирания разбить на Хтах ~ 1 равных участков, которым от границы зоны стирания к жесткому порогу решающей схемы в порядке убывания номеров от Хтах присваивать соответствующие целочисленные значения ИДС. Принципиально это означает, что в традиционной схеме со стиранием элементов, символы, попавшие в зону неопределенности должны интерпретироваться как стертые позиции, большинство из которых в обычной схеме стирающего канала связи оказались бы ложными стираниями. В новых условиях символы с ИДС меньшими Хтах также могут трактоваться как стирания, но они в отличие от классического стирающего канала связи будут иметь вполне определенные градации надежности. Пусть в канале с аддитивным белым гауссовским шумом (АБГШ) номинальный уровень двоичных сигналов равен [ч/я| и пусть порог зоны

неопределенности определяется выражением \р4Ё\, где 0<р<1 - интервал стирания. При этом все сигналы )\ > оцениваются как ИДС с номером

Лтах = 2а -1, где а - разрядность оценок в двоичном виде. Интервал от 0 до \р4Щ разбивается на Хтах -1 уровней. Тогда границей первого уровня от

жесткого порога решающей схемы является число [у ] = Р^Ю/С^тах ~

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

Лып = )р(*1 i = и^ +]р(г I / = О, (2)

о о

а выражение для ИДС с максимальным значением принимает вид

^тах ~ | р(г\1=1)сЬ+ | р(г\1 = 0)с!г, (3)

•Уяр -у[е(1+р')

где р' = 1-р. Здесь значение л/£(1 + р') учитывает, что в случае ф) < -4Ё и > \1е принятый символ получает оценку ктах, т.е. решающее устройство функционирует по принципу ограничителя с кусочно-линейным преобразованием. Аналитическое выражение для рабочей характеристики формирователя оценок при г(1) > 0 принимает вид

1 Е(\-р)2

I ехр---—у-2-

х». (4)

При 2(1) < 0 характеристика симметрична относительно порога.

Для выявления особенностей предлагаемого метода формирования оценок рабочая характеристика приемника на рис.1 совмещена со значениями ПРВ р(г | /).

а

■■ И 1 \6

-- / ел - ол\

/ —- Г-х,.-<' -О/А :3. — £ -»•

0 р4Ё 4Ё{\ +

Рис. ]. Рабочая характеристика предлагаемого приемника: а - характеристика для двоичного канала с АМ; б - характеристика для канала с ФМ или КАМ- сигналами

Рассматривая только зависимость |/'), получаем, что при случайном

сигнале г, находящемся в точке 1, согласно (4) формируется действительное значение ИДС. По мере роста аргумента 2, начиная с точки 2, ИДС формируется как Хтах, следовательно, и в точке 3 будет сформировано максимальное значение градации надежности. Однако наличие в (4) значения дисперсии сг2 вновь указывает на прямую зависимость оценок от параметра сигнал-шум. Переходя к целочисленным оценкам в соответствии с функцией г, представим новое правило формирования целочисленных ИДС в виде

1Л(*Л1=

э4Ё

(5)

Значение может быть выбрано любым. В работе принято Хтах=7. Это необходимо для получения сравнительных характеристик предлагаемого правила относительно известных методов, в которых считается достаточным, если а = 3. Сравнение осуществлялось на основе комплекса программ имитационных моделей соответствующих решающих правил.

В ходе испытаний модели анализу подвергалось не менее 1О6 двоичных символов. Результаты имитационного моделирования по правилу (5) представлены гистограммами на рис. 2.

Частость ИДС

Значения

ИДС

Число ИДС в комбинации

а)при соотношении сигнал-шум 0 дБ

комбинации

б)при соотношении ешнал-шум 3 дБ

Рис. 2. Результаты статистических испытаний

Распределение оценок изучалось для двоичного кода БЧХ длины п = 15. На гистограммах в нулевом ряду показаны общие данные по количеству конкретных ИДС, а последующие ряды оценок указывают на появление одной, двух и т.д. до п оценок. Заметно, что распределение для оценки ~Ктах - 7 имеет выраженный максимум.

Для получения сравнительных оценок относительно различных методов формирования ИДС в качестве критерия эффективности выбрано отношение рпр- вероятности совпадения номеров ИДС с правильно принятыми

символами к рош - вероятности совпадения этих же номеров с ошибочными символами. Данное отношение в работе принято за коэффициент правдоподобия: к'пр - р'пр /р'ош, где / = 1,7. Верхняя граница этого параметра определялась как

Частость ИДС

, гтах _

Нд " 1.

0,9 4Е

ехр

(г-У£)2

т-2

2а

(к

-0,971 I ехр -Зст

(г+У£)2

2<т

(6)

Сравнение некоторых характеристик по данному критерию представлено на рис. 3. Заметно, что метод квантования (средний пунктир) для оценки 7 достаточно близок к найденной верхней границе. При этом меньшая по значимости оценка 6 (правый пунктир) значительно уступает верхней границе. Остальные оценки для этого метода (на графике не показаны) равномерно распределены в сторону возрастания показателя сигнал-шум, но со значительным снижением коэффициента правдоподобия. Оценки, полученные методом скользящих окон, для ИДС 7, 6 и 5 на рис. 3 представлены тонкими сплошными линиями.

400 300 200 1(Ю

0

гр4: Ш- I /' [А

■ ' / 1

<т Г Ш [г методы формирования ИДС

I

Предлагаемый Метод

: е, им

J г *

КдБ)

0 1 2 3 4 5

Рис. 3. Сравнительные характеристики для правдоподобий исследуемых методов

Заметно, что коэффициент правдоподобия для Хтах = 7 предлагаемого в работе метода формирования ИДС относительно известных методов формирования оценок надежности отличается в лучшую сторону. Вид характеристики б) на рис. 1 отвечает требованиям угловых видов модуляции.

В третьей главе обосновывается методика обработки комбинаций блокового избыточного кода путем разбиения разрешенного множества кодовых комбинаций на локальные списки (кластеры). Номера кластеров определяются заранее оговоренными / разрядами разрешенных комбинаций, при этом / < к, где к - число информационных разрядов кода. В результате правильного определения номера кластера декодер оперирует со списком комбинаций, объем которого «2к. Известна асимптотическая оценка энергетического выигрыша, получаемая при использовании корректирующего кода с исправлением ошибок, Он =10-/^(/?(/ + 1))дБ, где К = к/п - скорость

кода, г- число, исправляемых кодом ошибок, и— длина кодового вектора. Подобная оценка определяется при условии действия в канале связи

гауссовского шума, когда Е / ,У0 -> со. Реализация мягкого декодера обеспечивает - £)5 • ¿т/л)дБ, где метрика Хэмминга. Отсюда

следует, что при Е / -> от асимптотический выигрыш при мягком декодировании приблизительно на 3 дБ выше, чем при реализации жесткой схемы принятия решения, т.е. О,, < .

В работе показано, что при использовании упорядоченной статистики (использование целенаправленных перестановок символов кодовой комбинации в системе мягкого декодирования) для блоковых кодов при оценке энергетического выигрыша в указанных условиях может быть применено выражение Оа<1- = цх 101а(Л:(] - К +1/и)дБ при этом 0<//<1, где ц< 1 только для двоичных кодов, поскольку они не обладают свойством максимальной декодируемости. На основании особенностей образования эквивалентных кодов относительно исходного кода минимальное значение параметра ц для двоичных кодов предлагается принять /г» 0,7. Следовательно Би < < .

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

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

Если задан двоичный циклический (п,к) код с порождающим полиномом

вшаё(х) = а„_кх"~к + ап_к_ххп~к~* +... + а0, где аг коэффициенты из , то весовой спектр кода определяется как множество векторов

здесь через В^ обозначены представители прямого кода, задаваемые полиномом g(x), а через показаны представители дуального кода,

формируемых полиномом g(x) — g(x) = к(х) .

Очевидно, при / = 0 все кодовые векторы входят в один кластер (система алгебраического декодирования). При произвольном разбивши пространства кодовых векторов В двоичного циклического кода на кластеры значения координат кодовых векторов остаются неизменными в пределах каждого кластера при условии, что сохраняется заданная система определения кластера. Представим номер кластера как последовательность / подряд идущих двоичных символов. Комбинация кода, содержащая g(x), на месте старших

разрядов должна содержать к-1 нулевых символов. Не теряя общности рассуждений предположим, что / = к -1. Тогда номер кластера по первым / разрядам для рассматриваемой комбинации в /- значной системе счисления будет иметь вид gif = (0 0 0 0)у.

Выполняя циклический сдвиг данной кодовой комбинации на один двоичный символ влево (вправо) и вновь, выделяя / разрядов, получим номер

кластера вида g2y=(0 0 0 a„_kx"'k)f. Для следующего циклического

сдвига получим значение g3 f = (О 0 ап_кхп~1 ап_к_^х"'к~1)f. Таким

образом, номера кластеров будут упорядочены в соответствии с особенностями распределения единичных коэффициентов а, в порождающем полиноме g(x), а в окончательном виде результат может быть представлен детерминированной для данных / и g(x) последовательностью чисел

Slf S2f Я3/ S4/ ••• S"/-Полученную из комбинации с порождающим полиномом последовательность номеров кластеров считается базовой и обозначается, как {gif} ■ Циклическое

смещение указанной кодовой комбинации приведет к новой комбинации, принадлежащей данному коду, но при нумерации кластеров она примет вид

82/ g*/ ■■■ g»f gif Предположим, что группа векторов веса Вlg определят общее число

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

всегда обеспечивает получение кластера с номером -1. Циклические сдвиги вектора веса Blg приведет к образованию п векторов данного веса. В формате

чисел, определяющих последовательность номеров кластеров, их можно представить в виде матрицы

gïf g2f g3f gAf ... g(n-\)f gnf g2f gif g*/ - g{n-\)f gnf g\f g3f gAf... g(n-ï)f gnf glf gif

gnf g\f glf g3f ... g(n-\)f .

В комбинациях производных от полинома g{x) будет ровно одинаковых номеров кластеров. Вторая половина кластеров с таким же номером будет в составе комбинаций, образованных от циклических

трансформаций порождающего полинома к(х)дуального кода. Важным свойством такой последовательности является строгая зависимость в смене номеров кластеров от структуры порождающего полинома ¿»(х). Аналогичную последовательность следует получить и для дуального кода И(х).

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

Показано что, каждый разряд любой координаты X или У имеет вес кратный значению 2', где / е /V и {О}, /<(&-/)/2. Это означает, что при восстановлении кодового вектора по признаку кластера значения координат X или У мало изменяются при замене в младших разрядах единиц на нули и наоборот. Это позволяет осуществить дополнительную защиту номера кластера и старших разрядов координат методом проверки четности. Асимптотическая оценка энергетического выигрыша представленного способа для кодов БЧХ указывает на возможность получения дополнительного выигрыша близкого к асимптотической оценке максимально декодируемого кода. Следовательно, Он < 0<; < 003 < Ок/, что показано па рис. 4.

Число информационных разрядов

Рис. 4. Оценка энергетического выигрыш при использовании метода списочного декодирования с оценкой номера кластера

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

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

В четвертой главе представлены методика и результаты имитационного моделирования различных алгоритмов работы декодера и оценка их эффективности с использованием критерия: достоверность в обмен на полосу пропускания. Характеристики гиперкодов различной размерности указанны в таблице 1, а результаты моделирования представлены на рис. 5. В модели реализован модифицированный алгоритм формирования ИДС и процедура декодирования кодовых комбинаций с учетом оценки номера кластера.

Табл. 1

Параметры кодов произведений для проведения моделирования

Параметры кода (">*) Кодовая скорость Базовый код Количество ииформационп ых бит, к Общая дайна блока, п

(16,11)х(16,Н) 0.47 БЧХ: (15,11), 121 256

(32,26)х(32,26) 0.66 БЧХ: (31,26), 676 1024

(64,57)х(64,57) 0.79 БЧХ: (63,57), 3249 4096

(16,11)х(16,11)х(16,11) 0.33 БЧХ: (15,11), 1331 4096

Рис. 5. Оценка помехоустойчивости кодов произведений

Результаты моделирования сравнивались с данными, полученными в канале без кодирования. Во всех экспериментах применялось последовательное соединение кодов БЧХ, образующих систему последовательного турбокодирования. Из результатов имитационного моделирования следует, что наибольшим энергетическим выигрышем обладает гиперкод (16, II)3. Данный код имеет кодовую скорость равную 0,33 и относительно небольшую длину информационного блока - 1331 бит.

На рис. 6 приведены графики зависимости вероятности ошибки на бит от отношения сигнал-шум для системы без кодирования, системы со сверточным кодом и некоторыми гиперкодами. Сверточный код задавался следующими характеристиками: кодовая скорость Я = 0,5; длина кодового ограничения К = 7; образующие полиномы 1718 и 1338. В качестве альтернативы такому коду рассматривались гиперкоды, имеющие кодовую скорость близкую к 0,5, например (16,11)2 с Я = 0,47.

e/No СиВ)

Рис. 6. Сравнение характеристик сверточного кода с гиперкодами

Применение этого кода дает энергетический выигрыш по сравнению со сверточным кодом порядка 0,3 дБ, что не позволяет утверждать о существенных преимуществах его применения. Исправляющая способность кода (16,11)2 позволяет исправлять все одиночные пакеты ошибок длиной до 32 бит, что в условиях замираний является весьма существенным.

Трехмерный код (16,11)3 при R = 0,33 дает энергетический выигрыш около 1,5 дБ. В данном случае скорость кода оказывается меньше 0,5. Это приводит к уменьшению энергии на символ и соответствующему уменьшению помехоустойчивости, которое затем компенсируется при декодировании.

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

В заключении формулируются основные результаты исследований.

1. Методом аналитического моделирования решающей схемы приемника определена верхняя граница коэффициента правдоподобия. Доказано преимущество модифицированной схемы формирования стираний и производство вычислений на этой основе ИДС функционально не зависящих от отношения сигнал-шум в канале связи.

2. Доказана возможность получения дополнительного энергетического выигрыша (от 0,5 до 1 дБ в зависимости от параметров кода) относительно системы с мягким декодированием за счет упорядочения статистики ИДС по убыванию. Показано, что наибольший эффект достигается на скоростях кода близких к 0,5, а число неудачных исходов при оценке свойств нелинейности эквивалентных кодов составляет около 30% от общего числа перестановок столбцов порождающей матрицы кода.

3. Показана возможность декодирования двоичных групповых кодов как максимально разнесенных кодов за счет использования процедуры выделения номера кластера при составлении списка, что обеспечивает по асимптотическим оценкам дополнительный энергетический выигрыш относительно мягкой схемы декодирования от 1 до 3 дБ. Предложен способ защиты номера кластера путем оценки числа циклических сдвигов групп символов, имеющих надежные ИДС в пределах кодового вектора.

4. На основе комплекса имитационных моделей проведено исследование различных схем списочного декодирования применительно к системам с ортогональным частотным разделением каналов. Показаны преимущества кодов произведений размерности ЗБ относительно традиционных схем декодирования как блоковых, так и непрерывных кодов.

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

Основные результаты диссертации изложены в следующих публикациях.

В ведущих научных изданиях, включенных в перечень ВАК

1. Гладких, А. А. Асимптотическая оценка процедуры неалгебраического декодирования избыточных кодов/ А. А. Гладких, К. Ю. Украинцев, Р. Ш. Шакуров // Инфокоммуникационные технологии. Периодический научно-технический и информационно-аналитический журнал. Том 6, №3, 2009. С.30-34.

2. Гладких, А. А. Декодирование недвоичных кодов в адаптивных системах обмена данными/ А. А. Гладких, Е. С. Бородина, Р. Ш. Шакуров // Автоматизация процессов управления. №2 (24) 2011. С.51-55

3. Пат. 1Ш 2344556 С1 МПК Н04Ь 1/20 (2006.01) Декодер с исправлением стираний / А. А. Гладких, С. Ю. Черторийский., В. В. Тетерко, Р. Ш.

Шакуров, Л. Р. Закирова. RU-.Ni> 2344556; заявлено 07.06.2007; опубл. 20.01.2009. Бюл. №2.-9с

В других изданиях

4. Маслов, С. А. Использование сигнально-кодовых конструкций в системах широкополосного радиодоступа для борьбы с преднамеренными помехами / Маслов С. А. Шакуров Р. Ш. //« Сборник научных трудов Ульяновского ВВИУС (военный институт)»- Ульяновск, 2005 г, с 91-93.

5. Шакуров, Р. Ш. Декодирование с использованием оценок надежности в высокоскоростных цифровых системах связи / Р. Ш. Шакуров // Материалы XIII военной научно - технической конференции 29 ИП МО РФ, г. Ульяновск, 2007 г, с 81 -84.

6. Черторийский С. Ю., Шакуров Р. Ш. Алгоритм повышения помехоустойчивости при бортовой обработки ОФМ-сигналов // Сборник научных трудов Ульяновского ВВИУС (военный институт), 2007 г, с 10-12.

7. Тетерко В. В., Черторийский С. Ю., Шакуров Р. Ш. Повышение достоверности высокоскоростного канала передачи данных // Научно-технической конференции УлГТУ, 2007 г, с 25-26.

8. Елисеев Д. И., Тетерко В. В.,Черторийский С. Ю., Шакуров Р. Ш. Моделирование алгоритмов турбодекодирования в системах спутниковой связи» депонированная статья // ЦСИФ МО РФ Сборник рефератов депонированных рукописей, серия Б, выпуск №79, Москва, ЦВНИ МО РФ, 2007, с 18-22.

9. Черторийский С. Ю., Шакуров Р. Ш. Применение алгоритма итеративного декодирования канала связи на основе низкоскоростных протоколов // Материалы XIV военной научно — технической конференции 29 ИП МО РФ, г. Ульяновск, 2007 г, с 37-39.

10. Тетерко В. В., Черторийский С. Ю., Шакуров Р. Ш. Моделирование алгоритмов мягкого декодирования в системах передачи дискретной информации // Сборник докладов и научных сообщений 29-ой научно — теоретической конференции, Тамбовский ВВАИУРЭ (военный ииститут), г. Тамбов, 2007 г, с 18-21.

11. Гладких А. А. Принцип списочного декодирования на основе вычисления номеров параллельных групп / А. А. Гладких, Шакуров Р. Ш. // Современные проблемы создания и эксплуатации радиотехнических систем. Труды шестой всероссийской научно-практической конференции (с участием стран СНГ), г. Ульяновск, 2009, С. 199-201.

12. Гладких А. А. Моделирование канала связи с избыточным кодированием и стиранием элементов / А. А. Гладких, В. В. Тетерко, Шакуров Р. Ш. // Математическое моделирование физических, экономических, технических, социальных систем и процессов. Труды седьмой международной конференции. Ульяновск, 2009, С. 79-81.

13. Гладких А. А., Шакуров Р. Ш. Формирование индексов достоверности символов в стирающем канале связи // Современные проблемы

проектирования, производства и эксплуатации радиотехнических систем. Сборник научных трудов. Седьмой выпуск.-Ульяновск: УлГТУ, 2010.-257 е., ил., С. 130-136.

14. Гладких А. А., Шакуров Р. Ш., Капустин Д.А. Анализ и синтез методов получения оценок надежности символов в системе мягкого декодирования избыточных кодов // НТК Интегрированные автоматизированные систему управления. Сборник докладов. 15-17 марта 2011 г. Ульяновск. С.191-194.

15. Гладких A.A., Шакуров Р.Ш., Кожанов П.Г. Метод формирования индексов достоверности символов в системе мягкого декодирования избыточных кодов // Сборник научно-методических статей вузов связи МО РФ по математическим и общим естественнонаучным дисциплинам / Под ред. И.В. Троценко; ВАС (филиал, г. Новочеркасск, Ростовской обл.). В 2 ч 4.2 - Новочеркасск, 2011. - 170 с.С. 140-145

16. Гладких A.A., Шакуров Р.Ш. Реализация принципа списочного декодирования на основе кластерного анализа // Сборник научно-методических статей вузов связи МО РФ по математическим и общим естественнонаучным дисциплинам / Под ред. И.В. Троценко; ВАС (филиал, г. Новочеркасск, Ростовской обл.). В 2 ч 4.2 - Новочеркасск, 2011.- 170 с. С.145-150.

17. Гладких A.A., Шакуров Р.Ш. Повышение эффективности декодирования по упорядоченным статистикам // Труды Российского научно-технического общества радиотехники, электроники и связи им. A.C. Попова. Выпуск LXVI. - 2011г. С.237-239.

Шакуров Радик Шамильевич

Разработка и моделирование алгоритмов списочного декодирования блоковых кодов методом вычисления кластера

Подписано в печать 06.09.2011. Формат 60x84/16. Усл. печ. л. 1,16. Тираж 100 экз. Заказ 878.

Типография УлГТУ, 432027, г. Ульяновск, Северный Венец, 32

СПИСОК СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ МЕТОДОВ СПИСОЧНОГО ДЕКОДИРОВАНИЯ.

ПОМЕХОУСТОЙЧИВЫХ КОДОВ.

1.1. Постановка задачи.

1.2. Принципы построения телекоммуникационных систем в условиях априорной неопределенности.

1.3. Оценка экспоненциальных границ для системы со стиранием решений и декодированием по списку.20*

1.4. Анализ методов декодирования по спискам в современных системах обмена информацией.

1.5. Кластерный подход к декодированию избыточных кодов как вариант списочного декодирования.

1.6. Выводы.

ГЛАВА 2. ПРИНЦИП ФОРМИРОВАНИЯ ИНДЕКСОВ ДОСТОВЕРНОСТИ СИМВОЛОВ В СИСТЕМАХ МЯГКОГО ДЕКОДИРОВАНИЯ.

2.1. Постановка задачи.

2.2. Принципы построения моделей формирования индексов достоверности символов.

2.3. Сравнительные оценки результатов моделирования.

2.4. Модификация метода получения ИДС в стирающем канале связи.

2.4.1. Формирование ИДС в двоичном канале связи.

2.4.2. Формирование ИДС в системе с сигнально-кодовыми конструкциями.

2.5. Выводы.

ГЛАВА 3. ПРИМЕНЕНИЕ КЛАСТЕРНОГО АНАЛИЗА К РЕШЕНИЮ

ЗАДАЧ СПИСОЧНОГО ДЕКОДИРОВАНИЯ.

3.1. Постановка задачи.

3.2. Асимптотическая оценка энергетического выигрыша при использовании двоичных помехоустойчивых кодов.

3.3. Декодирование избыточных кодов методом упорядоченной статистики

3.3.1. Декодирование двоичных кодов.

3.3.2. Декодирование недвоичных кодов.

3.4. Системы защиты номера кластера при декодировании циклических кодов.

3.5. Развитие конструкции каскадного кода в системе с гиперкодированием.

3.6. Применение принципа гиперкодирования в системе с недвоичным кодом.

3.7. Выводы.

ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ И ОЦЕНКА1 ИХ ЭФФЕКТИВНОСТИ МЕТОДОМ

СТАТИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ.

4.1 Принципы и алгоритмы построения модели системы связи.

4.2. Оценка адекватности разработанной модели.

4.3. Описание имитационной модели на основе ОЧМ.

4.4. Результаты моделирования избыточных кодов.

Актуальность исследования

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

Большинство современных исследований' в области помехоустойчивого кодирования связывается с мягкой обработкой кодовых векторов приемником^ реализующего эффективные итеративные преобразования символов- комбинаций: В! этой связи становится? актуальной? задача построения моделей формирования индексов достоверности символов (ИДС) на физическом уровне, позволяющих классифицировать принятые символы по градациям их надежности. Решение подобной1 задачи обеспечивает более полное использование приемником1 введенной в код избыточности. Необходимо отметить, что наиболее распространенным с точки зрения формирования ИДС является метод разбиения пространства различаемых сигналов на интервалы, при попадании в которые демодулируемого параметра соответствующему символу присваивается определенная^ градация надежности. Однако подобный; метод не выгоден с точки зрения вычислительных затрат. В свою очередь использование модели логарифмического отношения. правдоподобия для получения ИДС не в полной мере отвечает требованиям практической реализации решающих 5 схем, поскольку получаемые оценки напрямую зависят от характеристик канала связи (в частности от отношения сигнал-шум).

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

Учитывая сказанное, актуальной является задача разработки метода получения целочисленных ИДС не зависящего от свойств канала связи и в тоже время пригодного для использования в сочетании со сложными видами модуляции, а также алгоритмов декодирования блоковых кодов на основе анализа номера списка (кластера) и программного обеспечения для моделирования указанных процессов и выявления потенциальных возможностей различных схем построения мягких декодеров.

Цель работы

Целью работы является повышение помехоустойчивости передачи сообщений в системах обмена данными с использованием процедуры декодирования по спискам в стирающем канале связи с применением целочисленных ИДС, обеспечивающих полное использование введенной в код избыточности.

Для достижения поставленной цели в работе решались следующие задачи:

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

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

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

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

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

6. Разработка комплекса программ реализации предложенных алгоритмов, и оценка их эффективности методом* имитационного моделирования.

Методы исследования

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

Научная новизна исследования

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

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

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

4. Предложен алгоритм составления списка на основе оценки номера кластера и старших разрядов координат кодового вектора с их дополнительной защитой методом циклических сдвигов и проверок четности.

5. Разработан алгоритм списочного декодирования блоковых кодов на основе процедуры составления списка по признаку кластера. Проведено статистическое испытание модели декодера с составлением списков по кластерам (патент РФ на изобретение № 2344556 от 20.01.2009 г.).

Практическая значимость исследования

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

Результаты диссертационной работы приняты для практического использования в разработках ОАО «Ульяновский механический завод», а также в учебном процессе филиала Военной академии связи г. Новочеркасск и в Ульяновском государственном техническом университете.

Достоверность результатов, представленных в диссертации подтверждается корректностью применения математического аппарата, непротиворечивостью фундаментальным положениям теории информации и общей теории связи, определяется близостью теоретических расчетов и экспериментальных данных, нолученных на ЭВМ.

Апробация результатов исследования

Основные положения диссертационной: работы докладывались и обсуждались: на научных конференциях Ульяновского. ВВИУС (военный институт), 2005-2007 годах; на XIII военной научно - технической конференции 29 ИГР МО РФ, г. Ульяновск, 2007 г.; на 40-й научно-технической конференции // «Вузовская наука в современных условиях УлГТУ», 2007 г.; на XIV военной научно - технической конференции 29 ИП МО РФ, г. Ульяновск, 2007 г.; на 29-ой научно — теоретической конференции, Тамбовский ВВАИУРЭ (военный институт), г. Тамбов, 2007 г.; на седьмой международной конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов», Ульяновск, 2009.; на научно-технической конференции // «Интегрированные автоматизированные системы управления» г. Ульяновск, 2011 г., на 66-ой Всероссийской конференции посвященной Дню радио «Научная сессия» г. Москва, 2011 г.

Публикации

По теме диссертации опубликовано 17 работ, в том числе 16 статей в сборниках научных трудов и материалах конференций, две из которых опубликованы в изданиях, рекомендованном ВАК РФ, и в одном патенте РФ на изобретение.

Структура и объем диссертации

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 116 работ отечественных и зарубежных авторов, содержит 43 рисунка и 12 таблиц. Общий объем диссертации составляет 139 страниц.

3.7. Выводы

1. Оценка асимптотических возможностей двоичных кодов по исправлению стираний указывает на имеющийся резерв в получении дополнительного энергетического выигрыша при полном использовании введенной в код избыточности. Величина такого выигрыша зависит от скорости кода и составляет от одного до трех децибел относительно мягких методов декодирования. Наибольшее значение выигрыша достигается при скорости кода близкой к 0,5, что соответствует основным принципам теории помехоустойчивого кодирования.

2. Обработка комбинаций любого помехоустойчивого кода в метрике Хэмминга с использованием алгебраических методов декодирования способно обеспечить приближение к асимптотической границе при условии использования свойств эквивалентных кодов. Применение указанной процедуры опирается на систему мягких решений и поиск эквивалентных кодов после упорядочения статистики этих решений по убыванию. Неоднозначность перехода к возможному применению эквивалентного кода из-за не выполнения условий сохранения* нелинейности порождающих матриц обеспечивает значение корректирующего множителя в выражении асимптотической границы в пределах от 0,7 до 0,8, при этом повышается сложность процесса декодирования.

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

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

5. Использование в системе связи недвоичных кодов позволяет отказаться от оценки эквивалентности кода в силу обязательного выполнения для таких кодов условий максимально декодируемых кодов. Вместе с этим, процедура вычисления обратной матрицы для переставленной матрицы остается актуальной и для таких кодовых конструкций. Применение упорядоченной статистики для кодов РС обеспечивает уменьшение общего числа операций сложения в двоичном поле заданной степени расширения. Это позволяет расширить диапазон вводимой в код избыточности при построении адаптивных систем связи.

ГЛАВА 41 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ И ОЦЕНКА ИХ ЭФФЕКТИВНОСТИ МЕТОДОМ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ

4.1 Принципы и алгоритмы построения модели системы связи

Машинное моделирование процессов; происходящих в реальных системах связи, широкие возможности современных программных средств и. средств вычислительной техники по реализации новых алгоритмом функционирования декодеров, позволяют получить надежные результаты для оценки конкретных технических решений, получаемых в ходе модификации известных схем декодирования помехоустойчивых кодов: Именно такие модели в свое время позволили выявить положительные особенности перспективных схем турбокодов и схем многопорогового декодирования [51, 52, 79^ 80, 86, 88, 91, 112].

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

По совокупности классификационных признаков имитационная- модель может быть охарактеризована как стохастическая; алгебраическая, дискретная, оценочная, динамическая и. многоэтапная. Она соответствует всем; основным принципам моделирования, определяющим построение математических моделей [63, 88]. Особенно важным является модульность построения, которая позволяет использовать накопленный опыт реализации типовых элементов, модулей; приразработке сложных моделей систем связи.

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

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

С помощью разработанной имитационной модели» системы связи, включающей элементы подсистемы с помехоустойчивым кодированием, проведено исследование, целью которого являлось получение вероятностных характеристик оценки и« сравнения полученных результатов с известными при следующих исходных параметрах моделирования:

-заданной структуре и алгоритме работы турбокодера-декодера; -источник входного сигнала — случайный источник,Бернулли; -канал АБГШ с постоянными параметрами;

-заданный, набор входных данных, определяемый в виде информационного вектора X = {дс,,х2,.,д;и}.

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

Начало 1 г Ввод исходных данных: StopTime, Ts, m, Niter, EbN0, punkt.y г, k, GJGZ. P0

Выполнение подпрограммы тепи1.ш iter=0; time=0; BERlter=0; d=1/(2*m*r*10A *(EbNo/10))

Формирование вектора информации : X(Ts, k, P0)=x1, Xj^-.X^; time=time+1

Формирование Турбокода: X1=X*G1; X2=interliv(X*G2); X=punktT*MUX(X,X1,X2) 6

Модуляция и добавление шума: Х=(1-2*Х)Л5ЯП(т); У=Х+п(с1)

Нормирование Lc=4*r*10A(EbN0/10); L(uk)=0

Декодер 1 lter=lter+1; Le1(uk)=ln(Pr(uk=+1)/ /Pr(uk=-1)); L1k=L(uk)+Lc*yk+Le1(uk)

Декодер 2 L(uk)=interliv(L1k); Le2(uk)=ln(Pr(uk=+1)/ /Pr(uk=-1)); L2k=L(uk)+Lc*yk+Le2(uk)

10

Деперемежение L(uk)=deinterliv(L2k)

Формирование результатов Y*=sign(L(uk));

BER,.er=f(x.Y*);

BER=sum(BER1 ,ter)/ /iter

12 —

Вывод результатов:

Y , BER,alBK

Нет

Рис. 4.1. Алгоритм работы имитационной модели системы связи с использованием параллельного турбокода

Основные возможности и параметры разработанной модели представлены в таблице 4.1. В таблице через ВЕЯ обозначается вероятность ошибки на бит.

ЗАКЛЮЧЕНИЕ

В ходе проведенных исследований установлено.

1. Использование средств помехоустойчивого кодирования в перспективных системах связи в условиях динамично развивающихся средств цифровой обработки сигналов неразрывно связывается с методами мягкой обработки кодовых комбинаций, а применение списочного декодирования оправдано в условиях высокого уровня помех. Подобные декодеры обеспечивают минимальную сложность реализации при заданной вероятности ошибки. Большинство методов подобной обработки кодовых комбинаций помехоустойчивых кодов оперирует образцами ошибок, позволяющих выделить подмножество тех кодовых комбинаций, которые с высокой вероятностью включают в себя переданный по каналу с помехами вектор. В отличие от традиционных методов списочного декодирования способ кластерного анализа оперирует с наиболее надежными символами, что позволяет ускорить процесс составления списка за счет определения номера кластера.

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

3. Оценка асимптотических возможностей двоичных блоковых кодов по исправлению стираний указывает на имеющийся резерв в получении дополнительного энергетического выигрыша при полном использовании потенциальных возможностей введенной в код избыточности. Доказана способность корректирующего кода обеспечить дополнительный энергетический выигрыш (от 0,5 до 1 дБ в зависимости от параметров кода) относительно системы с мягким декодированием за счет упорядочения статистики ИДС по убыванию. Показано, что наибольший эффект достигается на скоростях кода близких к 0,5, а число неудачных исходов при оценке свойств нелинейности эквивалентных кодов составляет около 30% от общего числа перестановок столбцов порождающей матрицы кода.

4. Применение метода кластерного анализа к процедуре составления списка позволяет достичь верхней границы для двоичных кодов при условии точного определения номера кластера. Защита номера кластера может выполняться несколькими способами. Наиболее эффективными следует считать метод выделения группы наиболее надежных символов в кодах с циклической структурой или выделение специальных позиций в кодовой комбинации из числа младших разрядов координат, которые определяются приемником как детерминированные стирания в канонической структуре кода. Предложен способ защиты номера кластера путем оценки числа циклических сдвигов групп символов, имеющих надежные ИДС в пределах кодового вектора, что обеспечивает по асимптотическим оценкам дополнительный энергетический выигрыш относительно мягкой схемы декодирования от 1 до 3 дБ.

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

1. Агеев, С. А. Декодирование на основе лучших показателей качества приема сигнала / С. А. Агеев, С. А. Бодров, А. А. Гладких, Ю. П. Егоров // Автоматизация процессов управления. 2004. - №1(3). - С.43-46.

2. Агеев, С. А. Декодер с исправлением стираний / С. А. Агеев, А. А. Гладких, Д. А. Кержнер, И. А. Кулешов, В. В. Петров, Г. А. Репин, М. Н. Служивый // Патент на изобретение № 2379841. Бюллетень изобретений. -2009.-№2.

3. Акимов, О; Е. Дискретная математика: логика, группы, графы, фракталы / О. Е. Акимов М.: издатель АКИМОВА, 2005. - 656 с.

4. Архипкин, А. В. Алгоритмы'турбокодирования для российских систем связи / А. В. Архипкин // Электросвязь 2006 - 5. С. 34-36.

5. Балакирский, В. Б. Декодирование сверточных кодов с использованием списков / В. Б. Балакирский, Б. Д. Кудряшов // Проблемы передачи информации. 1989. -Т.25.№1. - С. 16-23:

6. Банкет, В. JI. Цифровые методы в спутниковой связи / В. JI. Банкет, В. М. Дорофеев. М.: Радио и связь, 1988'. - 240 с.

7. Бассалыго, JI. А. Новые верхние границы для кодов, исправляющие ошибки / JI. А. Бассалыго // Проблемы передачи информации. -1965.-T.1.\NM.-G.4M4.

8. Берлекэмп, Э. Р. Алгебраическая теория кодирования / Э. Р. Берлекэмп; пер.с англ. / под ред. Бермана С. Д. М.: Мир, 1971. - 384 с.

9. Берлекэмп, Э. Р. Техника кодирования с исправлением ошибок / Э. Р. Берлекэмп // ТИИЭР. 1980. - Т. 68, №5, - С. 24-58.

10. Блиновский, В. М. Пропускная способность произвольно меняющегося канала при списочном декодировании / В. В.'Блиновский, П. Нарайан, М. С. Пинскер // Проблемы передачи информации. 1995. - Т.31.№2. - С. 3-19.

11. Блох, Э. JI. Модели источника ошибок в каналах передачи цифровой информации / Э. JI. Блох, О. В. Попов, В. Я. Турин. -М.: Связь, 1971. 312 с.

12. Богданов, В. В. Защита от ошибок в сетях ATM / В. В. Богданов, П. С. Вихлянцев, М!. В. Симонов // Информост. 2002. - №3. - С. 20-24.

13. Бородин, JI. Ф. Введение в теорию помехоустойчивого кодирования / JI. Ф.

14. Бородин. М.: Сов. Радио, 1968. - 408 с.

15. Бояринов, И. М. Самопроверяющиеся схемы и алгоритмы декодированиядвоичных кодов Хэмминга, БЧХ-кодов и кодов Рида-Соломона над GF^2m ) /

16. И. М. Бояринов // Проблемы передачи информации. -2008.-Вып.2 С. 32-45.

17. Брауде-Золотарев, Ю.М. Помехоустойчивое кодирование радиоканалов с частотной манипуляцией / Ю. М. Брауде-Золотарев, М.А. Лаврентьев // Радиотехника 2004 - № 6 - С. 12-16.

18. Быховский, М. А. Многочастотные широкополосные сигналы открывают путь к 4G, / М. А. Быховский // Мобильные системы. — 2007. №3. - С. 1215.

19. Ван дер Вандер, Б. JI. Алгебра / Б. JI. Ван дер Вандер. М.: Наука, 1976. -648 с.

20. Ван Трис, Г. Теория обнаружения, оценок И' модуляции / Г. Ван Трис. Том третий. М.: Советское радио, 1977. - 662 с.

21. Варагузин, В. А. Турбо-коды и итеративное декодирование: принципы, свойства, применение / В. А. Варагузин, JI. Н. Протопопов // Мультимедиа. -2000.-№ 12.-С. 33-38.

22. Васильев, К. К. Математическое моделирование систем связи / К. К. Васильев, М. Н. Служивый. .Ульяновск: УлГТУ, 2010. - 128 с.

23. Велдон, И. Дж. Циклические коды, задаваемые разностными множествами / И. Дж. Велдон // Некоторые вопросы теории кодирования. М., 1970. - С.9-21.

24. Вентцель, Е. С. Теория вероятностей и ее инженерные приложения / Е. С. Вентцель, Л. А. Овчаров: / Учеб. пособие для втузов. 2-е изд., стер. М.: Высш.шк., - 2000. - 480 с.

25. Вернер, М. Основы кодирования / М. Вернер. М.: Техносфера, 2004. - 288 с.

26. Воеводин, В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин.' -СПб.:Петербург, 2004. 608 с.

27. Возенкрафт, Дж. Теоретические основы техники связи / Дж. Возенкрафт, И. Джекобе. М.: Мир, 1969. - 640 с.

28. Возенкрафт, Дж. Последовательное декодирование / Дж. Возенкрафт и Рейффен. М.: Иностр. лит-ра, 1963 152 с.

29. Вольфбейн, С. П. Помехи при передаче дискретной информации / С. П. Вольфбейн, Н. Г. Векслер. Киев: Техшка, 1973. 172 с.

30. Галлагер, Р. Теория информации и надежная связь / Р. Галлагер; пер. с англ, под ред. Пинскера М. С. и Цыбакова Б .С. М.: Сов. радио, 1974. - 568 с.

31. Галлагер, Р: Дж. Коды с малой плотностью проверок на четность / Р. Дж.

32. Галлагер. М.: Мир, 1966. — 144 с.

33. Гасанов, Э. Э. Теория хранения и поиска информации / Э. Э. Гасанов, В. Б. Кудрявцев. М.: Физмалит, 2002. - 288 с.

34. Гихман, И. И. Введение в теорию случайных процессов / И. И. Гихман, А. В. Скороход. -М.: Наука, 1965. 654 с.

35. Гладких, А. А. Оценка асимптотической эффективности кода в системе с исправлением сгираний / А А Гладких // ВИМИ сборник «Рипорп». —1975.—№ 17.

36. Гладких, А. А. Устройство для восстановления кодовой последовательности / А. А. Гладких, К. К. Васильев, В. В. Тетерко // Патент на изобретение № 2166235. Бюллетень изобретений, 2001. № 12.

37. Гладких, А. А. Способ декодирования блоковых кодов со стираниями элементов / А. А. Гладких, Н. И. Лычагин, С. А. Агеев; А. И. Мансуров и др. // Патент на изобретение № 2327297. Бюллетень изобретений, 2008. № 17.

38. Гладких, А. А. Устройство исправления стираний / А. А. Гладких, С. Ю. Черторийский, В. В. Тетерко, Р. Ш. Шакуров, Л. Р; Закирова // Патент на изобретение № 2344556. Бюллетень изобретений, 2009. № 2.

39. Гладких, А. А. Основы теории мягкого декодирования избыточных* кодов в стирающем канале связи / А. А. Гладких. Ульяновск: УлГТУ, 2010.-380 с.

40. Гладких, А. А. Декодирование недвоичных кодов в адаптивных системах обмена данными / A.A. ' Гладких, Е.С. Бородина, Р.Ш. Шакуров // Автоматизация процессов управления-2011-№2 (24).—С. 51-55.

41. Думер, И. И. Списочное декодирование двоичных кодов Рида-Маллера первого порядка / И. И. Думер, Г. А. Кабатянский, С. Тавернье // Проблемы передачи информации. 2007. - Т. 43. № 40. - Вып. 3. - С. 66-73.

42. Залогин, Н. Н. Манипуляция характеристиками шумоподобного сигнала в широкополосных системах связи Н. Н. Залогин, В. В. Колесов // Радиотехника 2005,- № 3 - С. 13-18.

43. Зигангиров, К. Ш. К теории списочного декодирования сверточных кодов / К. Ш. Зигангиров, Р. Йоханнессон // Проблемы передачи информации-1996-Т.32.-№1.-С. 122-130.

44. Злотник, Б. М. Помехоустойчивые коды в системах связи / Б. М. Злотник // Статистическая теория связи. М.: Радио и связь, Вып. 31, 1989. - 232 с.f

45. Золотарев, В. В. Алгоритмы кодирования символьных данных в вычислительных сетях / В. В. Золотарев // Вопросы кибернетики. -1985. Вып. 106. - С. 45-51.

46. Золотарев, В. В. Реальный энергетический выигрыш кодирования для спутниковых каналов /. В. В. Золотарев // Тез. докл. 4-й Междунар. конф. «Спутниковая связь ICSC-2000».-M;: МЦНТИ, 2000. Т.2. - С. 20-25.

47. Золотарев, В. В. Помехоустойчивое кодирование. Методы и алгоритмы. Справочник / В'. В. Золотарев, Г. В. Овечкин; под редакцией чл.-кор. РАН Зубарева Ю. Б. М.: Горячая линия-Телеком, 2004'. - 126 с.

48. Зяблов, В. В. Анализ корректирующих свойств итерированных и каскадных кодов / В. В: Зяблов // Передача цифровой информации по каналам с памятью. -М.: Наука, 1970. С. 76-85.

49. Зяблов, В. В. Высокоскоростная передача сообщений в реальных каналах / В. В. Зяблов, Д. JI. Коробков, С. JI. Портной. — М:: Радио исвязь, 1991. 288 с.

50. Зяблов, В. В. Границы сложности декодирования линейных блоковых кодов с помощью решеток / В. В. Зяблов, В. Р. Сидоренко // Проблемы? передачи информации. 1993. - Т. 29.к № 3. - С. 3-9.

51. Зяблов, В. Bt Метод обнаружения ошибочного декодирования с использованием списков / В. В. Зяблов, М. А. Цветков // Информационные процессы. 2004. - Т .4. № 2. - С. 188-201.

52. Зяблов, В. Bi Об оптимальном выборе порога в системе множественного доступа, основанной на перестроении ортогональных частот. / В.' В: Зяблов, Д. С. Осипов // Проблемы передачи информации. 2008. - Т.44. № 2. - С.23-31.

53. Иванов И. В. Классификациями синтез полиномиальных кодеков в системах автоматизированной обработки данных. / И. В. Иванов // Технология конструирования в электронной аппаратуре, 2005, № 4. — С. 19-23.

54. Ибрагимов, Т. А. Асимптотическая теория оценивания. Т. А. Ибрагимов, Р. 3. Хасьминскиш М1: Наука, 1979. - 528 с.

55. Карташевский, В. Г. Обработка пространственно-временных сигналов в каналах с памятью / В. Г. Карташевский. М.: Радио и связь, 2000. - 271 с.

56. Карташевский, В. Г. Итерационное декодирование турбо-кодов в канале с памятью / В. Г. Карташевский, Д. В. Мишин // 3-я Международная конференция и выставка «Цифровая обработка сигналов и ее применение». М, 2000. - С. 65-68.

57. Карташевский, В. Г. Прием кодированных сигналов в каналах с памятью / В. Г. Карташевский, Д. В. Мишин. М.: Радио и связь, 2004 - 239 с.

58. Кларк, Дж. Кодирование с исправлением ошибок в системах цифровой связи / Дж. мл. Кларк, Дж. Кейн; пер. с англ. — М.: Радио и связь, 1987. 392 с.

59. Кловский, Д. Д. Передача дискретных сообщений по радиоканалам / Д. Д.

60. Кловский. —М.: Связь, 1969. 375 с.

61. Кловский, Д. Д. Прием сигналов со сверточным кодированием в канале с межсимвольной интерференцией / Д. Д. Кловский, В. Г., Карташевский; С. А. Белоус // Проблемы передачи информации. 1991. - № 2. - С. 37—48.

62. Коржик, В. И: Помехоустойчивое кодирование дискретных сообщений вчканалах со случайной структурой / В: И. Коржик, Л. М. Финк. М.: Связь, 1975.-272 с.

63. Красносельский // «Электросвязь»: № 1- 2001. С. 17-20;

64. Кремер, Н. Ш. Теория;вероятностей?и математическая-статистика: Учебникдля вузов. 2-е изд., перераб. и доп.- / Е/. Ш: Кремер. - М:: Юнити-Дана, 2004. -573 с.

65. Крылов, В. И. Методы приближенного преобразования Фурье и обращенияпреобразования^ Лапласа / В. И. Крылов, Н. С. Скобля. М1: Наука, 1974. -¡5 220 с.I

66. Кудряшов, Б. Д. Списочное декодирование в каналед с гауссовскимшумом./ Б. Д. Кудряшов // Проблемы передачи информации.- 1991.Т.27.№ 3. С. 30-38.

67. Левин, Б. Р. Теоретические основы статистической радиотехники. Книгапервая / Б. Р. Левин. -М.: Советское радио, 1974. 552 с.

68. Лычагин, Н. И. Неалгебраическое декодирование групповых кодов в1.стирающем канале связи / Н. И. Лычагин, С. А. Агеев, А. А. Гладких, А. В.

69. Васильев // «Системы и средства связи телевидения^ и радиовещания».- №1,2.-2006.-С.49-55.

70. Мак-Вильямс, Ф. Дж. Перестановочное декодирование систематических1кодов / Ф. Дж. Мак-Вильямс // Кибернетический сборник. Новая серия, 1965,1. Вып. 1.-С. 35-37.

71. Мак-Вильямс, Ф. Дж. Теория кодов, исправляющих ошибки / Ф. Дж. Мак-Вильяме, Н. Дж. А. Слоэн. -М.: Связь, 1979. 354 с.

72. Магемагака. Большой энциклопедический словарь / Гл. ред. Прохоров ЮВ. 3-е изд.-М.: Большая Российская энциклопедия, 1998: — 848 с.

73. Месси Дж. Пороговое декодирование / Дж. Месси. М.: Мир, 1966.- 284 с.

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

75. Назаров, Л.Е. Алгоритмы посимвольного приема двоичных блоковых кодов / Л.Е. Назаров //Радиотехника.- 2004- №6- С. 28-35.

76. Осмоловский,, С. А. Стохастические методы передачи данных / С. А. Осмоловский.-М.: Радио и связь, 1991. 240 с.

77. Питерсон, У. Коды, исправляющие ошибки / У. Питерсон, Э. Уэлдон; пер. сангл.; под редакцией Р. Л. Добрушина и С. Н. Самойленко. М.: Мир; 1976. 594 с.

78. Прокис, Джон. Цифровая связь / Джон. Прокис; пер. с англ.; под редакцией Д. Д. Кловского.- М;: Радио и связь, 2000; 800 с.

79. Пугаче, В. С. Теория стохастических систем: Учебное пособие / В. С. Пугачев, И. II. Синицын. М.: Логос, 2004. - 1000 с.

80. Скляр, Бернард. Цифровая связь. Теоретические основы и практическое применение / Бернард Скляр Изд. 2-е, испр. пер. с англ. — М.: Издательский' Гдом «Вильяме», 2003. 1104 с.

81. Сеньковская, Е. А. Вопросы кодирования в односторонних радиоканалах передачи информации ОНЧ-диапазона / Е. А. Сеньковская // Радиотехника— 2003.-№3.-С. 32-36.

82. Советов, Б. Я. Моделирование систем ./ Б. Я. Советов, С. А. Яковлев 2-е изд. М;: Высш. шк., 1998. - 319 с.

83. Тихонов, В; И. Марковские процессы / В. И. Тихонов, М. А. Миронов. М.: Радио и связь, 1977. - 448 с.

84. Федеральный- справочник. Связь и массовые коммуникации в России; — М. : Центр стратегического партнерства, 2009. 305 с.

85. Финк, JI. М.Теорияпередачидискретных сообщений / JI. М. Финк. М.: Сов. радио, 1970.-728 с.

86. Форни, Д- Каскадные коды/Д; Форни:-М;: Мир, 1970;-207 с.

87. Форни, Д; Экспоненциальные границы' для; ошибок в системах со стиранием; декодированием списком и решающей обратной связью / Д. Г. Форни;// Некоторые вопросы теории кодирования. М: 1970, - С. 166-205.

88. Чуднов, А. М. Помехоустойчивость, линий; и сетей связи в условиях оптимизированных помех / А. М. Чуднов; под редакцией. А. П. Родимова. -Л.: ВАС, 1986,- 84 с. ''

89. Шлома, A. Mi Новые алгоритмы формирования и обработки сигналов в системах подвижной связи / А. М. Шлома, М; Г. Бакулин, В; Б. Крейнделин, А. П: Шумов: М:: Горячая линия - Телеком, 2008. - 344 с.

90. Шувалов, В. П. Прием сигналов с оценкой их качества / В. П. Шувалов. М.: Связь, 1979.-240 с.

91. Харари Ф: Перечисления графов; / Ф. Харари, Э. Палмер .- М.: Мир, 1977.-324 с.

92. Bèrrou С., Adde P., Angui Е., Faudeil S. A low complexity soft-output viterbi decoder architecture // in Proc. of the Intern: Conf. on Commun. 1993. - May.106.107.108.109.110.111. 112.113.114.115.116.1. P. 737- 740.

93. Damen O., Chkeif A. and Belfiore J. C. Lattice code decoder for space-time codes, IEEE Commun. Letters, vol. 4, pp. 161-163, May 2000.

94. MacKay D. J. C. Good error correcting codes based on very sparse matrices, IEEE Trans. Inform. Theory, vol.45, pp.399-431, March 1999.

95. Sudan M. Decoding of Reed-Solomon Codes Beyong the Error-Correction Bound, J. Complexity, vol. 12, pp. 180- 193, Dec. 1997

96. Takeshita O. Y., Collins O.M., Massey P.C., Costello D.J. A Note on Asymmetric Turbo-Codes // IEEE Communication Letters. 1999. - March. - Vol.3. - P. 6971.

97. Takeshita O. Y., Costello D.J., Jr. New classes of algebraic intervers for turbocodes // in Proc. of IEEE Intern. Symp. on Inf. Theory, (MIT, Cambrige, MA USA). 1998. Aug. - P.419.

98. Viterbo E. and Boutros J. A universal lattice code decoder for fading channels, IEEE Trans. On Inform. Theory, vol. 45, pp. 1639-1642, July 1999.