Комплекс решений по оптимизации передачи данных в радиоканалах с замираниями

Размещено на http://www.allbest.ru/

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

комплекс решений по оптимизации передачи данных в радиоканалах с замираниями

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

Автореферат

диссертации на соискание учёной степени доктора технических наук

Мелентьев Олег Геннадьевич

НОВОСИБИРСК 2007

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

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

профессор Шувалов В.П.

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

профессор Панько С.П.

- доктор технических наук,

ведущий научный сотрудник Ляхов А.И.

- доктор технических наук,

профессор Пуговкин А.В.

Ведущее предприятие указано в решении диссертационного совета.

Защита состоится «__» 2007 г. в 10.00 часов на заседании диссертационного совета. Д 212.099.04 при федеральном государственном образовательном учреждении высшего профессионального образования «Сибирский федеральный университет»

по адресу: 660074, Красноярск, 74, ул. Киренского, 26

С диссертацией можно ознакомиться в читальном зале КГТУ

Автореферат разослан «___»___________ 2007 г.

Учёный секретарь

диссертационного совета Д 212.099.04,

кандидат технических наук, доцент Саломатов Ю.П.

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

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

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

Группирование ошибок, свойственное прежде всего радиоканалам, затрудняет обеспечение высокой эффективности с использованием только лишь средств корректирующего кодирования. Необходимы дополнительные мероприятия, направленные на декорреляцию ошибок. К таковым можно отнести различные виды перемежений и хоппинг, используемые в системах мобильной связи стандартов GSM, CDMA и в беспроводных системах передачи данных Wi-Fi, WiMAX. Обоснованный выбор глубины перемежения и длины слота хоппинга требуют определения количественных оценок влияния данных операций на условия передачи. Полученные в работах E.Эллиота, В.И. Коржика, Л.М. Финка результаты позволяют рассчитать модифицированные параметры дискретного канала только для поэлементного перемежения и при глубине порядка 10-20. Далее возникают трудности, связанные с увеличением объёма вычислений, что затрудняет оперативное использование этих методик в адаптивных системах. Необходимо разработать модели и методики, позволяющие оценивать влияния поэлементного и посимвольного перемежения, а также хоппинга на параметры дискретных каналов, не требующие значительных вычислительных затрат.

Для эффективной передачи информации по нестационарным каналам необходимо вводить элементы адаптации. Вопросами анализа адаптивных систем занимались М.Н. Арипов, Э.Л. Блох, Н.Н. Буга, Л.Ф. Жигулин, Л.П. Коричнев, О.В.Попов, Л.А.Растригин, Ю.Г.Ростовцев, Б.Я. Советов, А.И. Фалько, В.А. Шапцев, В.П. Шувалов, M. Zorzi и другие. Известны различные классы адаптивных систем, многие их которых широко используются в системах передачи. Например, системы с классической решающей обратной связью.

Растущие возможности элементной базы позволяют реализовывать более эффективные алгоритмы систем. Появление ряда работ J. Perez-Romero, R. Agusti, O. Sallent, S. Sesia, G. Vivier, A. Mehta, D. Kagaris, R.Viswanathan, Y. Wu, Z. Niu, J. Zheng показало перспективность разработки и исследования систем с гибридной обратной связью, которые в ряде случаев позволяют добиться лучших качественных показателей, что открывает широкие перспективы для их внедрения в системах передачи данных следующих поколений.

Помимо коррекции повреждённых блоков целесообразно осуществлять регулировку внутренних параметров системы (длину блока, избыточность, глубину перемежения, длину слота при хоппинге и т.п.) исходя из условий передачи. Оценка качества передачи может проводиться на разных уровнях. Например, на уровне непрерывного канала это может быть измерение мощности сигнала, отношения сигнал-шум и т.д. Представляется интересным рассмотреть методы, использующие оценку качества дискретного канала (метод обучения системы по известной последовательности) или канала передачи данных. На уровне канала передачи данных наименее затратной является оценка состояния канала по качеству приёма блока. Данная оценка проводится для каждого принятого блока, а её результаты являются естественным источником информации о состоянии канала при использовании систем с решающей обратной связью. Важным моментом является выбор алгоритма, на основе которого принимается решение об изменении состояния канала. Время, затрачиваемое на определение состояния канала, и ошибки при определении состояния канала во многом будут определять производительность системы в целом. В работах A. Annamalai, V. Bhargava, M. Rice и S. Cho описан ряд алгоритмов, основанных на использовании сигналов переспроса. Предложены отдельные методики оценки эффективности алгоритмов, которые, однако, не учитывают ошибки определения состояния. Представляет интерес разработка универсальных методик, позволяющих анализировать и сравнивать различные алгоритмы оценки состояния канала в одинаковых условиях, с приемлемой точностью и при сравнительно небольших затратах вычислительных ресурсов.

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

Объект исследования: методы повышения эффективности систем передачи данных по радиоканалам с группирующимися ошибками.

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

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

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

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

2. Разработать методику оценки параметров модели по статистике ошибок в дискретном канале.

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

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

5. Разработать математические модели, связывающие вероятностно-временные характеристики (ВВХ) систем с их внутренними параметрами и параметрами дискретного канала.

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

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

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

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

Научная новизна полученных результатов

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

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

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

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

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

6. Разработаны аналитические и имитационные модели алгоритмов адаптации с оценкой успешных и ошибочных приёмов (ОУОП), со скользящим окном наблюдения (СОН), со скользящим окном наблюдения переменной длины (СОН-ПД), с фиксированным периодом наблюдения (ФПН) и с переменным периодом наблюдения (ППН), позволяющие получать оценки производительности адаптивной системы в зависимости от параметров алгоритма и параметров дискретного канала с двумя и тремя состояниями.

Практическая значимость работы

Результаты диссертационной работы использованы: в Уральском конструкторском бюро связи (УКБС) Екатеринбургского филиала электросвязи ОАО «Уралсвязьинформ» при разработке абонентских устройств в рамках реализации проектов «Организация широкополосного доступа к ресурсам сети Интернет для общеобразовательных учреждений» и «Организация связи к службе 112» в Свердловской области; в Объединённом Макро Региональном Центре по Уральскому федеральному округу в ООО «Эквант» при решении технических проблем и проектировании систем передачи данных; в СибГУТИ при разработке лекционных курсов по дисциплинам: «Системы и сети передачи дискретных сообщений», «Основы построения телекоммуникационных систем и сетей».

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

Основные результаты, выносимые на защиту

1. Методы расчёта значений вероятности ошибок заданной кратности в блоке фиксированной длины для дискретного канала с двумя состояниями.

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

3. Аналитические выражения для расчёта модифицированных параметров модели Гилберта после применения операций перемежения и хоппинга.

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

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

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

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

8. Аналитические модели систем с алгоритмами адаптации ОУОП, СОН, СОН-ПД, ФПН и ППН, позволяющие получать оценки производительности адаптивной системы в зависимости от параметров данного алгоритма и параметров дискретного канала с двумя состояниями.

9. Аналитическая модель системы с алгоритмом адаптации ОУОП, позволяющая получить оценку производительности адаптивной системы в зависимости от параметров алгоритма и параметров дискретного канала с тремя состояниями.

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

Апробация

Основные результаты диссертационной работы были доложены на:

Российской научно-технической конференции «Информатика и проблемы телекоммуникаций» - Новосибирск, 1996, 2005гг.

Международной научно-технической конференции «Информатика и проблемы телекоммуникаций» - Новосибирск, 2001, 2002, 2003, 2004гг.

III Международной конференции «Современные информационные технологии - СИТ-98» - Новосибирск, 1998г.

Международной научно-технической конференции «Microwave electronics: Measurements, Identifications, Applications - MEMIA 2001» - Новосибирск, 2001г.

Международных научно-технических конференциях «Siberian Russian Workshops and Tutorials on Electron Devices and Materials - EDM-2002, EDM-2003, EDM-2004, EDM-2005» - Эрлагол, 2002, 2003, 2004, 2005гг.

