В. В. Золотарёв, Ю. Б. Зубарев, Г. В. Овечкин
МНОГОПОРОГОВЫЕ ДЕКОДЕРЫ
И ОПТИМИЗАЦИОННАЯ
ТЕОРИЯ КОДИРОВАНИЯ
Под редакцией академика РАН
В. К. Левина
Москва
Горячая линия - Телеком
2012
Стр.1
ББК 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
Стр.2
Предисловие научного редактора
Развитие современной цивилизации во все большей степени
базируется на использовании информационных технологий.
Сейчас они переживают бурный процесс перевода в цифровой
формат, что позволяет организовать процессы создания, передачи,
хранения и обработки данных на принципиально новой основе,
гарантирующей высокую степень целостности и доступности
цифровой информации.
Однако эта фаза развития информационных технологий характеризуется
весьма быстрым и значительным повышением
требований к достоверности цифровых данных. Ведущую роль
в обеспечении высокого уровня надежности и качества передачи
и хранения дискретной информации играют современные методы
помехоустойчивого кодирования.
За более чем полувековую историю развития теории и техники
помехоустойчивого кодирования основные методы и подходы
к решению главной проблемы этой научной дисциплины –
максимально простого и одновременно очень эффективного декодирования
– неоднократно и весьма существенно менялись.
Если сначала ведущими направлениями теории кодирования
были разработки алгоритмов исправления ошибок на базе алгебры
конечных полей, то затем наступила эра алгоритма Витерби.
Этот алгоритм был с теоретической точки зрения максимально
сложным, переборным, но настолько эффективным, что
значительный период времени все развитие теории кодирования
и создание конкретных устройств исправления ошибок для
спутниковой связи было сконцентрировано именно на этом методе.
Правда, использовать длинные коды для алгоритма Витерби
было невозможно из-за проблемы экспоненциально растущей
с увеличением длины кода сложности декодирования.
Последовавший затем период дальнейшего поиска эффективных
методов кодирования успешно завершился внедрением в технику
связи каскадных кодов. При этом, как и предсказывала теория,
на практике действительно оказалось, что каскадные коды
позволяли при меньшей сложности декодирования по сравнению
с исходными некаскадными методами обеспечивать одновременно
и гораздо более высокие характеристики помехоустойчивости.
3
Стр.3
Однако, несмотря на большой прогресс в теории и в микроэлектронной
технологии, характеристики систем кодирования и последующего
декодирования до конца 80-х годов оставались все еще
весьма далекими от теоретически возможных пределов.
Только появление в 1993 году турбо кодов показало специалистам,
что практически полное использование емкости цифровых
каналов связи оказывается уже вполне решаемой технической
задачей. Множества турбо подобных и некоторых других
кодов доказали, что действительно существует реальная возможность
гораздо более эффективного использования пропускной
способности очень дорогих космических, спутниковых и
многих других цифровых каналов связи, чем это было возможно
до сих пор. Энергетика гауссовских каналов при использовании
некоторых кодов этих классов может быть, в принципе, всего на
несколько десятых долей децибела более высокой, чем это определяется
основным теоретическим ограничением: равенством
кодовой скорости и пропускной способности канала.
Последующие достижения и перспективы теории кодирования
обычно связывают с низкоплотностными (LDPC) кодами.
Их сложность декодирования была немного меньшей, чем у
турбо кодов, но все же еще слишком высокой. Тем не менее,
промышленность освоила производство целого ряда декодеров
и этого типа, что позволило говорить о дальнейшем прогрессе
техники кодирования.
Вместе с тем все примеры использования турбо и LDPC кодов
с приемлемыми параметрами в очередной раз показали, что
характеристики декодеров для этих кодов заметно ухудшаются в
реальных условиях их создания из-за вынужденных упрощений
самих алгоритмов по сравнению с идеальными условиями их моделирования
в исследовательских лабораториях. Заметное снижение
энергетического выигрыша кодирования (ЭВК) – параметра,
непосредственно характеризующего полезность кодов для
систем, например, спутниковой связи, – достигает при создании
реальных декодеров этих типов величины 0,5…1,0 дБ, что и свидетельствует
о том, что главная задача кодирования: исправлять
проще, быстрее и при более высоком уровне шума – еще очень
далека от своего окончательного решения. Следует также указать
на то, что и быстродействие декодеров указанных выше кодов,
4
Стр.4
реализованных с учетом всех достижений микроэлектроники,
остается далеко не столь высоким, как это часто требуется, что
также сильно ограничивает область их использования.
Необходимо отметить, что полезность применения кодирования,
например, в технике связи при передаче двоичных данных
обычно определяется именно параметром ЭВК, который
просто характеризует величину эффекта увеличения мощности
передатчика системы связи, использующей хорошие методы
кодирования и, главное, последующего декодирования принятого
цифрового потока. А поскольку эта величина может достигать
3, 5 и даже 10 и более раз (свыше 10 дБ), то становится понятным
исключительная важность кодирования, которое создает
системе связи столь большой запас по мощности. Если в 1980
году известный американский специалист, автор классических
книг по теории кодирования Э. Берлекэмп в одном из своих обзоров
утверждал, что каждый децибел снижения энергетики канала
связи оценивается в миллион долларов, то при современном
масштабе цифровых сетей экономическая ценность применения
кодирования возросла еще во много десятков раз. Это
происходит в результате появления возможности существенного
повышения скорости передачи цифровых данных, значительного
снижения размеров очень дорогих антенн, многократного
увеличения дальности связи, а также многих других весьма
важных достоинств цифровых систем связи, использующих помехоустойчивое
кодирование. Этим и определяется важность
для всей отрасли телекоммуникаций работ по созданию эффективных
декодеров, в связи с чем на десятках ежегодных международных
конференций вопросы помехоустойчивого кодирования
всегда оказываются среди самых актуальных.
Текущее состояние исследований и применения недвоичных
кодов и алгоритмов их коррекции еще более проблемно. Через 50
лет после открытия кодов Рида–Соломона (РС) оказывается, что
наилучшими и единственно реализованными декодерами для недвоичных
кодов до сих пор остались именно они. Но даже текущее
состояние технологии создания декодеров для недвоичных
кодов по-прежнему не позволяет использовать коды РС длиннее
255 символов. Поэтому для новых дисков Blue-Ray и в других
сложных системах защиты и надежного хранения символьных
5
Стр.5
(байтовых) данных все еще используют различные комбинации,
в том числе и каскадные, именно коротких кодов РС. Это мало
повышает достоверность и защищенность хранимых данных при
большом уровне искажений, одновременно заметно увеличивая
требуемую для таких схем избыточность и существенно снижая
скорость обработки.
Таким образом, реальное состояние теории кодирования,
имеющегося множества конкретных методов кодирования и,
главное, декодирования, в настоящее время далеко от их потенциальных
возможностей. Даже в случае достижения высоких вычислительных
мощностей аппаратуры параметры имеющихся
декодеров разных типов остаются все еще далекими от требований
простоты реализации при высокой достоверности декодированного
цифрового потока в случае высокого уровня шума.
Новое очень эффективное решение проблемы сложности
декодирования при одновременной реализации высоких энергетических
характеристик систем кодирования на базе многопороговых
декодеров (МПД) ясно и доступно изложено в предлагаемой
читателю книге известных российских специалистов в области
помехоустойчивого кодирования члена-корреспондента
РАН Ю.Б. Зубарева, профессора В.В. Золотарёва и доктора технических
наук Г.В. Овечкина. Первые авторские свидетельства
на изобретения, закрепляющие приоритет СССР в разработке
этого удивительно простого и очень эффективного метода, относятся
к 1972 году. За истекший 40-летний период разработки
и исследований методов помехоустойчивого кодирования авторами
этой книги создана всеобъемлющая оптимизационная теория
помехоустойчивого кодирования.
Она фактически уже позволила решить на хорошем прикладном
уровне все основные задачи создания кодов для МПД,
оптимизации параметров декодеров и найти новые классы задач,
которые могут быть решены с использованием их новой плодотворной
теории.
МПД алгоритмы, как и большинство декодеров для турбо и
LDPC кодов, являются итеративными процедурами. Однако
турбо коды появились на 20 лет позже многопороговых декодеров,
которые и в те годы, и в настоящее время продолжают
весьма динамично развиваться и интенсивно патентуются.
6
Стр.6
Оглавление
Предисловие научного редактора ......................................................... 3
От авторов ............................................................................................. 13
Введение................................................................................................ 19
ГЛАВА 1. ЗАДАЧА КОДИРОВАНИЯ В ТЕХНИКЕ СВЯЗИ.............. 23
1.1. Линейные коды.............................................................................. 23
1.2. Единство блоковых и сверточных кодов..................................... 28
1.3. Каналы связи.................................................................................. 31
1.4. Каналы с многопозиционными системами сигналов ................. 33
1.5. Алгоритмы декодирования корректирующих кодов.................. 36
1.6. Эффективность декодирования.................................................... 38
1.7. Длины используемых кодов.......................................................... 44
1.8. Основные требования к новым алгоритмам................................ 45
ГЛАВА 2. ПРИНЦИП РОСТА ПРАВДОПОДОБИЯ РЕШЕНИЯ
МНОГОПОРОГОВОГО ДЕКОДЕРА..................................................... 47
2.1. Эффективность и сложность: выбор направления
исследований......................................................................................... 47
2.2. Принцип глобальной оптимизации функционала....................... 52
2.3. Алгоритм многопорогового декодирования ............................... 56
2.4. Гауссовский канал ......................................................................... 66
2.5. Недвоичные коды .......................................................................... 67
2.6. Декодирование в каналах со стираниями.................................... 73
2.7. Несистематические коды .............................................................. 74
2.8. Многопозиционные системы сигналов........................................ 76
2.9. Расширение области приложения принципов МПД................... 77
2.10. Выводы ......................................................................................... 78
ГЛАВА 3. РАЗМНОЖЕНИЕ ОШИБОК В МАЖОРИТАРНЫХ
ДЕКОДЕРАХ............................................................................................ 80
3.1. Понятие размножения ошибок ..................................................... 80
3.2. Вероятность первой ошибки порогового декодера самоортогонального
кода........................................................................................ 82
3.3. Размножение ошибок в сверточных самоортогональных
кодах ...................................................................................................... 84
3.4. Блоковые самоортогональные коды............................................. 90
3.5. Интегральные оценки размножения ошибок .............................. 95
3.6. Многопороговые процедуры для недвоичных кодов................. 97
3.7. Размножение ошибок в недвоичных кодах ............................... 103
3.8. Зависимость решений декодеров в каналах
со стираниями ..................................................................................... 107
237
Стр.237
3.9. Построение кодов с малым уровнем размножения
ошибок................................................................................................. 109
3.10. Выводы ....................................................................................... 110
ГЛАВА 4. АНАЛИТИЧЕСКИЕ ОЦЕНКИ ЭФФЕКТИВНОСТИ
МНОГОПОРОГОВОГО ДЕКОДИРОВАНИЯ..................................... 113
4.1. Методы оценок характеристик................................................... 113
4.2. Двоичные самоортогональные коды.......................................... 115
4.3. Нижние оценки вероятности ошибки недвоичного
оптимального декодера ...................................................................... 121
4.4. Характеристики мягких МПД алгоритмов................................ 123
4.5. Характеристики МПД для каналов со стираниями .................. 124
4.6. Границы эффективного использования мажоритарных
методов ................................................................................................ 126
4.7. Методы улучшения характеристик МПД.................................. 131
4.8. Улучшение оценок характеристик мягких МПД...................... 134
4.9. Выводы ......................................................................................... 137
ГЛАВА 5. ХАРАКТЕРИСТИКИ МНОГОПОРОГОВОГО
АЛГОРИТМА ......................................................................................... 138
5.1. Экспериментальные методы исследования............................... 138
5.2. Характеристики МПД в двоичном симметричном канале....... 139
5.3. Характеристики МПД в гауссовских каналах........................... 140
5.4. Символьные декодеры многопорогового типа ......................... 142
5.5. Декодирование в стирающих каналах ....................................... 147
5.6. Сложность программной реализации ........................................ 148
5.7. Требования к аппаратуре кодирования...................................... 151
5.8. Характеристики МПД декодеров на ПЛИС.............................. 153
5.9. ЭВК алгоритмов декодирования ................................................ 154
5.10. Выводы ....................................................................................... 157
ГЛАВА 6. ИСПОЛЬЗОВАНИЕ МНОГОПОРОГОВЫХ ДЕКОДЕРОВ
В СЛОЖНЫХ СИСТЕМАХ.................................................................. 159
6.1. Сложные системы кодирования ................................................. 159
6.2. Использование МПД в каскадных схемах................................. 160
6.3. Каскадирование при использовании кодов с проверкой
на четность .......................................................................................... 162
6.4. Сверточные декодеры в каскадном коде с контролем
по четности.......................................................................................... 165
6.5. Символьные каскадные схемы коррекции ошибок при использовании
кодов с контролем по модулю q............................................. 167
6.6. Каскадные схемы коррекции ошибок на базе символьных МПД
и недвоичных кодов Хэмминга ......................................................... 168
238
Стр.238
6.7. Каскадные схемы коррекции ошибок на базе символьных
МПД и недвоичных СОК................................................................... 172
6.8. Использование МПД с многопозиционными системами
модуляции ........................................................................................... 175
6.9. Использование МПД для кодов с неравной защитой
символов.............................................................................................. 176
6.10. Применение МПД в схемах параллельного
каскадирования ................................................................................... 177
6.11. Декодирование кодов с выделенными ветвями ...................... 182
6.12. Кодирование в каналах с неравномерной энергетикой.......... 191
6.13. Применение МПД в каналах со сложной структурой
потоков ошибок .................................................................................. 193
6.14. Адаптивность алгоритмов МПД............................................... 193
6.15. Декодирование двоичных кодов в области R≈C..................... 195
6.16. Выводы ....................................................................................... 199
Заключение.......................................................................................... 200
Приложение 1. Список сокращений, принятых в книге.................. 208
Приложение 2. Рекомендации для дальнейших исследований ...... 209
Приложение 3. Работа многопороговых декодеров вблизи
пропускной способности канала ....................................................... 211
Список литературы............................................................................. 215
Список дополнительной литературы................................................ 224
Стр.239