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

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

ООЗОБ742Б

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

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

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

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

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

Ульяновск - 2006

003067426

Работа выполнена на кафедре «Телекоммуникации» Ульяновского государственного технического университета (УлГТУ)

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

доктор технических наук, профессор Васильев Константин Константинович

Официальные оппоненты:

доктор технических наук, профессор кафедры «Информационные технологии» Ульяновского государственного университета Кумунжиев Константин Васильевич,

кандидат технических наук, доцент кафедры «Информатика» Ульяновского высшего авиационного училища гражданской авиации Пятаков Анатолий Иванович

Ведущая организация:

Федеральный научно-производственный центр открытое акционерное общество «Научно-производственное объединение «Марс», г. Ульяновск

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

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

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

Автореферат разослан « £9> » (¿аЛь^ л 2006 г.

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

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

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

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

2. Впервые разработан алгоритм адаптивной процедуры плавного изменения интервала стирания в зависимости от характера изменения индексов достоверности, позволяющий повысить достоверность приема информации при низких соотношениях сигнал-шум (патент РФ на изобретение № 2209519).

3. Впервые сформулирован и обоснован способ декодирования систематических кодов с использованием алгебры логарифмических отношений правдоподобий и свойств графа Таннера, позволяющий повысить индексы достоверности информационных бит за счет мощности проверочных символов (патент РФ на изобретение № 2256294).

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

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

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

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

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

Вышеуказанные результаты работы приняты для практического использования в разработках ФНПЦ ОАО «НПО «Марс», в 29 Испытательном полигоне (войск связи) и в 16 Центральном научно-исследовательском испытательном институте связи МО РФ.

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

Личный вклад автора

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

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

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

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

Основные положения диссертационной работы докладывались и обсуждались на 61-й научной сессии Российского НТОРЭС им. A.C. Попова г. Москва 2006 г.

В трудах 4-й Всероссийской научно-прак. конференции (с участием стран СНГ) «Современные проблемы создания и эксплуатации радиотехнических систем»- Ульяновск: УГТУ, 2004 г.

В трудах IX Военной НТК «Актуальные вопросы совершенствования техники и систем военной связи на основе современных телекоммуникационных технологий» - Ульяновск: 29 ИП МО РФ, 2004.

В трудах Всероссийской научно-практической конференции (с участием стран СНГ) «Современные проблемы создания и эксплуатации радиотехнических систем», Ульяновск, УГТУ, 1998.

В статье: Декодирование на основе лучших показателей качества приема сигнала // «Автоматизация процессов управления», 2004, №1(3), С.43-46.

В статье: Неалгебраическое декодирование групповых кодов в стирающем канале связи // «Системы и средства связи, телевидения и радиовещания», № 1,2,2006.-С 49-55.

Новизна технических решений закреплена в патентах РФ на изобретения № 2209519 от 27.7.2003 г. и № 2256294 от 10.7.2005 г.

Публикации

По теме диссертации опубликовано 10 работ, в том числе 6 статей в сборниках научных трудов и материалов конференций, 1 статья в журнале «Автоматизация процессов управления», 1 статья в журнале «Системы и средства связи, телевидения и радиовещания», входящем в перечень ВАК РФ, и в двух патентах РФ на изобретения.

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

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

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

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

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

Обобщенная модель непрерывного канала связи рассматривается с общепризнанных позиций: математически такой канал определяется совокупностью множества передаваемых сигналов V, множества принимаемых сигналов С/ и условного распределения вероятностей Р(//у) 1еВ, уеУ, заданного на некоторых подмножествах множества и, где В - а -алгебра борелевского множества ¡У.

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

где h(t, г) - случайная функция двух переменных, а случайная функция, не зависящая от входного сигнала v(t) и функции h(t, г).

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

u(t) = Lv + n(t) = \h(t, r)v(t - r)dr + n(t);

(1)

-00

-4Щ ~p

№

Рисунок 1 - Условные ПРВ для двух сигналов с симметричным интервалом стирания

В такой модели декодер получает две жестко синхронизированные последовательности. Первая последовательность информационная. Она представляется, символами ¿¡,$2,Вторая, синхронная с первой по номерам следования символов, последовательность в которой

sJ = О при отсутствии сигнала стирания и = 1 при наличии такого сигнала.

Условная плотность распределения вероятностей двух гауссовских сигналов щ и м2 показывает, что значение вероятности ложного стирания Р/л. ПРИ симметричном интервале стирания и передаче Щ в условиях

гауссовских шумов всегда будет превосходить значение вероятности правильного стирания р{ 5 :

О р

\р(6\щ)с1б < \р{6\щ)с15. (2)

-Р О

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

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

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

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

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

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

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

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

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

На основе проведенного анализа предметной области сформулированы главные задачи исследований:

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

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

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

Во второй главе на основе аппарата дискретных марковских процессов разработана математическая модель двоичного стирающего канала связи, позволившая определить выражение для корреляционной функции К@(т) стационарного потока #(?) информационных символов и стертых позиций:

2Л гх- 32 л2

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

неопределенности, выражения кх = р(Л - ^ +1,5р) и к^ = р{р + ^ - 1,5р)

определяют степень убывания Л и ц при введении интервала стирания, параметр | г | характеризует время. Показано, что значимые значения корреляционной функции для стирающего канала связи, при рф 0, сохраняются на протяжении 3-4 временных интервалов. Полученный результат имеет важное прикладное значение, так как позволяет обосновать параметры

схемы, формирующей целочисленные оценки надежности символов на основе

потока стираний.

1

а з □ 6 04 О 2

°-б -4 -2 0 2 4 б

•Е

Рисунок 2 - Изменение функции корреляции при введении стирающего канала связи (Л — 0,25 )

Для определения оценки надежности символа назначаются два скользящих окна размерами К{ и К2 бит каждое, при этом = К2 ■ Совместный поток информационных символов и поток стираний разделяются. В потоке стираний не стертым в первичной последовательности информационным символам присваивается значение ноль, а стертым позициям символов присваивается значение единица. Окна следуют по выделенной из потока данных последовательности стираний одно за другим, перекрываясь между собой, на интервале одного бита. Если этот символ - стирание, то от общей оценки отнимется единица. Оценка надежности вырабатывается для символа, попавшего в оба окна по принципу подсчета числа стираний в окнах Кх и К2. Первоначально каждому окну присваивается вес АГ]+1 и АГ2+1- Если в окно попало £ стираний, то вес окна уменьшается на эту величину. Общая оценка определяется как сумма оценок первого и второго окна:

Если на приемной стороне образовалась последовательность символов, пронумерованная относительно анализируемого символа х( по оси времени влево и вправо

(4)

хI

ч-З'

тогда в окно при АГ,= 3 попадают символы х1',х1_^\х{_2> а в окно К2 -СИМВОЛЫ Х(+2~,Х{+\\х1.

Минимальной оценкой для х( в указанных условиях оказывается оценка 1 (все символы в окнах стерты и равны единицам), а максимальной оценкой может служить оценка 8 (все символы в окнах равны нулю). Легко убедиться в том, что оценки меньшего веса совпадают со стираниями и в силу этого могут служить индексами достоверности для принятых символов. После оценки символа Х(, при получении очередного значения х/+4, приемник сдвигает

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

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

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

- оценки носят целочисленный характер;

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

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

где т]- интенсивность импульсной помехи, г- текущее время, у/й1-значение фазы сигнала на приеме, р - значение интервала стирания. Получено графическое представление действия импульсной помехи в стирающем канале связи (рисунок 3).

S1I1T

sin y/oi<-l±p,

т

(5)

б

J

4

ID

12

14

T

Рисунок 3 - Влияние импульсной помехи на ФМ сигнал

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

На рисунке 4 приведена диаграмма при воздействии импульсной помехи малой интенсивности. Заметна положительная роль стирающего канала в

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

п 1 1 а у п и 1 77 = 15 - пр=0'5 с и !

1 ^ 6 1 1 п и | Л " и 1 Г -

О 5 10 15 20 25 30

Рисунок 5 - Влияние импульсной помехи большой интенсивности

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

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

В третьей главе разрабатывается способ обработки комбинаций избыточного кода на основе кластерного анализа.

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

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

В работе доказано, что число двоичных символов, определяющих признак кластера равно / и Ой/йк, где к - число информационных символов в кодовом векторе группового кода, и число комбинаций такого кода, входящих в кластер одного признака, определяется соотношением 2к'/. При / = 0 все кодовые векторы входят в один кластер (традиционный подход).

Номера комбинаций прямого и дуального кода, упорядоченные по циклическим сдвигам строки с номером Х"'к порождающей матрицы систематического кода С, подчиняются соотношению 1е{Х) +1нт =2' -1, а номера их кластеров Ке(Х) + КНХ) = 2' -1.

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

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

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

Показано что, каждый разряд любой координаты X или У имеет вес

кратный значению 2', где г е # и {О}, ¡<(к-/)/2. Это означает, что при восстановлении кодового вектора по признаку кластера значения координат X

или У мало изменяются при замене в младших разрядах единиц на нули и наоборот. В таблице 1 приведен пример разбиения гада £ЧХ на кластеры с указанием координат.

Таблица 1 - Разбиение комбинаций кода БЧХ с £ (У) =2467а

№ комбинации | Группа 1 (координата XV Группа 2 (координата У) Номер кластера в дйончлим коде Прямые координаты (Х,У) Инвариантные тт № кластера

0 0 '0 0 .0 0 0 0 0 0 0 0 0 Ж ■ 9 0 0 0 0 0 0

] 0 0. 0 0: 1 0 1 0 0 1 1 0 ■ С 1 2 38 ж, Ш 7

2 6 0 0 1 0 . г 0 0 1 1 0 1 ■г- ,1 0 5 13 40' 44 6

3 ■о 0 0 1 1- г 1 0 1 0 I 1 0 0 1 7 43 ..56 53: 1

4 .0 0 1 0 0 6 1 1 1 1 0 1 0 1 1 8 61 ■4 47- 3

5 ■0 ■■О' г ■0- 1 0- 0 1 1 0 1 1 1 ■ 0 0 10 27 20. 54. 4

6 0 0 I 1 о 1- 1 1 0 0 0 0 1 0 . 1 13 48 Ш ■3 ' 5

7 0 0 1 I .1 ш? 0 1 0 1 1 0 0 ц;. ■ 0 15 22 60 26 2

§ 0 . 1 0: 0 0 1 1 1 3 0 1 0 : г ■1- 0 17 58 ■ 34 ; 23: 6

9 0 г 0 .0 1 1. 0 [ 1 1 0 0 ■о- 0 л. 19 28 .50 • 14 1

10 0 1 0 1 ■0 0 1 1 0 1 ! 1 о ■ б. 20 55 № 59 0

11 0 г 1 " 1: ■ 0 0 1 0 0 0 1 1 ■ т 22 17 ■26 34" 7

12 :0 ■Ц" "1 ■0. ■о 1 0 0 0 1 1 ] - 1 : 0 '1 - 25 7 38 56 5

13 % I г 0 1 ( I 0 0 0 0 1 0 I 0 27 33 54. 33 2

14 0; ■1' 1 г 0 0 0 0 1 0 1 0 .0 .1 1 28 10 $4 20 3

15 0. ■ Г ■ 1. 1 •о. 1 0 1 1 0 0 ■1 : О- ■ 0 30 44 30 ' 13 4

16 X 0 0 0 ■0 1 0 1 0 0 1 1 ■о . ]/ 1 33 19 3;- 50 . 3

17 1 0 0 0 1 1. 1 1 0 1 0 1 •и 0 0 35 53 49 43-. 4

18 .1 0- 0 1 ■0 0 0 1 1 1 ! 0 1 : о: 1 36 30 9 30 5

19 .1 о 0 1 1 0 1 1 1 0 0 0 0 .Г 9. 38 56 25 ■г ..-. 2

20 Ш ()■■ "Г 0: 0 1 1 0 1 1 1 0 ■ 0 1 О: 41 46 4Г 29 0

21 1 0 ■ 1 0 ■1 1 0 0 1 0 0 0 -1 ; 1 I 43 8 ' 55 ; -4 : 7

22 1 в- 1 1 0': 0 1 0 0 0 1 1 1 ; 1 ■й. 44 35 : 49 6

23 1 1 1 1 0 0 0 0 1 0 1 0 о а 46 5 29 40 1

24 1 •л 0 0 0, 0 1 0 1 0 0 1 I V 48 41 3. .37 ' 5

25 1 1 0 0 ■1 0' 0 0 1 1 1 1 '0 ' 1. .0 50 14 1-9 60 : 2

26 ■1 .1 о. 1 ■0 1. 1 0 0 1 0 0 О • ■ 1 ■Д.. 53 36 ■ 43 : 9: ; 3

27 1 ■д- 0 1 1 0 0 0 0 1 0 1 ■ Ч) 0 55 2 ' $ > 16 : 4

28 ь 1. ; 1 о 0 .О- 0 1 0 1 0 0 Н1:;' "0 56 20 Щ 6

29 р % 0 [ 0 1 1 0 0 1 0 0' Щ 1 58 50 2? ; 19. 1

30 % 1 .1- .1 0. 0 1 1 0 0 1 ' 0; •0 61 25 .4?.. 38 0

31 1 1 Ш ! к •1' 1 1 1 1 1 1 Р] ё ■ 63 63 б:- 63 7

70 60 50 40 30 20 10 О 70 60 50 40 30 20 10 0 70 60 50 40 30 20 10 0 70 60 50 40 30 20 10 0

10 20 30 40 50 60 70

10 20 30 40 50 60 70

70 60 50 40

зо 20 10 0

10 20 30 40 50 60 70 0

70

Кластер №2

Л 58; 56

/

> 7,33

22

•50,14 ----

Кластер № 6

Л 7, 53"

/ \

/ N^44, 35

—

1 2 30 4 5 6 70

Кластер № 5

«Я 41

\

V /

, 7

10 20 30 40 50 60 70

я- 61 Кластер N8 3

N

\

\ ** >53, 36

\ И

ч 9

Кластер N2 4

53

.55

10 20 30 40 50 60 70

10 20 30 40 50 60 70

Рисунок 6 - Созвездия комбинаций в кластерах кода БЧХ (15,5,7) с / = 3

Заметно, что все комбинации кода находятся в уникальных отношениях к точкам с координатами (0;0) и (2к -\\2к -1). Симметрия второго рода между отдельными кластерами наглядно представляет конфигурации комбинаций прямого и дуального кода. Это свойство, в случае необходимости, позволяет в два раза снизить объем памяти декодера, поскольку симметричные комбинации дуального кода могут быть вычислены по комбинациям прямого кода по тос!2* -1.

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

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

разрядов (/7 = 1...(к-/)/2) могут быть восстановлены при условии, что старшие разряды координат X и У приняты достоверно.

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

Для представленного примера границами будут служить линии:

(Х = 0;Г = 0 и Х = 2*-1;Г = 2*-1);

(Х = 2*;Г = 2* и X = 20-1; 7 = 2^-1). (6)

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

Пример разбиения плоскости кластера на области показан на рисунке 7.

70 60 50 40 30 20 10 о

О 10 20 30 40 50 60 70

Рисунок 7 - Пример разбиения кластера на области

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

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

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

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

Z(¿,)+I(¿2) * (-1)1+" х sigfiL(dl)] х Sig^L(d2)] х ппп^ОД);,\L(d2 )¡), (7)

здесь функция sign(•) возвращает знак своего аргумента; L(dt) - индекс достоверности символа, участвующего в формировании проверочного бита; L(d2) - индекс достоверности проверочного символа; п - число свернутых среди информационных разрядов единиц.

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

Вероятность ошибки яа 6irr

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

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

В четвертой главе представлены методика и результаты моделирования алгоритмов работы декодера и оценка их эффективности с использованием критерия: достоверность в обмен на полосу пропускания. Особое внимание уделено проблеме обработки данных блоковыми кодами в каналах с низкими эксплуатационными характеристиками. Алгоритм декодирования рассматривался для канала с АБГШ без использования процедуры перемежения символов. Адекватность модели проверялась на контрольных примерах варианта системы без стирания элементов, представленной в библиотеке МАТЬАВ. Предполагается, что последующее включение процедуры перемежения символов однозначно будет способствовать улучшению характеристик декодера. Предлагаемый алгоритм представлен на рисунке 9.

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

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

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

Рисунок 9 - Алгоритм декодирования 19

Таблица 2 - Оценка выигрыша

Соотношение сигнал-шум 1дБ 2дБ ЗдБ 4дБ ЗдБ 6дБ

Выигрыш в дБ относительно схемы алгебраического декодера 2,1 1,8 1,1 0,7 0,3 0,1

Выигрыш в дБ относительно схемы без кодирования 2,7 2,5 2,1 1,9 1,4 1,3

Указанная тенденция сохраняется для других систематических кодов.

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

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

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

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

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

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

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

7. Методом имитационного моделирования проверена эффективность предложенных алгоритмов повышения достоверности передачи цифровой

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

Список публикаций

1. Лычагин Н.И. Неалгебраическое декодирование групповых кодов в стирающем канале связи / Н.И. Лычагин, С.А. Агеев, A.A. Гладких, A.B. Васильев // «Системы и средства связи телевидения и радиовещания», № 1,2, 2006. - С 49-55.

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

3. Визиренко А.Б., Тетерко В.В.. Гладких A.A., Климентьев П.В., Сергеев В.А. Декодер с изменяемым интервалом стирания. Патент РФ на изобретение № 2209519, Официальный бюллетень «Изобретения. Полезные модели» № 21, 2003.

4. Гладких A.A., Васильев К.К., Агеев С.А., Егоров Ю.П., Бодров С.А., Маслов A.A. Устройство восстановления кодовой последовательности. Патент РФ на изобретение № 2256294, Официальный бюллетень «Изобретения. Полезные модели» № 19,2005.

5. Тетерко В.В., Гладких A.A. Преобразование кодов Рида-Соломона в системах с изменяющимися параметрами// Труды Всероссийской научно-практической конференции (с участием стран СНГ) «Современные проблемы создания и эксплуатации радиотехнических систем» (Ульяновск, УГТУ, 1998, с. 75-76).

6. Тетерко В.В., Гладких A.A. Методика получения оценок надежности символов кодовых последовательностей // Труды Всероссийской научно-практической конференции (с участием стран СНГ) «Современные проблемы создания и эксплуатации радиотехнических систем» (Ульяновск, УГТУ, 1998, с. 77-79).

7. Тетерко В.В., Гладких A.A. Декодирование на основе показателей максимума правдоподобия // Труды IX Военной НТК «Актуальные вопросы совершенствования техники и систем военной связи на основе современных телекоммуникационных технологий» - Ульяновск: 29 ИП МО РФ, 2004, с. 9395.

8. Тетерко В.В., Гладких A.A. Итеративное декодирование в стирающем канале связи // Труды 4-й Всероссийской научно-прак. конференции (с участием стран СНГ) «Современные проблемы создания и эксплуатации радиотехнических систем»- Ульяновск: УГТУ, 2004, - с 77-80.

9. Тетерко В.В., Гладких A.A. Декодирование с использованием оценок надежности в стирающем канале связи // Труды 31-й научно-практической конференции - Рязань, 2006, с. 50-52.

10. Гладких А.А., Тетерко В.В. Применение кластерного анализа при декодировании блоковых кодов // Труды 61-й научной сессии Российского НТОРЭС им. А.С. Попова-Москва, 2006,- с. 381-383.

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

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

Подписано в печать 21.12.2006. Формат 60x84/16. Бумага офсетная. Усл. печ. л, 1,00. Тираж 100 экз. Заказ/«*

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

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

ВВЕДЕНИЕ.

Глава 1. МОДЕЛИ, МЕТОДЫ И АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ В СТОХАСТИЧЕСКИХ КАНАЛАХ СВЯЗИ.

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

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

1.2.1. Каноническая схема цифровой системы связи.

1.2.2. Модели непрерывных каналов связи.

1.2.3. Оптимальный прием в непрерывном канале.

1.2.4. Субоптимальные отображения каналов связи.

1.3. Модели полунепрерывных каналов связи.

1.3.1. Модель канала связи со стиранием элементов.

1.3.2. Функции правдоподобия для двоичного симметричного канала связи

1.3.3. Последовательный детектор максимального правдоподобия.

1.3.4. Способ получения оценок надежности символов в стирающем канале связи.

1.4. Анализ методов декодирования групповых кодов.

1.4.1 Алгебраические методы декодирования.

1.4.2 Неалгебраические методы декодирования.

1.4.3 Мягкое декодирование.

1.5. Выводы.

Глава 2. МОДЕЛИ НЕГАУССОВСКИХ КАНАЛОВ СВЯЗИ СО СТИРАНИЯМИ.

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

2.2. Модель марковского двоичного канала со стираниями.

2.3. Стирающий канал при воздействии импульсных помех.

2.4. Параметры модели дискретного канала со стираниями.

2.5. Выводы.

Глава 3. РАЗРАБОТКА АЛГОРИТМОВ НЕАЛГЕБРАИЧЕСКОГО ДЕКОДИРОВАНИЯ СИСТЕМАТИЧЕСКИХ КОДОВ.

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

3.2. Кластерный подход к декодированию полиномиальных кодов.

3.3. Декодирование на основе лучших показателей приема сигнала.

3.4. Синтез алгоритмов функционирования декодера.

3.5. Выводы.

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

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

4.2. Модель Гауссовского канала связи со стиранием элементов.

4.2.1. Принцип моделирования непрерывного канала связи с АБГШ.

4.2.2. Моделирования системы связи с избыточным кодированием.

4.3 Оценка эффективности разработанных алгоритмов методом имитационного моделирования.

4.4. Выводы.

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

2. Впервые разработан алгоритм адаптивной процедуры плавного изменения интервала стирания в зависимости от характера изменения индексов достоверности, позволяющий повысить достоверность приема информации при низких соотношениях сигнал-шум (патент РФ на изобретение № 2209519).

3. Впервые сформулирован и обоснован способ декодирования систематических кодов с использованием алгебры логарифмических отношений правдоподобий и свойств графа Таннера, позволяющий повысить индексы достоверности информационных бит за счет мощности проверочных символов (патент РФ на изобретение №2256294).

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

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

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

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

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

Вышеуказанные результаты работы приняты для практического использования в разработках ФНТТЦ ОАО НПО «Марс», в 29 Испытательном полигоне (войск связи) и в 16 Центральном научно-исследовательском испытательном институте связи МО РФ.

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

Личный вклад автора

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

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

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

Основные положения диссертационной работы докладывались и обсуждались на 61-й научной сессии Российского НТОРЭС им. А.С. Попова г. Москва 2006 г.

В трудах 4-й Всероссийской научно-прак. конференции (с участием стран СНГ) «Современные проблемы создания и эксплуатации радиотехнических систем»- Ульяновск: УГТУ, 2004 г.

В трудах IX Военной НТК «Актуальные вопросы совершенствования техники и систем военной связи на основе современных телекоммуникационных технологий» - Ульяновск: 29 ИП МО РФ, 2004.

В трудах Всероссийской научно-практической конференции (с участием стран СНГ) «Современные проблемы создания и эксплуатации радиотехнических систем», Ульяновск, УГТУ, 1998.

1.В статье: Декодирование на основе лучших показателей качества приема сигнала // Автоматизация процессов управления, 2004, №1(3), С.43-46, а также в статье: Неалгебраическое декодирование групповых кодов в стирающем канале связи//«Системы и средства связи телевидения и радиовещания», № 1,2, 2006- С 49-55Новизна технических решений закреплена в патентах РФ на изобретения № 2209519 от 27.7.2003 г. и № 2256294 от 10.7.2005 г.

Публикации

По теме диссертации опубликовано 10 работ, в том числе 6 статей в сборниках научных трудов и материалов конференций, 1 статья в журнале «Автоматизация процессов управления», 1 статья в журнале «Системы и средства связи, телевидения и радиовещания», входящем в перечень ВАК РФ, и в двух патентах РФ на изобретения.

Положения, выносимые на защиту

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

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

3. Разработан способ неалгебраического декодирования систематических кодов за счет разбиений множества разрешенных комбинаций на кластеры и представления их в форме созвездий в декартовой системе координат двумерного евклидова пространства.

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

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

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

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

4.4. Выводы

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

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

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

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

ЗАКЛЮЧЕНИЕ

Основными результатами диссертации являются:

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

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

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

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

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

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

112

Доказана возможность исправления стираний, кратности п - к.

7. Методом имитационного моделирования проверена эффективность предложенных алгоритмов повышения достоверности передачи цифровой информации в широком диапазоне изменений параметра сигнал-шум. Показано, что при низких значениях этого параметра обеспечивается энергетический выигрыш до 2 дБ, и по мере повышения отношения сигнал-шум их эффективность сходится к эффективности используемого избыточного кода.

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

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

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

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

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

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

7. Боккер П. Передача данных: Техника связи в системах телеобработки данных / П. Боккер.- В 2-х томах. Том 2. Устройства и системы: Пер с нем./ Под ред. Д.Д. Кловского. -М.: Радио и связь, 1981. 256 е.: ил.

8. Быков В.В. Цифровое моделирование в статистической радиотехнике / В.В. Быков М.: Сов. радио, 1971.-326 с.

9. Бородин Л.Ф. Введение в теорию помехоустойчивого кодирования / Л.Ф. Бородин. М.: Сов. радио, 1968.-408 с.

10. Ван дер Вандер Б.Л. Алгебра / Б.Л. Ван дер Вандер. М.: Наука, 1976.648 с.

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

12. Васильев К.К. Методы обработки сигналов. Учебное пособие / К.К. Васильев. Ульяновск: УлГТУ, 2001. - 78 с.

13. Васильев К.К. Прием сигналов при мультипликативных помехах / К.К. Васильев. Изд-во Сарат.ун-та, 1983. - 128 с.

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

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

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

17. Визиренко А.Б. Декодер с изменяемым интервалом стирания / А.Б. Визиренко, В.В. Тетерко, А.А. Гладких, П.В. Климентьев, В.А. Сергеев. Патент РФ на изобретение № 2209519 от 27 июля 2003.

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

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

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

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

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

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

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

25. Гильберт Э.Н. Пропускная способность канала с пакетами ошибок /Э.Н. Гильберт//Кибернетический сборник. -М.: Мир, 1964, № 9, С 109-122.

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

27. Гладких А.А. Устройство восстановления кодовой последовательности /

28. A.А. Гладких, К.К. Васильев, С.А. Агеев, Ю.П. Егоров, С.А. Бодров, А.А Маслов, патент РФ на изобретение № 2256294.

29. Гоппа В.Д. Новый класс линейных корректирующих кодов / В.Д. Гоппа // Проблемы передачи информации, 1970.-Е. 6, Вып 3-С.24-30.

30. Гренадер У. Краткий курс вычислительной вероятности и статистики / У.Гренадер, В. Фрайбергер. -М.: Наука, 1978.-192 с.

31. Дадаев Ю.Г. Теория арифметических кодов / Ю.Г. Дадаев. -М.: Радио и связь, 1981.- 272 е.: ил.

32. Зигангиров К.Ш. Процедуры последовательного декодирования / К.Ш. Зигангиров. -М.: Связь, 1974. 264 е.: ил.

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

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

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

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

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

38. Зяблов В.В. Высокоскоростная передача сообщений в реальных каналах /

39. B.В. Зяблов, Д.Л. Коробков, С.Л.Портной. М.: Радио и связь, 1991. - 288 с.

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

41. Ипатов В.П. Периодические дискретные сигналы с оптимальными корреляционными свойствами / Ипатов В.П. -М.: Радио и связь, 1992.-152 е.: ил.

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

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

44. Кловский Д.Д. Передача дискретных сообщений по радиоканалам / Д.Д. Кловский. -М.: Связь, 1969. -375 с.

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

46. Клюев Н.И. Информационные основы передачи сообщений / Н.И. Клюев. -М.: Сов. радио, 1966. 275 с.

47. Колмогоров А.Н. Математическая логика / А.Н. Колмогоров, А.Г. Драгалин. -М.: УРСС, 2004.- 240 с.

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

49. Коржик В.И. Расчет помехоустойчивости систем передачи дискретных сообщений.: Справочник / В.И Коржик., JI.M Финк., К.Н Щелкунов; под ред. JI.M. Финка. -М.: Радио и связь, 1981.-232 с.

50. Красносельский М.Н. Турбокоды: принцип и перспективы / М.Н. Красносельский // «Электросвязь», № 1,2001.-С 17-20.

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

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

53. Латхи Б.П. Системы передачи информации / Б.П. Латхи. М.: Связь, 1971.- 320 е.: ил.

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

55. Лившиц А.Р. Многоканальные асинхронные системы передачи информации (элементы теории) / А.Р. Лившиц, А.П Биленко. М.: Связь, 1974.- 232 е.: ил.

56. Лычагин Н.И. Неалгебраическое декодирование групповых кодов в стирающем канале связи / Н.И. Лычагин, С.А. Агеев, А.А. Гладких, А.В. Васильев // «Системы и средства связи телевидения и радиовещания», № 1,2, 2006.-С 49-55.

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

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

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

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

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

62. Назаров А.Н. Модели и методы расчета структуно-сетевых параметров ATM сетей А.Н. Назаров. -М.: Горячая линия-Телеком, 2002.-256 е.: ил.

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

64. Привалов И.И. Аналитическая геометрия / И.И. Привалов. М.: Наука, 1966.- 272 с.

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

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

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

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

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

70. Тонг С.Я. Методы синхронизации при передаче сообщений двоичными циклическими кодами / С.Я. Тонг // Некоторые вопросы теории кодирования. -М.: 1970, С.91-101.

71. Федоров Р.Ф. Стохастические преобразования информации / Р.Ф. Федоров, В.В. Яковлев, Г.В. Добрис. JI.: Машиностроение, Ленингр. отд, 1978.-304 е.: ил.

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

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

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

75. Фрид Э. Элементарное введение в абстрактную алгебру / Э. Фрид; пер. с венгер. Ю.А. Данилова. М.: Мир, 1970.- 260 е.: ил.

76. Шеннон К.Е. Математическая теория связи / К.Е. Шеннон // Работы по теории информации и кибернетики.- М.: Иностранная литература, 1963.- 476 е.: ил.

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

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

79. Элайес П. Сети гауссовских каналов и их применение к системам с обратной связью / П. Элайес// Некоторые вопросы теории кодирования. М.: 1970, С.205-230.

80. Berlekamp E. R. "Bounded Distance + 1 Soft-Decision Reed-Solomon Decoding", IEEE Trans. Info. Theory, vol. 42, no. 3, pp. 704 720, May, 1996.

81. Berrou C., Adde P., Angui E., Faudeil S. A low complexity soft-output viterbi decoder architecture // in Proc. of the Intern. Conf. on Commun. 1993. - May. - P. 737- 740.

82. Berrou C., Glavieux A., Thitimasjshima P. Near Shannon limit error-correcting coding and decoding: Turbo codes (l)//Proc. IEEE Int. Conf. on Communications. -Geneva. Switzerland, May 1993. P. 1064-1070.

83. Croizer S., Lodge J., Guinand P., Hunt A. Performance of turbo-codes with relative prime and golden interleaving strategies // in Proc. Sixth Intern. Mobile Satellite Conf. (Ottawa). 1999. - June. - P. 268-275.

84. Elias P., "Coding for Noisy Channels," IRE Com. Rec., vol. 3, pt. 4, pp. 37 -46,1955.

85. Erfanian J., Pasupathy S., Gulak G. Reduced complexity symbol detectors with parallel structures for ISI channels // IEEE Trans, on Commun. 1994. - Vol. 42. -P. 1661-671.

86. European Telecommunication Standards Institute (ETSI), Universal Mobile Telecommunications System (UMTS)A Multiplexing and Channel Coding (FDD). 3 GPP TS 125.212 Version 3.4.0 (23 September, 2000).

87. Jin H., Khandekar A., McElice R. Irregular repeat-accumulate codes // Proc. 2nd Int. Symp. on Turbo Codes and Related Topics (Brest, France). 2000. - Sept. -P.l-8.

88. Koetter R. and Vardy A., "Algebraic Soft-Decision Decoding of Reed-Solomon Codes", Proc. 2000 IEEE Int. Symp. Info. Theoiy (ISIT '00), p. 61, Sorrento, Italy, June 25-30, 2000.

89. Morelos Zaragoza R. H. and Imai H. Binary Multilevel Convolutional Codes with Unequal Error Protection Capabilities // IEEE Trans. Comm., vol. 46, no.7, pp. 850-853, July 1998.

90. Morris J.M. Burst Error Statistics of Simulated Viterbi Decoded BPSK on Fading and Scintillating Channels // IEEE Trans. Comm., vol. 40, no. 1, pp. 34 41, Jan. 1992.

91. Perez L.C., Seghers J. and Costello D. J., Jr. A Distance Spectrum Interpretation of Turbo Codes // IEEE Trans. Info. Theory, vol. 42, no. 6, pp. 1698 -1709, Nov. 1996.

92. Picart A. and Pyndiah R.M. Adapted Iterative Decoding of Product Codes // Proc. 1995 IEEE Global Telecomm. Conf. (GLOBECOM'95), pp.2357 2362, 1995.

93. Pursley M. B. and Shea J. M. Bit-by-Bit Soft-Decision Decoding of TrellisCoded M-DPSK Modulation // IEEE Comm. Letters, vol. 1, no. 5, pp. 133 135, Sept. 1997.

94. Pyndiah R.M., Glavieux A., Picart A. and Jacq S. Near Optimum Decoding of Product Codes // Proc. 1994 IEEE Global Telecomm. Conf. (GLOBECOM'94), vol. 1, pp. 339 343, San Francisco, CA, Dec. 1994.

95. Reddy S.M. and Robinson J.P. Random Error and Burst Correction by Iterated Codes//IEEE Trans. Info. Theory, vol. IT 18, no. l,pp. 182-185, Jan. 1972.

96. Reed I. and Solomon G. Polynomial Codes over Certain Finite Fields // SI AM J.Appl. Math., Vol. 8, pp. 300-304, 1960.

97. Richardson T.J. and Urbanke R.L. The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding // IEEE Trans. Info. Theory, vol. 47, no. 2, pp. 599-618, Feb. 2001.

98. Robertson P., Villebrun E., Hoher P. A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain // in Proc. of the Intern. Conf. on Commun. (Seattle, United States). 1995. - June. - P. 1009-1013.

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

100. 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. 69-71.

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