Международной научно-технической конференции «Перспективы развития современных средств и систем телекоммуникаций» - Томск, 2003г.

Международной научно-технической конференции «Современные проблемы телекоммуникаций» - Одесса, 2003г.

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

Международной научно-практической конференции «Перспективы развития современных средств и систем телекоммуникаций» - Екатеринбург, 2005г.

IX Международной научно-технической конференции «Проблемы функционирования информационных сетей» - Новосибирск, 2006г.

Публикации

По результатам исследований опубликовано 45 работ, из них одна монография, 9 статей в реферируемых журналах, рекомендованных ВАК РФ для публикаций материалов, отражающих основные результаты докторских диссертаций, 7 работ, депонированных в ВИНИТИ, учебное пособие СибГУТИ с грифом УМО, 2 свидетельства о регистрации в ОФАП и 25 докладов на международных и всероссийских конференциях.

Личное участие

В совместных публикациях автору диссертации принадлежат постановки задач, разработка методов исследования, трактовка полученных результатов. Программы для ПК и расчёты, представленные в главах 5 и 6, выполнены совместно с аспирантами диссертанта П.А. Коноваловым и С.Н. Мякишевым.

Структура диссертационной работы

Диссертация состоит из введения, шести глав, заключения и приложений. Список литературы содержит 95 наименований. Объём диссертации 305 страниц, включая 9 таблиц и 129 рисунков.

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

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

В первой главе рассматриваются вопросы моделирования дискретных каналов. Приводится оценка погрешности определения границ производительности системы, обусловленная уменьшением числа состояний, учитываемых в модели канала. Показано, что при аппроксимации дискретного канала, имеющего четыре состояния, моделью с тремя состояниями максимальная погрешность составила 2,9%, а при аппроксимации моделью с двумя состояниями - 6,1%. При этом сложность модели системы уменьшается соответственно в 3,4 и 20 раз. Пропорционально сложности модели уменьшается и время вычислений, что особенно важно при реализации адаптивных систем.

Проведённая оценка, а также анализ публикаций в научной печати (Zorzi M., Rao R.R., Yee J.R., Weldon E.J., Babich F., Lombardi G., Ebert J.P., Willig A.A., Villasenor J.D.) показывают, что достаточную точность при приемлемых затратах на вычисление обеспечивают модели с двумя состояниями, такие как модели Гилберта и Гилберта - Эллиота. Данные модели были выбраны в качестве рабочих для дальнейшего анализа.

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

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

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

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

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

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

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

Поскольку все параметры канала определяются по средним длинам состояний, получены выражения для расчёта точности оценок средних длин состояний Dg (Db) по допустимым погрешностям оценок искомых вероятностей Pgg и Pgb :

, , % ,

где - допустимые погрешности оценок искомых вероятностей Pgb и Pgg.

Далее на основе имитационного моделирования проводится оценка зависимости погрешностей и доверительных интервалов измеряемых величин Dg(Db) от объёмов испытаний при различных параметрах модели Гилберта, описывающей дискретный канал.

Сами по себе погрешности оценок параметров дискретного канала не позволяют судить о необходимой и достаточной точности их измерения. Более важным представляется получение погрешностей вторичных параметров системы ПД, обусловленных погрешностями полученных оценок. В качестве вторичных параметров были выбраны вероятность неправильного приёма блока и вероятности появления ошибок кратности от 0 до 10 в блоке длиной n=200 элементов. Данные параметры были рассчитаны по истинным значениям параметров канала (используемым при генерации потока ошибок) и определены по статистическим оценкам при разных объёмах испытаний.

Погрешности статистических оценок не превысили 10.6% при =500 и 3.3% при =1000. Погрешности в определении вероятности приёма блока без ошибок не более 19.3%. При оценке вероятностей ошибок m =1...10 погрешности не превышали 11.5%.

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

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

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

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

