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

В рамках своей диссертации « » мне нужно было делать обзор моделей прогнозирования . Кроме обзора, я сделала вариант классификации, который мне тогда не очень удался. Классификацию уже немного поправила, теперь хочется разобраться в существующих моделях прогнозирования временных рядов. Такие модели называют стохастическими моделями (stochastic models).

По оценке некто Тихонова в его «Прогнозировании в условиях рынка » на сегодняшний день (2006 год) существует около 100 методов и моделей прогнозирования. Эта оценка звучит бредово, я полно разбирала ее ! Давайте теперь вместе разберемся, какие же модели прогнозирования временных рядов существуют на сегодняшний день.

1. Авторегрессионные модели прогнозирования (ARIMAX, GARCH, ARDLM)
2. Модели экспоненциального сглаживания (ES)
3. Модель по выборке максимального подобия (MMSP)
4. Модель на нейронных сетях (ANN)
5. Модель на цепях Маркова (Markov chains)
6. Модель на классификационно-регрессионных деревьях (CART)
7. Модель на основе генетического алгоритма (GA)
8. Модель на опорных векторах (SVM)
9. Модель на основе передаточных функций (TF)
10. Модель на нечеткой логике (FL)
11. Что еще?...

Регрессионные модели прогнозирования

• Простая линейная регрессия (linear regression)
• Множественная регрессия (multilple regression)
• Нелинейная регрессия (nonlinear regression)

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

Модель по выборке максимального подобия

Модель на нейронных сетях

Модель на цепях Маркова

Вопрос к аудитории: посоветуйте хорошую и понятную (!) книгу/статью по применению цепей Маркова для прогнозирования временных рядов.

Модель на классификационно-регрессионных деревьях

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

Вопрос к аудитории: посоветуйте хорошую и понятную (!) книгу/статью по применению генетического алгоритма для прогнозирования временных рядов.

Модель на опорных векторах

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

Модель на нечеткой логике

Вопрос к аудитории тот же!

Итого

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

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

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

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

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

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

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

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

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

Точность прогнозов

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

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

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

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

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

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

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

Виды прогнозов

Различают три основных вида прогноза: технологический, экономический и прогноз объема продаж (спроса).

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

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

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

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

Кафедра «Электрическая связь»

Отчёт по лабораторной работе №1

Моделирование и исследование процессов кодирования и декодирования циклических кодов

Работы выполнил
студенты группы АТк-404
МАВРИН А.М.

1. Исходные данные

Вариант 15

В системе передачи данных имеется 15 объектов на каждой из 63 станций. Канал передачи информации – односторонний с независимыми ошибками.

2. Цель работы

1. Определить параметры циклического несистематического (n,k) кода.

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

3. Закодировать информационную комбинацию в несистематическую кодовую комбинацию .

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

5. Определить теоретически синдром ошибки.

6. Построить схему генератора синдромов.

7. По таблице состояний для этой схемы определить синдром ошибки.

8. Исказить кодовую комбинацию на один или два элемента (в зависимости от количества ошибок по заданию) и показать, на каком такте произойдёт исправление ошибки (по таблице состояний).

3. Выполнение работы

3.1. Определение параметров циклического кода

3.2. Проверка производящего полинома на соответствие выбранному коду

а) (n – k ) = 4 (высшая степень полинома, верно )

4. Кодирование

4.1. Построение схемы кодера

4.2. Уравнения функционирования

4.3. Таблица, иллюстрирующая схему работы кодера

Таблица 1

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

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

Тогда среднее количество переданной информации на каждый символ равно

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

(2.56)

Найдя и подставив его в (2.55), можно найти максимальное количество передаваемой в таком канале информации и его пропускную способность .

В частном случае симметричного канала величина равна нулю и оптимальное значение , как и следовало ожидать, равно 0,5.

В предельном случае, когда один из символов, например «1», всегда принимается правильно , a другой символ «0» может приниматься как «1» с вероятностью , выражение (2.56) упрощается

(2.56а)

Заметны, что в этом случае символ «1» является «надежным» передаваемым символом, так как он всегда принимается верно. Однако «достоверным» принятым символом является (0), так как приняв его, можно с полной достоверностью утверждать, что именно этот символ передавался.

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

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

