МПД Золотарёва принцип. Вопрос 31 Как ещё можно иначе описать работу мпд Те описания, которые есть в книгах
 Скачать 456.35 Kb.
|
Вопрос 31 Как ещё можно иначе описать работу МПД? Те описания, которые есть в книгах, достаточно формальны. Для некоторых читателей это сложно. А можно посмотреть на эти декодеры Золотарёва как-то более качественно, образно? Ответ на вопрос 31 Как ещё иначе можно посмотреть на работу МПД? Один из наших студентов посмотрел на схему декодера Золотарёва в комиксе про ОТ и МПД на сайте www.mtdbest.ru и за минуту нарисовал вот такую картинку. А когда мы спросили его, что это такое, он нам объяснил, что так он видит процесс работы этого алгоритма. Сходимость процедур глобального поиска для МПД декодеров A Start X=A+E W 0 =|E| w 1 w m Ws W s >W m >W 1 >W 0 ? Рис. 1 Поскольку обсуждаемый код линеен, то давайте полагать, что при какой-то большой вероятности искажений передачи символов кода посылается нулевое сообщение. Выбор передаваемого сообщения, которое является кодовым словом, не влияет на вероятность ошибки решения декодера. При передаче к кодовому вектору А добавился вектор шума E, вес которого равен |E|. В нашем случае вес – число единичек в двоичном векторе. В декодер поступит вектор X=A+E. ОД должен найти кодовое слово такое, что оно среди всех возможных было бы самым близким к вектору X. Так как А – нулевой вектор, то вес X такой же, как у E : |X|=|E|. И пусть сообщение А - ближайшее к Х, т.е. А – решение ОД. Мы тут же спросили студента, а как он будет рассказывать про свою картинку, если вектор шума имеет столь большой вес, что уже А – не решение ОД. И он почти мгновенно порадовал нас чётким ответом, что в этом случае совершенно ничего не изменится вообще, так как он рассказывает о процессе сходимости решений МПД к решению ОД, а не к правильному решению. Так что для того, чтобы не мешать пониманию картинки, наш студент сразу предложил считать, что вектор Е не столь «тяжёл» и отправленное сообщение А – это именно и решение ОД. А далее у него оказалось ещё интереснее. Как известно, в МПД, как во многих других декодерах, сначала выполняется простейшая процедура вычисления вектора синдрома для принятого сообщения (посмотрите про эту операцию в книгах). И вот при этом получаем некоторый стартовый вариант решения МПД, от которого начинается процесс поиска решения ОД. Этот вариант показан голубой точкой Start на краю рисунка, дополнительно помеченной символом Ws . Этим знаком обозначен вес разности точки Start и принятого вектора Х. И эта точка лежит на некоторой круговой линии, на которой находятся все решения, у которых вес разности с Х равен Ws. Вес Ws всегда реально много больше, чем |E|, Ws>>|E|. На внутренних кругах лежат другие решения, расстояния Wm до которых от вектора Х уменьшаются по мере их приближения к Х. Общее количество решений декодера, лежащих на различных кругах, растёт экспоненциально с ростом длины кода. В этом случае процесс декодирования становится таким, что, согласно рисунку для блокового МПД в комиксе, данные в нём двигаются синхронно и циклически, а пороговые элементы при этом постепенно корректируют контролируемые информационные символы. А на обсуждаемой диаграмме в процессе коррекции ошибок декодер просматривает на текущем круге веса Wm (но сначала, конечно, на круге веса Ws !) возможность перейти с него на один из внутренних кругов, каждый из которых является геометрическим местом решений, которые находятся на некотором одинаковом расстоянии Wn от Х, причём Wm>Wn. Однако при этом пороговые элементы в декодере Золотарёва таковы, что переход на внутренний круг возможен только тогда, когда новое решение на этом внутреннем круге меньшего веса будет отлично от предыдущего решения точно в одном информационном символе. И в этом условии заключается та величайшая проблема мажоритарных алгоритмов, которая была сформулирована и потом успешно полностью решена теорией размножения ошибок (РО). Но если она не решена, то обычно декодер будет с какого-то момента просто бегать по кругу некоторого веса Wm, Wm>W 0 Возможность такой неудачи показана последней пунктирной стрелкой к решению А, которая подчёркивает красным вопросительным знаком отсутствие гарантии достижения алгоритмом в конце процесса декодирования итогового правильного решения А . Но если использовать все возможности РО и строить только правильные коды по критериям РО, то даже при большом шуме непростой по своим условиям поиск на кругах диаграммы студента будет почти всегда продолжаться до момента попадания декодера в решение А, ближайшее к принятому вектору Х, как мы договорились об этом перед началом рассмотрения студенческого слайда. А ещё наш студент сказал, что текущее условие о единственности измененного символа в очередном решении МПД после каждого события коррекции блока является очень жёстким, но совсем необязательным. Он предложил найти другое решающее правило для декодеров Золотарёва и менять символы блока группами или даже ещё каким-то другим способом, что может улучшить характеристики декодирования при большом уровне шума. Вполне очевидно, что главное условие тут – сохранение линейной от длины кода сложности, - можно выполнить. А вот конкретный вид новой решающей функции – это очень непростая задача. Её, возможно, скоро решит наш студент или другие участники научной школы ОТ. Это будет очередной шаг дальнейшего развития теории размножения ошибок (РО) в МПД. Интересно, кто же всё-таки её решит. Да, кто? Студент, мы или, может быть, – Вы ? Мы согласны. Успехов вам! Вопрос 32 Почему теория МПД настолько сложна? И как можно попроще оценить характеристики алгоритмов Золотарёва. Ответ на вопрос 32 О совершенстве ОТ и её компактности Весьма важным является место ОТ и её соотношение с классической теорией кодирования. Очень условной качественной картинкой, иллюстрирую- щей эти отношения, является приводимый ниже слайд, который, тем не менее, даёт простые ответы на эти вопросы. Главный ответ: наоборот, ОТ крайне проста. Это очевидно уже потому, что основа ОТ - многопороговые декодеры Золотарёва, которые являют мажоритарными декодерами, т.е. простейшими алгоритмами, известными уже 50 лет. Их отличие от декодеров Дж. Месси принципиально с точки зрения теории, но по существу это те же декодеры великого американского учёного, изменённые очень незначительно, но так, что они стали на каждом шаге приближаться к решению оптимального , т. е. наилучшего по минимуму вероятности ошибки декодера (ОД). The sizes of « classic » and ОТ • . ОТ «Classic theory» 1/10 8 The level of OT compactness 1000 times!!! Анализ всех монографий по ОТ, которые были изданы нашей научной школой в этом тысячелетии, показывает, что все они являются системно- философскими трактатами по теории информации с крайне ограниченным использованием сложной математики. Некоторым исключением являются те разделы ОТ, которые относятся к основам теории размножения ошибок (РО) и её приложениям к конкретным кодам. Совершенно ясно, что столь новый важный и очень оригинальный раздел теории кодирования, который не смогли за прошедшие 50 лет открыть, исследовать и понять никакие научные группы в России и в зарубежье, и не мог быть очень простым. И, тем не менее, после полного анализа и описания столь сложного явления, как РО, последовавшие из его понимания выводы и технологии оказались также понятны и естественны. РО показала, что надо строить коды с самой минимально возможной зависимостью проверок относительно декодируемых символов между собой. Иначе говоря, коды должны быть такими, чтобы для любой пары декодируемых символов число общих ошибок в проверках должно быть минимально возможным. А этого уже можно достичь на основе понятных вычислительных процессов. Этот вывод, который невозможно сделать без теории РО, привёл к простым алгоритмам создания таких кодов, которые тоже укладывались в концепцию простых методов с ясными и понятными итоговыми критериями качества кодов. Общее число новых математических соотношений в характеристиках методов ОТ оказалось совсем небольшим и ограничено теперь буквально несколькими десятками новых формул. А из прежней прикладной теории кодирования в ОТ используются только несколько простых преобразований, которые позволяют вычислять вероятность ошибки в первом символе используемого двоичного блокового или свёрточного кода P 1 (e) для двоичного симметричного канала. На слайде показана цепочка из простейших вычислений на базе производящих функций вероятности (ПФВ), позволяющая вычислить это удобный для всех предварительных оценок параметр мажоритарного декодера. Общий результат - единственный Вероятность ошибки порогового декодера в первом символе кода P 1 (e). Так как проверка неправильна с вероятностью p J = 0,5[1 – (1–2p 0 ) J ] . Тогда через ПФВ вида получаем вероятность ошибки в первом символе И ЭТО ВСЁ ! d m m m J J J x a q x p q x p x A 0 0 0 ) )( ( ) ( d d m m a e P 2 / ) 1 ( 1 ) ( Всё это, тем не менее, позволяет рассчитывать все необходимые характеристики декодирования методами ОТ во всех классических каналах, рассматриваемых в теории кодирования для любых алгоритмов нашей ОТ - новой «квантовой механики» теории информации. Описанная ситуация и представлена на слайде, где изображены почти абсолютно независимые прежняя «классическая» и новая оптимизационная часть прикладной теории кодирования. Соединяющее их маленькое красное пятнышко, которым мы обозначили несколько выражений, составляющих тменно предложенный Дж. Месси метод вычисления вероятности P 1 (e ), т.е. слайда выше – это всё, что их объединяет. ОТ – полностью переписанная прикладная теория кодирования. И указанные на слайде соотношения для размеров этих двух теорий: новой ОТ и старой «классической» - действительно примерно соответствуют трём десятичным порядкам по объёму информации. Условная доля формул для P 1 (e) действительно ничтожна и указанная их часть – это фактически просто их качественная оценка. Ну, и отметим, наконец, что вся ОТ очень наглядна и абсолютно понятна. Так что: - учите, пожалуйста! В ОТ не наберётся и 30 активно используемых формул. ОТ – это очень просто! Но результаты – наилучшие, оптимальные ! |