В соответствии с рассматриваемыми моделями, вероятности возникновения ошибок в состояниях различны, поэтому перед вычислением необходимо определить вероятности того, что из элементов блока элементов были переданы в плохом состоянии канала - . Тогда вероятность m-кратной ошибки в блоке из n элементов можно определить, используя выражение где - вероятность m-кратной ошибки, если число элементов, переданных в В-состоянии, равно i (для модели Гилберта); - вероятность ошибки в В-состоянии; - число сочетаний из i по m.

Основные затраты при определении приходятся на определение вероятностей B(i,n). Далее предлагаются два метода нахождения вероятностей B(i,n), отличающиеся точностью результатов и временем вычислений.

Предлагается матричный метод точного решения задачи, позволяющий несколько снизить требования к вычислительным ресурсам при вычислении B(i,n). Для решения задачи вводим новые состояния, являющиеся комбинацией физического состояния канала Sj и числа шагов нахождения в нём. За n шагов система будет находиться k шагов в состоянии Sb и l шагов в состоянии Sg, причём k+l=n. Такое комбинированное состояние будем обозначать Sj(k,l). Начальные состояния при n=0 обозначены через Sb(0,0) и Sg(0,0) соответственно. Обозначим начальные вероятности состояний через pb и pg, а вектор начальных вероятностей - через , при этом .

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



Рис. 1 Граф состояний системы при введении комбинированных состояний

На первом шаге матрица переходных вероятностей соответствует исходной матрице модели Гилберта. Матрица переходных вероятностей на n-м шаге имеет размерность

2(n-1)x2n; её структура имеет следующий вид:

,

где: - диагональная матрица, расширенная справа на один нулевой столбец; - диагональная матрица, расширенная слева на один нулевой столбец; Abb, Abg, Agb, Agg - диагональные матрицы порядка (n-1), ненулевые элементы которых равны соответственно;- столбец нулей, расширяющий соответствующие матрицы справа или слева.

Изложенный выше подход позволяет получить вектор распределения вероятностей для комбинированных состояний на любом шаге . Для получения значений B(i,n) необходимо просуммировать вероятности состояний bj(k,l) с одинаковым первым индексом. Таким образом, схема формирования вероятностей B(i,3) имеет вид:

; ; ; .

В общем виде можно записать:

.

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

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

Искомая величина представляет собой сумму вероятностей всех векторов состояния канала длины n и веса i.

В отличие от канала с независимыми ошибками, в канале с выраженным группированием ошибок вероятности векторов одного веса будут зависеть от числа возвращений плохого состояния на длине вектора. Вероятности векторов, в которых встречается частое чередование 0 и 1 (т.е. многократные переходы из плохого состояния в хорошее), могут иметь вероятность на несколько порядков меньшую, чем векторы того же веса, но с малым числом возвращений в плохое состояние. Исключая из расчёта вектора, отражающие многократное возвращение в В-состояние, можно значительно сократить время расчёта, сохраняя приемлемую точность результатов. Естественно, такой подход будет давать некоторую погрешность результата, зависящую от числа учитываемых возвращений, длины блока и вероятностей смены состояний канала. Критерием интегральной оценки погрешности, вносимой отбрасыванием членов, учитывающих многократные возвращения, может служить величина .

Получены выражения, позволяющие учитывать вклад в вероятность B(i,n) векторов с одним, двумя и v возвращениями:

при ;

при ;

при .

Данные выражения справедливы для числа возвращений от v=3 и выше.

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

,

где PT, (PУ) - значения, полученные по точному алгоритму и по упрощённой методике соответственно.

Зависимости относительной разницы результатов расчёта B(i,n), полученных с применением точной и упрощённой методики при числе учитываемых возвращений 2, 3, 4 и 5, показаны на рисунке 2.

Рис. 2 Зависимости относительной разницы результатов расчёта B(i,n), полученных с применением упрощённой методики при разном числе учитываемых возвращений

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

Для объективного сравнения затрат при вычислении по разным методикам необходимо выбрать параметры, количественно характеризующие эти затраты и не зависящие от быстродействия процессора и оптимальности алгоритмов. Выберем в качестве таких параметров количество операций сложения и умножения, необходимых для вычисления одного значения вероятности и проведём их оценку. На рисунке 3 приведены зависимости числа операций суммирования (пунктирные линии) и умножения (сплошные) на вычисление для n, изменяющемся в пределах от 5 до 128 при расчётах по методике Эллиота и упрощённой методике при числе учитываемых возвращений, равном 7.

Рис. 3. Зависимости затрат операций сложения и умножения на вычисление P(5,n) от n: 1 - по методике Эллиота; 2 - по упрощённой методике

дискретный канал параметр гилберт

Графики наглядно показывают преимущество упрощённой методики в диапазоне длин блоков более 40.

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

Методы вычисления модифицированных параметров рассматривались ранее в работах Е. Эллиота и других авторов. В частности, искомые модифицированные параметры можно определить как элементы матрицы, полученной возведением исходной матрицы переходных вероятностей в степень (В. Феллер. Введение в теорию вероятностей и её приложения, 2-е изд. М.: Мир, 1967). Такой метод позволяет учитывать влияние только поэлементного блочного перемежения и требует много времени при большой глубине перемежения. В главе получены более простые и универсальные выражения, позволяющие учитывать как поэлементные, так и посимвольные операции.

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

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

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

. (1)

Доказательство теоремы выполнено при помощи метода математической индукции.

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

(2)

, .

Выражения (2) справедливы для поэлементного перемежения и поэлементного временного разделения каналов.

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

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

;

. (3)

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

(4)

Для проверки гипотезы использовалось имитационное моделирование. Задавая параметры исходного дискретного канала, генерировался случайный массив длин плохих и хороших состояний. Далее сгенерированный массив просеивался через “дырки” размером и периодом Z (см. рисунок 4). После просеивания определялись средние длины состояний , , по которым оценивались значения модифицированных параметров. Результаты моделирования и расчётов с использованием (4) при , и объёме сгенерированного массива 500 элементов приведены на рисунке 5. Как видно из рисунков, точки, полученные методом имитационного моделирования, достаточно точно ложатся на графики зависимостей средних длин состояний, полученные по предложенным выражениям (4) или группируются вокруг них. Данные результаты указывают на состоятельность гипотезы.

Рис. 4 Просеивание массива длин состояний

Рис. 5 Результаты расчётов и моделирования при Pgg=0,9; Pbb=0,8

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

Рис. 6 Поверхность относительных скоростей

Рис.7 Область выигрыша при перемежении

Методика позволяет определить область, в которой обеспечивается выигрыш (см. рис 7).

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

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

и .

Передача ведётся слотами длиной -элементов. При передаче каждого следующего слота происходит смена канала (см. рисунок 8).

Рис 8 Хоппинг при двух каналах и длине слота 4 элемента

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

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

, . (5)

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

, .

Далее определим модифицированный коэффициент группирования .

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

; , где . (6)

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

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

. (7)

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

. (8)

Зная коэффициент группирования во всем диапазоне длин слотов, искомые вероятности смены состояний определяются выражением (5), а средние длины состояний - выражениями (9)

, . (9)

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

, где , . (10)

Средние длины хоппинг-процесса во всём диапазоне длин слотов для каналов можно описать выражениями:

, . (11)

Вероятность ошибки в плохом состоянии результирующего канала при хоппинге n исходных каналов может быть определена выражением (12)

. (12)

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

Результаты имитационного моделирования и расчётов по предложенным выражениям для хоппинга трёх каналов с разной длиной слота показаны на рисунке 9. Параметры исходных каналов: ; .

Рис. 9 Зависимости средних длин состояний от длины слота для хоппинга трёх каналов

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

Далее рассматривается влияние хоппинга на относительную скорость системы с исправлением ошибок.

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

Рассматривается два дискретных канала с группирующимися ошибками ДК1 и ДК2, параметры которых описываются моделью Гилберта.

Для организации передачи данных к исходным каналам применяется операция хоппинга с длиной слота . Затем в каждом из образованных посредством хоппинга каналов выполняется операция перемежения с глубиной перемежения . В результате преобразований получаем два одинаковых дискретных канала ДК* с модифицированными параметрами (рисунок 10).

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

