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

В.В.Золотарёв Обзор по кодированию2 Большой объем передачи цифровых данных требует обеспечить их высокую достоверность w Одним из важнейших способов снижения вероятности ошибки при передаче по каналам с шумами, искажающими цифровые потоки, является использование методов помехоустойчивого кодирования

В.В.Золотарёв Обзор по кодированию3 Принципы помехоустойчивого кодирования w Информация разбивается на блоки, например, двоичных символов, к которым добавляются контрольные разряды, являющие функцией от информационной части передаваемого сообщения. w Относительная доля исходных информационных символов в таком расширенном блоке называется кодовой скоростью R.

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

В.В.Золотарёв Обзор по кодированию5 Основное ограничение теории информации для кодирования w Всегда должно выполняться условие w R

В.В.Золотарёв Обзор по кодированию6 Как в технике связи выполнить указанное условие? Это сложно или нет? w 1. Введение избыточности, соответствующей заданному значению кодовой скорости R - это очень просто. Значит, R

В.В.Золотарёв Обзор по кодированию7 Простейший кодер для блокового кода, исправляющего 2 ошибки! Так задаем избыточность (скорость); R=1/2

В.В.Золотарёв Обзор по кодированию8 По возможности - ещё проще!!! Пример кодера для свёрточного кода с той же кодовой скоростью R=1/2.

В.В.Золотарёв Обзор по кодированию9 Предельные возможности кодов

В.В.Золотарёв Обзор по кодированию10 Какое качество кодов главное? w - кодовое расстояние d, определяющее минимальное количество символов, в которых могут отличаться кодовые слова, т. е. допустимые сообщения. w Например, w Например, в кодах проверки на чётность все допустимые слова - только w с w с чётным числом единичек и, значит, для них кодовое расстояние d=2 !

В.В.Золотарёв Обзор по кодированию11 Зачем надо брать коды с большими значениями d ? Зачем надо брать коды с большими значениями d ? w Чем больше d, тем большее число ошибок, попавшее в сообщение при передаче, может быть исправлено. w В этом случае растёт доля сообщений, которые после обработки (декодирования) могут оказаться безошибочными. w w А тогда какие максимальные значения d возможны?

В.В.Золотарёв Обзор по кодированию12 Пределы корректирующих свойств двух классов кодов

В.В.Золотарёв Обзор по кодированию13 Какой же длины должен быть код? Один из главных вопросов: Какой же длины должен быть код? w Поскольку при R

В.В.Золотарёв Обзор по кодированию14 Нижние оценки вероятностей ошибки оптимального декодирования блоковых кодов с R=1/2 в ДСК. Нижние оценки вероятностей ошибки оптимального декодирования блоковых кодов с R=1/2 в ДСК. Даже коды длины n=1000 неэффективны при вероятности ошибки в канале Ро>0.08. А теория-то утверждает, что можно успешно работать при Ро 1/2. И ведь это переборные методы!

В.В.Золотарёв Обзор по кодированию15 Главные «шутки» природы Главные «шутки» природы w 1. Почти все коды «хорошие». Случайно выбранный код, т.е. структура связей в кодере, в большинстве случаев в хорошем приёмнике обеспечит вероятность итоговой ошибки, мало отличающуюся от наилучшей из возможных. w 2. Почти все коды могут декодироваться только переборными методами. Для кода длины 1000 перебор при R=1/ (!!!) вариантов решений превышает число атомов во Вселенной! И ЧТО ЖЕ ДЕЛАТЬ ?!!!

В.В.Золотарёв Обзор по кодированию16 Главная проблема теории помехоустойчивого кодирования w 1. Найти и исследовать методы более простого непереборного декодирования принятых из канала с шумом сообщений.. w 2. Обеспечить такое качество декодирования этими методами, чтобы оно было по возможности ближе к эффективности с переборных процедур. w 3. Максимально учитывать потребности и условия применения кодирования в реальных системах связи.

В.В.Золотарёв Обзор по кодированию17 Что умеют конкретные методы декодирования? Коды БЧХ: до R=C, т.е. до Ро = о-о-о-чень далеко!

В.В.Золотарёв Обзор по кодированию18 Пороговые декодеры: очень просто Пороговые декодеры: очень просто Обратим внимание: Это действительно простейшая схема исправления многих ошибок!

В.В.Золотарёв Обзор по кодированию19 Но эффективность ПД - мизерна! До Ро =0.11 тоже чрезвычайно далеко.

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

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

В.В.Золотарёв Обзор по кодированию22 Решенные проблемы МПД w 1. Полностью решена сложнейшая задача оценки размножения ошибок (РО) в ПД w 2. Построены коды с минимальным РО w 3. Созданы 4 поколения аппаратуры кодирования, реализующей алгоритм МПД. w 4. Самое главное : Сохранена минимально возможная сложность декодирования, характерная для обычного ПД. w 5. Следствие. МПД и при высоких уровнях шума работает почти как ОД. w 6. ИТОГ. Создание эффективного декодера - решенная в принципе проблема.

В.В.Золотарёв Обзор по кодированию23 Нижние оценки вероятностей ошибки оптимального приема свёрточных кодов с R=1/2 по алгоритму Витерби и МПД в ДСК. 2.0

В.В.Золотарёв Обзор по кодированию24 А что надо для техники связи? w «Снижение энергетики канала связи на 1 дБ дает экономическую эффективность в миллион долларов» - Э. Р. Берлекэмп. Техника кодирования с исправлением ошибок. ТИИЭР, 1980, т.68, 5. w В настоящее время при многократном росте стоимости сетей связи цена снижения энергетики многократно (!!!) возросла. Но как увязать вероятностные характеристики канала с его энергетикой ?

В.В.Золотарёв Обзор по кодированию25 Кодирование значительно снижает энергетику канала передачи ! w Величина снижения называется энергетическим выигрышем кодирования (ЭВК) ЭВК = 10*Lg(R*d) дБ w w Связисты давно знают, как изменить приёмник для увеличения ЭВК w А где границы снижения энергетики?

В.В.Золотарёв Обзор по кодированию26 Как связисты улучшают ёмкость (пропускную способность) канала? Как связисты улучшают ёмкость (пропускную способность) канала? И спользуют «мягкий» модем, оценивающий надежность приёма (амплитуду) сигнала, а не «жёсткий», который только выносит решение о значении принятого бита. Это позволяет снизить энергетику сигнала примерно на 2 дБ. Распределение выходного напряжения «мягкого» модема с квантованием на 16 уровней оценок амплитуды сигнала показано на рисунке. « - » « + »

В.В.Золотарёв Обзор по кодированию27 Минимально возможное отношение энергии на бит передаваемой информации к мощности шума канала E b /No для различных кодовых скоростей R может быть представлено для жёсткого и мягкого модемов так

В.В.Золотарёв Обзор по кодированию28

В.В.Золотарёв Обзор по кодированию29 Лучшие решения - каскадные! Лучшие решения - каскадные! При этом кодирование осуществляется двумя и более кодами, которые в приемнике декодируются в обратном порядке и при определенном взаимодействии декодеров. На практике получили широкое распространение каскадные схемы из свёрточного кода, декодируемого по алгоритму Витерби, и кода Рида-Соломона. На графике - лучшие известные результаты по эффективности в гауссовском канале

В.В.Золотарёв Обзор по кодированию30 Но!! МПД на 2 порядка проще!

В.В.Золотарёв Обзор по кодированию31 Что будем использовать? - Наиболее простые и эффективные методы !!!

В.В.Золотарёв Обзор по кодированию г. т. (095) моб.: