Семинар ИКИ Использование новейших методов помехо- устойчивого кодирования в проектах исследования космоса 14.09.2004 г. В.В.Золотарёв, ИКИ РАН. - презентация

1 Семинар ИКИ Использование новейших методов помехо- устойчивого кодирования в проектах исследования космоса г. В.В.Золотарёв, ИКИ РАН

2 Кодирование - это введение избыточности.. K-Информация + R- избыточные символы R=k/n - кодовая скорость n=k+r - длина блока Примеры: коды контроля по чётности: r=1 Коды Хемминга: r=log 2 n - исправляют одну любую ошибку, d=3 Число исправляемых ошибок t: d=2t+1, где d - кодовое расстояние - главный параметр, характеризующий отличия сообщений между собой

3 В.В.Золотарёв. Кодирование - Космосу! 3 Главное ограничение теории информации для помехоустойчивого кодирования Всегда должно выполняться условие: R < C ! Здесь: R - кодовая скорость, C - пропускная способность канала. В этом случае возможна передача цифровых данных с произвольно малой вероятностью ошибки после декодирования.

4 В.В.Золотарёв. Кодирование - Космосу! 4 Предельные возможности кодов С- пропускная способность канала

5 В.В.Золотарёв. Кодирование - Космосу! 5 По возможности- кодировать проще!!! Пример кодера для свёрточного...кода с той же кодовой скоростью R=1/2...(помещается на передающей стороне, ЛА)

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

7 Что нужно от кодов для сетей связи? Проф. Берлекэмп (США) указал в 1980г. в обзоре, опубликованном в ТИИЭР: Это - энергетический выигрыш!, - мера эффекта увеличения энергии сигнала, оцениваемая как ~$1 миллион на 1 дБ ЭВК. Теперь это ещё более важно. { см. обзор в журнале Электросвязь 9, 2003; его перевод на английский также представлен на нашем веб-сайте ИКИ } Сейчас каждый дополнительный 1 дБ ЭВК даёт в больших сетях экономический эффект в сотни миллионов долларов! Это-размеры антенн, скорость, надёжность и дальность связи

8 Пример расчёта ЭВК Пусть задан код с d=11 и R=1/2. Требуемая вероятность ошибки ; 9,6 дБ Вероятность ошибки канала p 0 =0,056; 1,0 дБ. Поскольку R=1/2, то E b /N 0 =4 (т.к. это +3дБ) Есть декодер с результирующей вероятностью ошибки P dec =462*p 0 (d-1)/2. Тогда P dec =10 -5 ЭВК = 9,6 - 4 =5,5 дБ. В частности, алгоритм Витерби реализует при этих данных ЭВК~5 дБ.

9 В.В.Золотарёв. Кодирование - Космосу! 9 Предельный энергетический выигрыш кодирования (ЭВК) из условия R

10 В.В.Золотарёв. Кодирование - Космосу! 10

11 Главные проблемы техники кодирования 1. Декодировать – проще!. 2. Достоверность – выше!. 3. Максимально учитывать условия кодирования в реальных системах связи 4. Как всего этого достичь? Многопороговыми декодерами!!!

12 В.В.Золотарёв. Кодирование - Космосу! 12 Принцип численного итеративного решения уравнения f(x)=0 (с 1972г.) - в течение 6 лет был перенесён в технику кодирования. На Западе этот подход открыли только в 1993г. (турбо коды)

13 В.В.Золотарёв. Кодирование - Космосу! 13 Многопороговое декодирование (МПД) –МПД многократно изменяет символы принятого сообщения и может при линейной сложности реализации достичь решения оптимального декодера (ОД). Это - результат применения итеративного подхода к коррекции ошибок, открытого у нас на 22 года раньше, чем на Западе. Обычно цена оптимального декодирования ( как для алгоритма Витерби) - полный перебор, а сложность МПД - всего лишь линейная функция от длины кода!!! ( как для алгоритма Витерби) - полный перебор, а сложность МПД - всего лишь линейная функция от длины кода!!!

14 В.В.Золотарёв. Кодирование - Космосу! 14 Рис. 1. Многопороговый декодер сверточного СОК с R=1/2, d=5 и n A =14 Свёрточный многопороговый декодер для кода с R=1/2, d=5 и 3 итерациями

15 Минимум вычислений при декодировании - в МПД! (Число операций на бит, программная реализация) Обычно : N 1 = C 0 * d*I, а в МПД: только N 2 = C 1 *d+ C 2 *I, - сумма основных параметров d и I вместо их произведения, (здесь: С i - небольшие целые числа, а d – кодовое расстояние, I-число итераций) Это в ~100 раз проще и быстрее, чем, например, при использовании турбо кодов! Реализован в специальной TV- системе.

16 Причины высокой эффективности нового МПД метода 1. Применена специальная очень легкая для реализации итеративная процедура. 2. Построены специальные коды с минимальным уровнем группирования ошибок. 3. Осуществлена оптимизация многих сотен параметров декодера. Задачи 1 и 2 - «очень трудны» Задача 3 - даже не ставилась

17 В.В.Золотарёв. Кодирование - Космосу! 17 Пример простейшего кодера на борту

18 Аппаратная реализация МПД на ПЛИС 1. МПД состоит почти полностью из элементов памяти или регистров сдвига. Это наиболее быстрые элементы и ПЛИС, и БИС. Доля остальных элементов МПД много менее 1 %. 2. МПД состоит из параллельно работающих регистров сдвига и однотактных пороговых элементов с мгновенной реализацией своих функций. Именно поэтому МПД для некоторых значений параметров примерно в 1000 более быстрые, чем другие, например, турбо декодеры. 3. Реализация: Скорость Мбит/с, ЭВК= 6,5 - 8,5 дБ

19 В.В.Золотарёв. Кодирование - Космосу! 19

20 В.В.Золотарёв. Кодирование - Космосу! 20 Новая научная и технологическая революция – передача при минимальной энергетике

21 В.В.Золотарёв. Кодирование - Космосу! 21 Что будем использовать? - Только наиболее простые и эффективные методы !!! МПД-К

22 В.В.Золотарёв. Кодирование - Космосу! 22 Добро пожаловать! Гости сайта ИКИ РАН в марте 2004 г. Более 5000 посетителей нашего веб-сайта переписали около 1 Гбайта данных об алгоритмах МПД в 2004 г.

23 В.В.Золотарёв. Кодирование - Космосу! 23 Применение наиболее мощных систем кодирования канала и источника 1. Кодирование канала. Повышает достоверность передачи данных на 2-5 десятичных порядков, ЭВК~8-12 дБ 2. Кодирование источника. Достигается сжатие данных в 2-5 и более раз. 3. Общий итоговый энергетический выигрыш от применения методов теории информации - до раз !

24 В.В.Золотарёв. Кодирование - Космосу! 24 Выводы 1. Мы открыли итеративные МПД алгоритмы 32 года назад. 2. Сложность программной версии МПД - это абсолютный известный сейчас минимум вычислений. Разница с турбо кодами по числу операций ~100 раз! 3. Аппаратные МПД быстрее турбо кодов ~1000 раз! 4. Решения МПД достаточно быстро стремятся к решениям оптимального декодера (ОД) 5. МПД - абсолютный лидер среди всех алгоритмов по критериям сложность-эффективность. 6. Поэтому мы навсегда опередили все другие алгоритмы! Мы мировые лидеры в кодировании!

25 В.В.Золотарёв. Кодирование - Космосу! г. ИКИ РАН т.(095) , моб.: В.В.Золотарёв ИКИ РАН т.(095) , моб.: В.В.Золотарёв