Рис. 10. Схема хоппинга двух каналов с перемежением

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

. (13)

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

Рис. 11. Зависимость коэффициента группирования от глубины перемежения при ;, : 1 - по формуле (13), 2 - по результатам имитационного моделирования

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

. (14)

Зависимости коэффициента группирования от при длине хоппинга, равной 10 элементов, полученные по результатам имитационного моделирования и расчётов по формулам (1) и (14), показаны на рисунке 12.

Рис. 12. Зависимости коэффициента группирования от глубины перемежения при длине слота ; ,

Совпадение результатов имитационного моделирования и расчётов по формуле (15) подтверждает правильность проведённых рассуждений.

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

; ; .

Число каналов, участвующих в процедуре хоппинга, определяет период зависимостей модифицированных параметров. Так, при двух каналах период равнялся , при трёх и четырёх - и соответственно. Зависимость коэффициента группирования по-прежнему будет определяться выражением (14), но функция требует модификации для учёта соответствующего числа каналов, участвующих в хоппинге. Как видно из рисунка 13, максимальные значения зависимости коэффициента группирования определяются выражением (1) при , где - число каналов; - 0, 1, 2, … .

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

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

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

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

Описание системы ГРОС-БКК. Передаваемая информационная последовательность разбивается на кадры длиной k элементов. Каждый информационный кадр защищается корректирующим кодом с обнаруживающей способностью . Информационный кадр вместе с заголовком и проверочными разрядами кода, обнаруживающего ошибки, образуют блок длиной элементов. Блок , в свою очередь, защищается кодом, исправляющим ошибки с исправляющей способностью . В результате данной операции получается дополнительная корректирующая группа из проверочных разрядов. Первоначально передаётся блок . Если на приёме в нём обнаружена ошибка, то запрашивается передача корректирующей группы . После исправления ошибок информационный блок повторно проверяется на наличие ошибок. Если ошибки остаются, то в следующей попытке повторяется информационный блок n.

Система ГРОС-СКК. Структура системы ГРОС-СКК показана на рисунке 14. После кодирования в блочном кодере информационный кадр вместе с r проверочными разрядами кода, обнаруживающего ошибки, образуют блок X длиной n элементов. Перед свёрточным кодированием к блоку добавляется v «нулевых» элементов для завершения решётки. Затем блок поступает в свёрточный кодер со скоростью 1/3. Каждый входной элемент на выходе кодера порождает три элемента. Выходные элементы с каждого сумматора кодера поочередно записываются в три регистра буфера Yl так, что первый регистр содержит первые элементы Y1, второй - вторые Y2, и, соответственно, третий - третьи Y3.



Рис.14. Структура системы передачи данных ГРОС-СКК

В соответствии с номером попытки передачи (l=1,2,3), в блочный матричный перемежитель из буфера поступает блок Yl, к которому добавляются m «нулевых» элементов для завершения матрицы перемежения. После перемежения блок Ylp длиной n+v+m элементов передаётся по прямому каналу с группирующимися ошибками.

На приёмной стороне блок Y*lp поступает в деперемежитель, где восстанавливается исходный порядок следования элементов и убираются m добавочных элементов. Восстановленная последовательность Yldp записывается в буфер. В зависимости от номера попытки передачи, блок сразу передаётся в свёрточный декодер (l=1) или сначала попадет в объединитель (l=2,3). В объединителе поступающие из буфера блоки объединяются путём чередования элементов в последовательность Y* длиной l(n+v). Свёрточный декодер (l,1,v+1) декодирует полученную последовательность и усекает блок X* до n элементов. Блочный декодер проверяет блок X* на наличие ошибок и принимает решение о качестве декодирования.

Обнаружение ошибок в блоке инициирует передачу по обратному каналу отрицательной квитанции. При получении первой отрицательной квитанции по прямому каналу передаётся блок Y2p, а на приёме производится исправление ошибок свёрточным декодером (2,1,v+1). В случае повторного обнаружения ошибок передаётся Y3p, а ошибки исправляются более мощным декодером (3,1,v+1). Если третья попытка оказывается неудачной, система возвращается к первой попытке или переходит к передаче следующего информационного блока.