Для несимметричного канала, в котором (или так что практически величиной можно пренебречь), можно применить эффективные корректирующие коды, позволяющие обнаруживать и исправлять ошибки . Однако теория таких кодов мало разработана и существенно отличается от теории кодирования в симметричных каналах. Так, например, код, состоящий из кодовых комбинаций 00 и 11, позволяет исправлять одну ошибку (переход 0 в 1), если условиться декодировать принятые комбинации 01 и 10 как 00. В то же время код, состоящий из комбинации 01 и 10 не даст возможности исправлять ошибку, а позволяет только ее обнаруживать, хотя оба эти кода характеризуются одинаковым хемминговым расстоянием, равным 2. Заметим, что в симметричном канале оба эти кода позволяют только обнаружить одиночную ошибку.

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

то в канале с памятью она может бить больше или меньше этой величины.

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

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

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

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

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

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

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

(2.60)

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

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

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

Вероятности пребывания канала в состояниях и , как легко подсчитать, равны

а безусловная вероятность ошибки

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

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

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

Модель Беннета-Фрелиха более гибка, чем модель Гильберта, так как она допускает весьма свободный выбор функции , на которую наложено только обычное условие нормирования, тогда как в модели Гильберта распределение вероятностей длительности состояния всегда выражается формулой , т. е. однозначно определяется величиной . Тем не менее для многих экспериментально исследованных каналов не удастся удовлетворительно подобрать параметры модели Беннета-Фрелиха, а тем более модели Гильберта. Ввиду этого О.В.Попов предложил более сложную модель дискретного канала, отличающуюся от модели Беннета-Фрелиха тем, что пачки ошибок считаются не независимыми. Согласно этой модели канал может находиться в двух состояниях, причем в первом состоянии ошибки не возникают, а во втором состоянии с определенной вероятностью возникают пачки ошибок; параметрами являются вероятности переходов из одного состояния в другое; вероятность возникновения пачки во втором состоянии, вероятность ошибки внутри пачки (которая обычно равна 0,5) и распределение вероятностей длины пачки. В большинстве случаев удается этими параметрами достаточно хорошо характеризовать реальные каналы.

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

при

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

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

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

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

Пропускную способность такого канала можно приближенно определить, усредняя «частичные» пропускные способности по состояниям и :

(2.61)

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

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

Очевидно, что применение кода, рассчитанного на постоянный симметричный канал с вероятностью ошибки равной средней вероятности ошибок в канале с памятью:

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

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

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

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

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

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

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

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

В 1959 г. Н. Абрамсон предложил циклический код, позволяющий исправлять как одиночные, так и двойные смежные ошибки . Вскоре П. Файр излучил обобщение этого результата, построив коды, позволяющие обнаруживать и исправлять пачки ошибок при . Эти коды оказались циклическими или укороченными циклическими кодами . Найдены также и другие коды, исправляющие пачки ошибок. Практическое применение их затрудняется тем, что при не очень большой избыточности, как правило, . Так, например, код Файра (279, 265), содержащий 265 информационных и 14 проверочных разрядов, позволяет исправить только одну пачку ошибок длиной . Другой код со значительно большей избыточностью (44, 22) исправляет пачки длиной . Заметим, что этот же код в условиях постоянного канала позволяет исправить только одиночные, двойные и в отдельных случаях тройные ошибки. Значительно более успешно осуществляется в циклических кодах обнаружение пачек ошибок .

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

В качестве примера симметричного аномального марковского канала рассмотрим двоичный канал с двумя состояниями, где в состоянии вероятность ошибки , а в состоянии вероятность ошибки , причем после правильного приема символа канал находится в состоянии , а после ошибочного приема - в состоянии . Другими словами, в состоянии все символы принимаются правильно, пока не произойдет ошибка, имеющая вероятность , после чего все последующие символы принимаются «в негативе» т. е. вместо «0» принимается «1» и наоборот, пока символ не будет принят правильно, что в состоянии произойдет с вероятностью . После этого канал перейдет в состояние . Легко убедиться, что оба состояния равновероятны и средняя вероятность ошибки . При такой вероятности ошибки пропускная способность постоянного канала равна нулю, тогда как рассматриваемый канал согласно (2.58) и (2.28) имеет относительно большую пропускную способность

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

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

Будет восстановлен символ а вместо символа - символ . Легко видеть, что все последующие символы (до перехода канала в позитив) будут также восстановлены правильно, а в момент перехода в позитив один символ будет восстановлен ошибочно. Таким образом, при каждом переходе канала из одного состояния в другое один из передаваемых символов будет принят с ошибкой. В результате примененное перекодирование превращает этот марковский канал в однородный канал с вероятностью ошибки . Если при первоначальном кодировании сообщения в символы применить код, исправляющий одиночные ошибки, то можно получить высокую верность приема в таком канале.

Получим:

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

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

Такие коды также обнаруживают все ошибки, кроме части ошибок смещения.

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

• Специальность ВАК РФ05.12.02
• Количество страниц 170