Многопороговые декодеры и оптимизационная теория кодирования

В. В. Золотарёв, Ю. Б. Зубарев, Г. В. Овечкин

МНОГОПОРОГОВЫЕ ДЕКОДЕРЫ 
И ОПТИМИЗАЦИОННАЯ 
ТЕОРИЯ КОДИРОВАНИЯ

 Под редакцией академика РАН 
         В. К. Левина

Москва
Горячая линия - Телеком
2012

 

ББК 32.811.4 
        З-80        
 
Рецензенты: 
профессор, доктор технических наук, заведующий кафедрой 
 радиотехнических систем МТУСИ  Ю.С.  Шинаков; 
профессор, доктор технических наук, заведующий кафедрой телекоммуникаций 
и основ радиотехники РГРТУ  В.В. Витязев 
 
        Золотарёв В.В., Зубарев Ю.Б., Овечкин Г.В. 
З-80       Многопороговые декодеры и оптимизационная теория кодирования /  
       Под ред. академика РАН В.К. Левина. – М.: Горячая линия – Телеком,  
       2012. – 239 с., ил. 
        ISBN 978-5-9912-0235-0 

Изложены основные принципы современной оптимизационной теории помехоустойчивого кодирования и следующие из нее алгоритмы многопорогового декодирования (МПД). Эти итеративные алгоритмы при каждом изменении корректируемых ими символов всегда находят строго более правдоподобные решения.  
Рассмотрены возможности открытых авторами символьных кодов и соответствующих им простых в реализации специальных символьных МПД, которые  намного проще и эффективнее всех других известных методов декодирования недвоичных кодов. Оцениваются границы эффективности реальных кодов при равенстве 
пропускной способности канала и кодовой скорости, т.е. при R=C. Сравнивается 
сложность различных алгоритмов коррекции ошибок.  
Для специалистов в области теории и техники кодирования, разработчиков 
систем связи, студентов и аспирантов соответствующих специальностей. 
ББК 32.811.4 
 
Адрес издательства в Интернет www.techbook.ru 
 
Научное издание 
 
Золотарёв Валерий Владимирович 
Зубарев Юрий Борисович 
Овечкин Геннадий Владимирович 
 
МНОГОПОРОГОВЫЕ ДЕКОДЕРЫ И ОПТИМИЗАЦИОННАЯ 
ТЕОРИЯ КОДИРОВАНИЯ 
 
 
Компьютерная верстка И.Н. Алексеевой 
Обложка художника В.Г. Ситникова 
 
Подписано в печать 21.01.2012. 
Формат 60×90/16. Уч.-изд. л. 14,93. Тираж 500 экз. (1-й завод 100 экз.) 
 
ISBN 978-5-9912-0235-0                                                      ©  Золотарёв В.В., Зубарев Ю.Б., 
                                                                                                       Овечкин Г.В., 2012 
                                                                                      ©  Оформление издательства 
                                                                              «Горячая линия – Телеком», 2012 

Предисловие научного редактора 

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

Однако, несмотря на большой прогресс в теории и в микроэлектронной технологии, характеристики систем кодирования и последующего декодирования до конца 80-х годов оставались все еще 
весьма далекими от теоретически возможных пределов.  
Только появление в 1993 году турбо кодов показало специалистам, что практически полное использование емкости цифровых каналов связи оказывается уже вполне решаемой технической задачей. Множества турбо подобных и некоторых других 
кодов доказали, что действительно существует реальная возможность гораздо более эффективного использования пропускной способности очень дорогих космических, спутниковых и 
многих других цифровых каналов связи, чем это было возможно 
до сих пор. Энергетика гауссовских каналов при использовании 
некоторых кодов этих классов может быть, в принципе, всего на 
несколько десятых долей децибела более высокой, чем это определяется основным теоретическим ограничением: равенством 
кодовой скорости и пропускной способности канала.  
Последующие достижения и перспективы теории кодирования обычно связывают с низкоплотностными (LDPC) кодами. 
Их сложность декодирования была немного меньшей, чем у 
турбо кодов, но все же еще слишком высокой. Тем не менее, 
промышленность освоила производство целого ряда декодеров 
и этого типа, что позволило говорить о дальнейшем прогрессе 
техники кодирования.  
Вместе с тем все примеры использования турбо и LDPC кодов с приемлемыми параметрами в очередной раз показали, что 
характеристики декодеров для этих кодов заметно ухудшаются в 
реальных условиях их создания из-за вынужденных упрощений 
самих алгоритмов по сравнению с идеальными условиями их моделирования в исследовательских лабораториях. Заметное снижение энергетического выигрыша кодирования (ЭВК) – параметра, непосредственно характеризующего полезность кодов для 
систем, например, спутниковой связи, – достигает при создании 
реальных декодеров этих типов величины 0,5…1,0 дБ, что и свидетельствует о том, что главная задача кодирования: исправлять 
проще, быстрее и при более высоком уровне шума – еще очень 
далека от своего окончательного решения. Следует также указать 
на то, что и быстродействие декодеров указанных выше кодов, 

реализованных с учетом всех достижений микроэлектроники, 
остается далеко не столь высоким, как это часто требуется, что 
также сильно ограничивает область их использования. 
Необходимо отметить, что полезность применения кодирования, например, в технике связи при передаче двоичных данных обычно определяется именно параметром ЭВК, который 
просто характеризует величину эффекта увеличения мощности 
передатчика системы связи, использующей хорошие методы 
кодирования и, главное, последующего декодирования принятого цифрового потока. А поскольку эта величина может достигать 3, 5 и даже 10 и более раз (свыше 10 дБ), то становится понятным исключительная важность кодирования, которое создает 
системе связи столь большой запас по мощности. Если в 1980 
году известный американский специалист, автор классических 
книг по теории кодирования Э. Берлекэмп в одном из своих обзоров утверждал, что каждый децибел снижения энергетики канала связи оценивается в миллион долларов, то при современном масштабе цифровых сетей экономическая ценность применения кодирования возросла еще во много десятков раз. Это 
происходит в результате появления возможности существенного 
повышения скорости передачи цифровых данных, значительного снижения размеров очень дорогих антенн, многократного 
увеличения дальности связи, а также многих других весьма 
важных достоинств цифровых систем связи, использующих помехоустойчивое кодирование. Этим и определяется важность 
для всей отрасли телекоммуникаций работ по созданию эффективных декодеров, в связи с чем на десятках ежегодных международных конференций вопросы помехоустойчивого кодирования всегда оказываются среди самых актуальных.  
Текущее состояние исследований и применения недвоичных 
кодов и алгоритмов их коррекции еще более проблемно. Через 50 
лет после открытия кодов Рида–Соломона (РС) оказывается, что 
наилучшими и единственно реализованными декодерами для недвоичных кодов до сих пор остались именно они. Но даже текущее состояние технологии создания декодеров для недвоичных 
кодов по-прежнему не позволяет использовать коды РС длиннее 
255 символов. Поэтому для новых дисков Blue-Ray и в других 
сложных системах защиты и надежного хранения символьных 

(байтовых) данных все еще используют различные комбинации,               
в том числе и каскадные, именно коротких кодов РС. Это мало 
повышает достоверность и защищенность хранимых данных при 
большом уровне искажений, одновременно заметно увеличивая 
требуемую для таких схем избыточность и существенно снижая 
скорость обработки. 
Таким образом, реальное состояние теории кодирования, 
имеющегося множества конкретных методов кодирования и, 
главное, декодирования, в настоящее время далеко от их потенциальных возможностей. Даже в случае достижения высоких вычислительных мощностей аппаратуры параметры имеющихся 
декодеров разных типов остаются все еще далекими от требований простоты реализации при высокой достоверности декодированного цифрового потока в случае высокого уровня шума. 
Новое очень эффективное решение проблемы сложности 
декодирования при одновременной реализации высоких энергетических характеристик систем кодирования на базе многопороговых декодеров (МПД) ясно и доступно изложено в предлагаемой читателю книге известных российских специалистов в области помехоустойчивого кодирования члена-корреспондента 
РАН Ю.Б. Зубарева, профессора В.В. Золотарёва и доктора технических наук Г.В. Овечкина. Первые авторские свидетельства 
на изобретения, закрепляющие приоритет СССР в разработке 
этого удивительно простого и очень эффективного метода, относятся к 1972 году. За истекший 40-летний период разработки 
и исследований методов помехоустойчивого кодирования авторами этой книги создана всеобъемлющая оптимизационная теория помехоустойчивого кодирования. 
Она фактически уже позволила решить на хорошем прикладном уровне все основные задачи создания кодов для МПД, 
оптимизации параметров декодеров и найти новые классы задач, 
которые могут быть решены с использованием их новой плодотворной теории.  
МПД алгоритмы, как и большинство декодеров для турбо и 
LDPC кодов, являются итеративными процедурами. Однако 
турбо коды появились на 20 лет позже многопороговых декодеров, которые и в те годы, и в настоящее время продолжают 
весьма динамично развиваться и интенсивно патентуются.  

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

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

гаемые только на основе переборных алгоритмов. При этом общее число операций МПД все равно остается весьма небольшим. 
Но на самом деле успех разработок МПД алгоритмов связан               
с решением еще одной, третьей классической задачи оптимизации 
функционала от очень большого числа переменных. Как совершенно справедливо указывают авторы, возможность одновременной вариации целого ряда параметров кодов и декодеров, в частности, весов проверок, значений пороговых элементов и разностных 
соотношений в полиномах используемых кодов создает дополнительные условия для улучшения характеристик МПД декодеров. 
Таких настраиваемых элементов в декодерах может быть много 
сотен и даже тысяч. Автоматизированный компьютерный поиск 
оптимизированных по критериям вероятности ошибки решений 
декодера параметров алгоритмов еще на этапе его проектирования 
заметно улучшает и так достаточно высокие характеристики МПД 
вообще без какого-либо увеличения объема вычислений декодера с 
такими улучшенными параметрами. Заметим, что постановку этой 
третьей проблемы для других систем декодирования даже невозможно вообразить, поскольку она может возникнуть только параллельно с решением первых двух описанных выше проблем эффективного и простого декодирования для МПД алгоритмов.  
Таким образом, успех теории и прикладных достижений в области простого и эффективного декодирования средствами МПД 
определяется одновременным успешным решением трех вышеприведенных сложнейших проблем, каждая из которых так или 
иначе связана с решением задач оптимизации функционалов от 
большого числа переменных. Именно в плодотворном применении 
оптимизационных принципов на всех этапах разработок и исследований МПД и заключается успешность новой теории кодирования для теории информации и техники связи. Отсутствие удовлетворительных решений хотя бы одной из них многократно понизило бы ценность возможных достижений в области итеративных 
мажоритарных схем декодирования, поскольку все их характеристики в этом случае были бы весьма и весьма скромными.  
В книге представлены и другие очень необычные для традиционных способов декодирования методы. Фактически все 
они служат главной цели: максимальному росту эффективности 
декодера при минимальной сложности его схемы. К ним можно 

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