В системе ГРОС-ККК приём при первых двух попытках передачи происходит аналогично системе ГРОС-СКК. Если после исправления ошибок свёрточным декодером (2,1,v+1) происходит их обнаружение, в третьей попытке передаётся корректирующая группа длиной r2 элемента аналогично системе ГРОС-БКК. Блок X* вместе с корректирующей группой r2 из буфера поступают в блочный декодер-2, где происходит коррекция ошибок.

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

Далее проводится оценка и сравнение ВВХ различных систем за попыток. Для системы ГРОС-БКК с ожиданием получены выражения, позволяющие определить вероятность успешной доставки:

при - нечётном ,

при - чётном ,

где ; ;

Pe - вероятность обнаружения ошибки в блоке, - вероятность приёма блока без ошибок, Pи - вероятность исправления ошибок и Pни - вероятность того, что после исправления ошибки останутся.

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

.

Далее были получены выражения для оценки затрат двоичных элементов на передачу блока при заданном числе попыток.

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

- при одной попытке ;

- при чётном значении , ;

- при нечётном , .

Затраты в обратном канале:

- при одной попытке ;

- при чётном значении , ;

- при нечётном значении , .

Относительная скорость определится выражением

.

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

Далее проводится моделирование систем с адресным переспросом.

В классической системе РОС-АП передача ведётся пакетами по N блоков. При обнаружении ошибок происходит адресный запрос повторения в следующей попытке только поражённых блоков. Моделирование такой системы удобно проводить на основе марковских цепей.

Выберем в качестве состояния системы количество успешно доставленных блоков j в пакете длиной N. В качестве дискретного шага системы выберем следующую попытку передачи после приёма сигнала обратной связи, несущего информацию о результатах предыдущей попытки. Граф системы РОС-АП при передаче четырёх блоков в пакете представлен на рисунке 15.

Рис.15 Граф состояний системы с ОС и адресным переспросом

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

.(15)

Элементы матрицы имеют смысл вероятности того, что Х блоков из Y будут доставлены без ошибок. Вектор распределения вероятностей состояний системы на любом шаге или после любой попытки передачи .

Зная вектор и матрицу, можно найти множество вероятностно-временных характеристик. Например, вероятность успешной доставки пакета после Lm-той попытки определится как последний элемент вектора .

Отличие гибридной системы ГРОС-БКК с АП в том, что в нечётных попытках повторяются поражённые информационные блоки, а в чётных - передаются корректирующие группы для исправления ошибок. Данная особенность приводит к необходимости использования двух матриц переходных вероятностей. Одна соответствует повторению информационных блоков и определяется аналогично (15). Вторая - отражает процесс исправления ошибок. Структура и размерность данных матриц одинаковы. Элементы второй матрицы имеют смысл правильного исправления Х блоков из Y после передачи корректирующей группы. Данные элементы определяются выражением

,

где .

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

Рис.16 Зависимости ВВХ систем ГРОС-БКК и РОС с адресным переспросом от максимального числа переспросов

На рисунке 16 представлены зависимости вероятности успешной доставки, затрат в прямом и обратном каналах и относительной скорости передачи от количества попыток для ГРОС-БКК системы с АП и классической системы РОС-АП, полученные аналитически (сплошные линии) и методом имитационного моделирования (точки). Данные зависимости наглядно иллюстрируют преимущества гибридной системы.

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

Особенностью системы ГРОС-СКК является то, что вероятности правильного приёма блока после первой, второй и третьей попыток передачи различны. Это приводит к необходимости использования при вычислении векторов распределения вероятностей состояний системы после l-той попытки передачи - трёх матриц переходных вероятностей (P1, P2, P3). Структура и размерность данных матриц одинаковы, а элементы определяются выражениями:

, ,

,

где Pe - вероятность обнаружения хотя бы одной ошибки в блоке n; Pпп2 и Pпп3 - вероятности правильного приёма блока n после исправления ошибок во второй и третей попытках передачи, соответственно.

...