Научная сессия ОНИТ Научная сессия ОНИТ Новая оптимизационная теория кодирования и её прикладные достижения 24.04.2008 г. В.В.Золотарёв, ИКИ РАН. - презентация

1 Научная сессия ОНИТ Научная сессия ОНИТ Новая оптимизационная теория кодирования и её прикладные достижения г. В.В.Золотарёв, ИКИ РАН

2 В.В.Золотарёв. Теория кодирования2 Главная фундаментальная научная проблема перехода от аналоговой связи и информатики к цифровой Обеспечение высокого уровня достоверности формирования, обработки, передачи и хранения цифровых данных. Обеспечение высокого уровня достоверности формирования, обработки, передачи и хранения цифровых данных. Средство решения этой проблемы – методы теории помехоустойчивого кодирования Средство решения этой проблемы – методы теории помехоустойчивого кодирования академика В.А.Котельникова. Теоретической основой однозначного точного восстановления аналогового сигнала является теорема отсчётов академика В.А.Котельникова. теореме Шеннона. При переходе нашей технологической цивилизации к передаче и хранению информации в дискретном виде главным требованием к таким системам, становится их соответствие теореме Шеннона. В этом случае можно всегда восстановить в приёмнике цифровое сообщение, искажённое в канале связи, со сколько угодно малой вероятностью ошибки, если длина кодового блока будет расти. Эта теорема положила начало современной теории кодирования.

3 Кодирование - это введение избыточности K - информация + R - избыточные символы R=k/n

4 В.В.Золотарёв. Теория кодирования4 С C

5 В.В.Золотарёв. Теория кодирования5 Основное ограничение теории информации для кодирования R

6 В.В.Золотарёв. Теория кодирования6 Что нужно от кодов для сетей связи? Что нужно от кодов для сетей связи? Это - энергетический выигрыш, ЭВК!, - мера эффекта увеличения энергии сигнала. Это - энергетический выигрыш, ЭВК!, - мера эффекта увеличения энергии сигнала. Сейчас каждый дополнительный 1 дБ ЭВК даёт в сетях связи экономический эффект во многие миллионы долларов! Сейчас каждый дополнительный 1 дБ ЭВК даёт в сетях связи экономический эффект во многие миллионы долларов! Ресурс ЭВК можно реализовать при ДЗЗ для снижения размеров антенн, а также для увеличения скорости, надёжности и дальности связи. Это исключительно важно для спутниковых систем связи типа VSAT, а также проектов микро- и нано- спутников или других высокоскоростных систем связи. Достигается только правильной быстрой математической обработкой цифрового потока! Ресурс ЭВК можно реализовать при ДЗЗ для снижения размеров антенн, а также для увеличения скорости, надёжности и дальности связи. Это исключительно важно для спутниковых систем связи типа VSAT, а также проектов микро- и нано- спутников или других высокоскоростных систем связи. Достигается только правильной быстрой математической обработкой цифрового потока!

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

8 В.В.Золотарёв. Теория кодирования8 Сложность декодеров разных типов для кодов длины n enen АВ!!! МПД Дискр. алгебр.

9 В.В.Золотарёв. Теория кодирования9 Блоковый многопороговый декодер для кода с R=1/2, d=5 и I итерациями МПД, сложность- N~d*I*n

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

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

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

13 В.В.Золотарёв. Теория кодирования13 Чипсет МПД декодера на ПЛИС Xilinx для каналов со скоростями до 150 Мб/с

14 В.В.Золотарёв. Теория кодирования14 Многопороговый декодер (МПД) для спутниковых и космических каналов связи, повышает кпд их использования в раз, в том числе для ДЗЗ. МАКЕТ МПД на ПЛИС Altera для каналов на 640 Мбит/с. Метод работает на информационных скоростях до 1,6 Гбит/с МПД – для космоса!

15 В.В.Золотарёв. Теория кодирования15 Новая научная и технологическая революция – передача цифровых данных с минимальной энергетикой С, дБ

16 В.В.Золотарёв. Теория кодирования16 Символьный многопороговый декодер для кода с R=1/2, d=5 и I итерациями QМПД- недвоичный ?

17 В.В.Золотарёв. Теория кодирования17 Добро пожаловать! Гости сайта ИКИ РАН в марте 2008 г. Более посетителей нашего веб-сайта из 50 стран переписали более 7 Гбайтов данных об МПД алгоритмах за последний год. ??? USAСеть

18 В.В.Золотарёв. Теория кодирования18

19 В.В.Золотарёв. Теория кодирования19 Чипсет МПД декодера на ПЛИС ALTERA

20 В.В.Золотарёв. Теория кодирования20 Сложность различных алгоритмов декодирования Коды и алгоритмы Алгоритм Витерби Алгоритм Витерби Алгебраические коды Алгебраические коды Турбо коды Турбо коды Низкоплотностные коды Низкоплотностные коды Мажоритарные коды - Мажоритарные коды - - только в России – МПД, который почти всегда сходится к оптимальному (переборному!) решению, но с линейной сложностью Сложность 2 n 2 n n 2 n 2 C 1 n C 1 n C 2 n C 2 n C 3 n С 3

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

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

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

24 В.В.Золотарёв. Теория кодирования г. ИКИ РАН т.(495) , ИКИ РАН т.(495) , моб.: В.В.Золотарёв