Содержание к диссертации
Введение
ГЛАВА 1. Защита информации от угроз нарушения целостности. Основные положения теории помехоустойчивого кодирования. LDPC-коды как класс линейных блочных кодов, их преимущества и недостатки 18
1.1. Защита информации от угроз нарушения целостности 18
1.2. Основы теории помехоустойчивого кодирования. Место системы помехоустойчивого кодирования в современных системах передачи информации 24
1.3. Описание LDPC-кодов 29
1.4. Преимущества и недостатки LDPC-кодов. Сравнение LDPC-кодов с использующимися в современных системах связи помехоустойчивыми кодами 36
ГЛАВА 2. Основы кодирования и декодирования LDPC-кодов. Основные алгоритмы декодирования, их преимущества и недостатки. Сравнение алгоритмов декодирования LDPC-кодов 47
2.1. Математические модели каналов связи 47
2.2. Алгоритмы декодирования LDPC-кодов. Обзор. Сравнение 51
2.2.1. Алгоритм с инверсией бита (BF) 54
2.2.2. Алгоритм с итеративным распространением доверия (IBP) 56
2.2.3. Алгоритм быстрого взвешенного мажоритарного декодирования UMPBP . 63
2.2.4. Алгоритм многопорогового декодирования (МИД) 67
2.2.5. Алгоритм быстрого декодирования минимум-суммы 71
ГЛАВА 3. Методика комплексной оценки помехоустойчивых кодов и алгоритмов декодирования 75
3.1. Подсчет числа операций, выполняемых для декодирования одного кодового слова для алгоритма min-sum 75
3.2. Выявление характерных особенностей алгоритмов декодирования на примере алгоритма min-sum 78
3.3. Критерий определения вычислительно сложных этапов алгоритма декодирования 82
3.4. Особенности аппаратной реализации LDPC-декодера 83
3.5. Содержание методики оценки кодов 86
Заключение 89
Приложение 1 90
Приложение 2 97
Список использованной литературы 99
- Основы теории помехоустойчивого кодирования. Место системы помехоустойчивого кодирования в современных системах передачи информации
- Алгоритмы декодирования LDPC-кодов. Обзор. Сравнение
- Алгоритм быстрого взвешенного мажоритарного декодирования UMPBP
- Выявление характерных особенностей алгоритмов декодирования на примере алгоритма min-sum
Введение к работе
Актуальность темы. В настоящее время деятельность любой организации невозможно представить без использования корпоративных сетей (КС), которые играют значительную роль в жизненном цикле производства продукции или оказании услуг. Их роль и влияние на обеспечение качества продукции и услуг постоянно растет.
КС зачастую представляет собой территориально распределенную совокупность локальных вычислительных сетей соединенных в единую глобальную сеть высокоскоростными каналами передачи данных. Проведенный анализ показывает, что, с одной стороны, корпоративная сеть является автоматизированной системой обработки данных, т.е. представляет собой совокупность информационно-вычислительных установок, аппаратных и программных средств, предназначенных для автоматизированного сбора, хранения, обработки, передачи и получения информации. С другой стороны, КС основана, в том числе, на использовании ряда организационных аспектов и должна рассматриваться в контексте эксплуатационной среды. Ключевым аспектом безопасности корпоративных сетей является безопасность ее высокоскоростных каналов передачи данных, так как они являются важнейшей средой распространения сигналов, используемой сетевым оборудованием между элементами КС. Высокоскоростные каналы передачи данных наиболее чувствительны к различного рода ошибкам в канале связи.
Основной функцией КС является обеспечение возможности постоянного получения, обработки, передачи и модификации информации. Эффективность выполнения данной функции определяется контролем над тремя основными свойствами информации: конфиденциальностью, целостностью, доступностью.
В теории компьютерной безопасности выделяют три вида преобразования информации, применяемых для защиты от угроз нарушения целостности информации: криптографическое шифрование, помехоустойчивое кодирование и сжатие (эффективное кодирование). Общим для всех трех видов преобразования является то, что информация неким образом меняет форму представления, сохраняя смысл. Выбор тех или иных видов кодирования определяется целью проводимых преобразований.
Сжатие информации (эффективное кодирование) представляет собой процесс преобразования исходного сообщения из одной кодовой системы в другую, в результате которого уменьшается размер сообщения. Эффективное кодирование применяется на предварительном этапе перед использованием криптографического преобразования. За счет эффективного кодирования уменьшается избыточность сообщений, что позволяет производить более надежное криптографическое шифрование информации.
Криптографические методы защищают информацию от атак, связанных с действиями злоумышленника - несанкционированного доступа, разрушения и/или искажения информации. Однако при передаче информации от абонента к абоненту возможны случайные помехи на линиях связи, ошибки и сбои аппаратуры, частичное разрушение носителей данных и т.д. В связи с этим особое место в линейке методов и средств борьбы с угрозами нарушения целостности информации занимает технология помехоустойчивого кодирования. Помехоустойчивое кодирование выполняется с целью защиты информации от случайных помех при передаче и хранении информации.
Для решения проблем передачи информации в реальных системах связи необходимо комплексное использование различных методов и средств. Криптографическое шифрование, помехоустойчивое кодирование и сжатие дополняют друг друга, и их комплексное применение помогает эффективно использовать каналы связи для надежной защиты передаваемой информации.
Увеличение скоростей передачи данных в канале влечет за собой возрастание количества случайных помех, способных исказить хранимые, обрабатываемые и передаваемые данные. Это обуславливает актуальность разработки и использования новых алгоритмов и методов, позволяющих обнаруживать и корректировать подобные ошибки. В данных условиях особого внимания заслуживают помехоустойчивые коды, позволяющие, в отличие от криптографического шифрования и сжатия, эффективно бороться со случайными ошибками в канале.
Скорость передачи данных по каналу связи напрямую связана с качеством и скоростью декодирования. Возникает противоречие между потребностью в увеличении скорости передачи и ограничениями со стороны аппаратуры помехоустойчивого кодирования. Разрешение противоречия возможно при разработке быстродействующих систем кодирования/декодирования, соответствующих скоростям передачи и характеристикам помех и позволяющих эффективно бороться с угрозами нарушения целостности данных в высокоскоростных каналах передачи данных. По мнению большинства специалистов в области защиты информации решение данной проблемы разбивается на множество важных научных, инженерных, практических и прикладных задач, таких как разработка методик оценки помехоустойчивых кодов, разработка методик определения типа используемого помехоустойчивого кода в канале, разработка отечественных алгоритмов помехоустойчивого кодирования и т.д.
Корректирующие коды получили широкое применение в задачах защиты информации. В настоящее время такие коды представлены в многочисленных технических приложениях, например, в стандартах CCSDS 101.О-В (Consultative Committee for Space Data Systems), ITU-T G.975.1 (International Telecommunication Union) и IEEE 802.16 (The Institute of Electrical and Electronics Engineers).
Одними из таких кодов являются коды с малой плотностью проверок на четность (LDPC-коды), которые по ряду причин были выбраны в качестве примера для рассмотрения разработанной и описанной в работе методики комплексной оценки помехоустойчивых кодов. Коды с малой плотностью проверок на четность (LDPC-код от англ. Low-density parity-check code, LDPC-code, низкоплотностный код) были впервые предложены Р.
Галлагером и позднее исследовались во многих научных трудах В.Д. Колесника, СВ. Федоренко, В.В. Золотарева, Г.В. Овечкина, Е.А. Крука, В.Б. Афанасьева, Е.Т. Мирончикова, Э.М. Габидулина. Работы этих ученых создали базу для проведения исследований в вопросах анализа различных алгоритмов помехоустойчивого кодирования с применением LDPC-кодов, однако ряд вопросов по-прежнему требует исследования.
Несмотря на то, что в течение долгого времени LDPC коды были практически исключены из рассмотрения, в последние годы наблюдается увеличение количества исследований в этой области. Это связано с тем, что коды с малой плотностью проверок на четность обеспечивают высокую степень исправления ошибок несмотря на то, что обладают плохим минимальным расстоянием. Было показано, что с ростом длины кодового слова некоторые LDPC-коды могут превосходить турбо-коды и приближаться к пропускной способности канала с аддитивным белым гауссовским шумом (АБГШ). В настоящее время максимальное приближение к границе Шеннона даёт LDPC-код с примерной длиной блока в 10 миллионов бит. Вместе с тем, многие предложенные конструкции LDPC-кодов являются циклическими или квазициклическими, что позволяет производить не только быстрое декодирование, но и эффективные процедуры кодирования. Кроме того, для LDPC-кодов, не обладающих свойством цикличности, были предложены эффективные процедуры кодирования. LDPC-коды становятся востребованы в системах передачи информации, требующих максимальной скорости передачи при ограниченной полосе частот. Основным конкурентом LDPC-кодов на данный момент являются турбо-коды, которые нашли своё применение в системах спутниковой связи, некоторых стандартах цифрового телевидения и мобильных системах связи третьего поколения.
В отличие от турбо-кодов, LDPC-коды более предпочтительны в каналах с меньшими вероятностями ошибок. С развитием методов передачи информации каналы передачи улучшаются, что даёт хорошую перспективу для развития LDPC-кодов.
Имеет место также и правовой аспект применения LDPC-кодов и турбо-кодов. Компании France Telecom и Telediffusion de France запатентовали широкий класс турбо-кодов, что ограничивает возможность их свободного применения и в то же время стимулирует развитие и использование других методов кодирования, таких как LDPC. LDPC-коды под патентные ограничения не попадают.
Существуют также и объективные причины, по которым LDPC-коды до недавнего времени не занимали лидирующих позиций в линейке помехоустойчивых кодов - высокая ресурсоемкость и вычислительная сложность алгоритмов декодирования с применением LDPC-кодов. Но, в связи с развитием мощности и быстродействия средств вычислительной техники, на данный момент LDPC-коды могут рассматриваться как одни из наиболее эффективных кодов, применение которых актуально на скоростях 10, 40 и 100 Гбит/с для оптоволоконных систем связи. Актуальность этих кодов объясняется следующими преимуществами их использования по сравнению с другими классами кодов: при большой длине кодового слова LDPC коды достигают границы Шеннона; при правильном построении кода отсутствует нижний предел ошибок (error floor); существуют эффективные алгоритмы декодирования LDPC кодов.
Объектом исследования являются методы и средства информационного противодействия угрозам нарушения информационной безопасности.
Предметом исследования являются средства обеспечения защиты от угроз нарушения целостности информации в высокоскоростных каналах передачи данных.
Целью диссертационного исследования является разработка новой методики комплексной оценки помехоустойчивых кодов, применяемой на предварительном этапе построения систем, реализующих защиту информации в высокоскоростных каналах передачи данных (на примере LDPC-кода).
Для достижения цели были поставлены и решены следующие задачи:
Проведен сравнительный анализ различных методов помехоустойчивого кодирования и определение областей применения LDPC-кодов.
Проанализированы алгоритмы кодирования/декодирования LDPC-кодов, применяемые в оптоволоконных системах связи и радиоканалах.
Проведена оценка сложности алгоритма на примере алгоритма min-sum и выделены структурные логические блоки в составе данного алгоритма.
Разработан программный моделирующий комплекс для проверки функционирования параметрически настраиваемого алгоритма декодирования LDPC-кода.
Предложен критерий определения вычислительно сложных этапов алгоритмов декодирования LDPC-кода для аппаратной и программно-аппаратной реализации.
Проведена оценка вычислительной сложности алгоритма декодирования LDPC-кода.
Сформулированы рекомендации по реализации алгоритмов декодирования LDPC-кода на различных классах вычислителей в зависимости от параметров.
Теоретические и методологические основы исследования. Теоретической основой диссертационного исследования явились разработки зарубежных и российских ученых и специалистов по проблемам защиты информации, помехоустойчивого кодирования, теории информации.
Информационную базу исследования составляют сведения, публикуемые в научных изданиях, в периодической печати, материалы международных и российских научных конференций по рассматриваемой проблеме, стандарты в области защиты информации, цифровой радиосвязи.
Для решения поставленных задач использовались аналитические методы исследования математических моделей, имитационное моделирование и экспериментальное исследование описываемых кодов, теории помехоустойчивого кодирования, теории вероятностей и математической статистики, теории графов. Экспериментальные исследования проведены с использованием пакета математического, статистического и имитационного моделирования MATLAB.7.01.
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
Разработана новая, научно обоснованная методика комплексной оценки помехоустойчивых кодов, которая может применяться на начальном этапе разработки систем помехоустойчивого кодирования, позволяющих с заданной достоверностью гарантировать защищенность целостности данных от разрушающих воздействий в высокоскоростных каналах передачи данных, реализуя механизмы защиты информационных символов. Отличительной особенностью данной методики является то, что она оперирует комплексным набором показателей для оценки кода, учитывает различные аспекты использования данного типа кодов и предназначена для оценки возможности и способов построения систем декодирования с применением рассматриваемого типа кодов. Методика приведена на примере LDPC-кода.
Выявлена взаимосвязь алгоритмов декодирования LDPC-кода, которая позволяет раскрыть иерархическую вложенность данных алгоритмов и сделать вывод о том, какой алгоритм является наиболее релевантным для определенной системы передачи данных с заданными параметрами.
Разработан способ оценки сложности алгоритмов декодирования кода, реализуемый путем разбиения алгоритмов декодирования выбранного кода на логические блоки, составления схем данных алгоритмов и подсчета количества операций. Данный способ позволяет оценить ресурсоемкость алгоритма и выработать рекомендации по аппаратному и программно-аппаратному составу комплексов помехоустойчивого кодирования, реализующих данный код.
Предложен критерий определения вычислительно сложных этапов алгоритма для аппаратной и программно-аппаратной реализации, позволяющий выработать рекомендации по его реализации на различных классах вычислителей за счет выявления характерных особенностей данного алгоритма.
Теоретическая и практическая значимость исследования. Теоретическая значимость исследования заключается в формировании нового подхода к совершенствованию способов обеспечения защиты от угроз нарушения целостности информации в высокоскоростных каналах передачи данных и реализации устройств помехоустойчивого кодирования для каналов связи на основе алгоритмов, использующих коды с малой плотностью проверок на чётность. Предлагаемый подход не призван заменить существующие методики реализации устройств, а применяется на предварительном этапе анализа канала связи и оценки помехоустойчивого кода.
Практическая значимость диссертационного исследования состоит в том, что разработанные рекомендации и методики могут быть использованы при разработке систем, реализующих защиту информации от угроз нарушения целостности в корпоративных сетях. Кроме того, результаты также могут быть использованы в образовательном процессе высших учебных заведений, при написании учебников и учебных пособий (по специальностям - 090102.65 «Компьютерная безопасность», 090900.62 «Информационная безопасность», 230400.68 «Информационные системы и технологии» и т.п.).
Работа соответствует паспорту специальности 05.13.19 - Методы и системы защиты информации, информационная безопасность (пункт 5 -методы и средства (комплексы средств) информационного противодействия угрозам нарушения информационной безопасности в открытых компьютерных сетях, включая Интернет).
На защиту выносятся следующие положения диссертации:
Взаимосвязь алгоритмов декодирования помехоустойчивого LDPC-кода
Критерий определения вычислительно сложных этапов алгоритмов кодирования/декодирования для итеративно декодируемых кодов, применяемых в высокоскоростных каналах передачи данных
Методика комплексной оценки помехоустойчивых кодов, применяемых в высокоскоростных каналах передачи данных
Достоверность и обоснованность полученных результатов обеспечиваются применением корректных исходных данных, апробированного аппарата исследований, проверкой непротиворечивости и адекватности промежуточных и окончательных положений и выводов, подтверждается полученными экспериментальными данными, совпадающими с существующими данными об эффективности известных кодов.
Основные положения и выводы диссертационного исследования были внедрены в ООР^«ЦИБИТ»^Такжсгдтдельные положения диссертации используются при проведении учебных занятий по следующим программам повышения квалификации: «Организация защиты информации», «Безопасность компьютерных систем», «Программно-аппаратные средства защиты информации в распределенных вычислительных системах» в войсковой части №11928.
Апробация работы. Основные положения диссертации доложены и одобрены на Всероссийской межвузовской научно-технической конференции «Микроэлектроника и информатика - 2010» (Москва, 2010); на Международной научно-технической конференции «Системные проблемы надежности, качества, информационно-телекоммуникационных и электронных технологий в управлении инновационными проектами. «Инноватика-2010» (Москва-Сочи, 2010); на Российской научно-технической конференции «Информатика и проблемы телекоммуникаций» (Москва-Новосибирск, 2011); на ряде научно-практических семинаров в СКГМИ (Москва-Владикавказ, 2008-2011 гг.).
Публикации. Основные результаты диссертации опубликованы в 5 печатных работах, общим авторским объемом 1,9 п.л., в том числе 3 из них в изданиях, рекомендованных ВАК Минобрнауки России.
Структура и объем работы. Диссертация состоит из введения, трех глав и заключения, списка использованных источников. Работа представлена на 110 страницах машинописного текста, включает 2 таблицы и 25 рисунков, библиография из 112 наименований.
Во введении обоснована актуальность рассматриваемой проблемы, сформулированы цели и задачи работы, определены практическая ценность и область применения результатов.
В первой главе диссертации изложены проблемы передачи информации, их комплексное решение, а также основные способы защиты от угроз целостности информации в высокоскоростных каналах передачи данных. Обосновано, почему именно методы помехоустойчивого кодирования наиболее чувствительны к возрастанию скорости передачи в канале. Рассмотрены основные положения теории помехоустойчивого кодирования, LDPC-коды как класс линейных блочных кодов, их преимущества и недостатки. Проведено сравнение LDPC-кодов с использующимися на сегодняшний момент помехоустойчивыми кодами.
Во второй главе рассмотрены основные модели каналов связи, описаны основные алгоритмы декодирования LDPC-кодов. Для каждого из алгоритмов составлена схема, последовательно отражающая суть каждого этапа итерации. Основой для разбиения на логические блоки послужил принцип группировки схожих математических операций и наглядного представления сложных преобразований над кодовым словом. Приведена схема, иллюстрирующая взаимосвязи алгоритмов. С её помощью показано развитие и оптимизация основных методов декодирования LDPC-кодов, начиная от алгоритмов Галлагера для жесткого и мягкого решения. Рассмотрены основные типы архитектур декодера.
В третьей главе приведены процедуры оценки сложности реализации алгоритма декодирования и поиска вычислительно сложных этапов алгоритма декодирования. Приведена методика подсчета числа математических операций для декодирования одного кодового слова на примере алгоритма min-sum. Получены формулы для вычисления количества необходимых операций различного типа и общего количества операций для декодирования одного кодового слова в зависимости от параметров используемого LDPC-кода и числа итераций декодирования по алгоритму min-sum. Рассмотрены характерные особенности алгоритма min-sum, важные для практической реализации декодера и выбора его будущей архитектуры. Сформулирован критерий определения вычислительно сложных этапов алгоритма декодирования. Рассмотрены возможные варианты аппаратной платформы LDPC-декодера, такие как ASIC (SOC), ПЛИС, CPU, GPU. Сформулировано содержание методики комплексной оценки помехоустойчивых кодов.
В заключении сформулированы основные результаты работы, полученные автором.
Основы теории помехоустойчивого кодирования. Место системы помехоустойчивого кодирования в современных системах передачи информации
Необратимое сжатие имеет обычно гораздо более высокую степень сжатия, чем кодирование без потерь, но допускает некоторые отклонения декодированных данных от исходных. На практике существует широкий круг практических задач, в которых соблюдение требования точного восстановления исходной информации после декомпрессии не является обязательным. Это, в частности, относится к сжатию мультимедийной информации: звука, фото или видеоизображений. Так, например, широко применяются форматы мультимедийной информации JPEG и MPEG, в которых используется необратимое сжатие. Необратимое сжатие обычно не используется совместно с криптографическим шифрованием, так как основным требованием к криптосистеме является идентичность расшифрованных данных исходным. Однако при использовании мультимедиа технологий данные, представленные в цифровом виде, часто подвергаются необратимой компрессии перед подачей в криптографическую систему для шифрования. После передачи информации потребителю и расшифрования мультимедиа файлы используются в сжатом виде (то есть не восстанавливаются).
Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов на один кодирующий байт-заполнитель и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других, - не кодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток вначале кодированных цепочек. Такими метками могут быть характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже - с малым числом повторяющихся байтов в сериях.
При равномерном кодировании информации на сообщение отводится одно и то же число бит, независимо от вероятности его появления. Вместе с тем логично предположить, что общая длина передаваемых сообщений уменьшится, если часто встречающиеся сообщения кодировать короткими кодовыми словами, а редко встречающиеся - более длинными. Возникающие при этом проблемы связаны с необходимостью использования кодов с переменной длиной кодового слова. Существует множество подходов к построению подобных кодов.
Одними из широко используемых на практике являются словарные методы, к основным представителям которых относятся алгоритмы семейства Зива и Лемпела. Их основная идея заключается в том, что фрагменты входного потока (фразы) заменяются указателем на то место, где они в тексте уже ранее появлялись. В литературе подобные алгоритмы обозначаются как алгоритмы LZ сжатия.
Подобный метод быстро приспосабливается к структуре текста и может кодировать короткие функциональные слова, так как они очень часто в нем появляются. Новые слова и фразы могут также формироваться из частей ранее встреченных слов. Декодирование сжатого текста осуществляется напрямую, - происходит простая замена указателя готовой фразой из словаря, на которую тот указывает. На практике LZ-метод добивается хорошего сжатия, его важным свойством является очень быстрая работа декодера.
Другим подходом к сжатию информации является код Хаффмана, кодер и декодер которого имеют достаточно простую аппаратную реализацию. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды, тогда как реже встречающимся символам - более длинные. За счет этого достигается сокращение средней длины кодового слова и большая эффективность сжатия. Коды Хаффмана имеют уникальный префикс (начало кодового слова), что и позволяет однозначно их декодировать, несмотря на их переменную длину.
Процедура синтеза классического кода Хаффмана предполагает наличие априорной информации о статистических характеристиках источника сообщений. При этом разработчику должны быть известны вероятности возникновения тех или иных символов, из которых образуются сообщения. [80]
Увеличение скоростей передачи данных в канале влечет за собой возрастание количества случайных помех, способных исказить хранимые, обрабатываемые и передаваемые данные. Это обуславливает актуальность разработки и использования новых алгоритмов и методов, позволяющих обнаруживать и корректировать подобные ошибки. В данных условиях особого внимания заслуживают помехоустойчивые коды, позволяющие, в отличие от криптографического шифрования и сжатия, эффективно бороться со случайными ошибками в канале.
Возможности систем связи, используемых в наши дни, совершенно несравнимы со своими аналогами даже 10-ти летней давности. Это результат напряженного труда многих ученых и инженеров во всем мире, как в области развития элементной базы, так и улучшения старых и выработке новых алгоритмов передачи и защиты информации от искажений и помех. И немалая роль тут принадлежит области помехоустойчивого кодирования, в которой развитие вычислительной техники стимулирует синтез новых, сложных и эффективных алгоритмов кодирования и декодирования, что позволяет существенно повысить качество передаваемой информации, обнаруживая и исправляя вносимые каналом связи ошибки. Это актуально практически во всех системах электросвязи, начиная от радиосвязи и заканчивая волоконно-оптическими магистралями. Общая схема организации систем передачи цифровой информации по каналам с аддитивным белым гауссовским шумом (АБГШ) приведена на рис. 1.1.
Алгоритмы декодирования LDPC-кодов. Обзор. Сравнение
Существуют два основных метода декодирования линейных блочных кодов - это декодирование с «жестким» и «мягким» решениями. Свои названия они получили от способа вынесения демодулятором решения относительно каждого принятого символа. Первый способ - когда демодулятор по уровню входного сигнала выносит жесткое решение, ноль пришел или единица, и с выхода демодулятора на вход декодера идёт уже цифровой поток. Второй способ - с выхода демодулятора поступает набор величин, характеризующих вероятность того, что передавалась единица и вероятность, что передавался ноль. Последовательность действий, реализующая на практике один из методов декодирования, называется алгоритм декодирования.
Все алгоритмы декодирования LDPC-кодов являются итеративными. Почти все они относятся к классу алгоритмов обмена сообщениями {message passing algorithm, MP) и строятся по критерию максимума апостериорной вероятности {maximum a-posteriori, MAP). Основой для построения декодера является граф Таннера. Итеративные схемы декодирования кодов с низкой плотностью проверок на четность не являются декодерами по максимуму правдоподобия, но позволяют получить разумный баланс по сложности и вероятности ошибки декодирования по сравнению с декодированием по максимуму правдоподобия. Итеративное декодирование подразумевает, что нахождение кодового слова будет производиться не за один проход, а за несколько, с последовательным уточнением результата на каждом шаге
Основные алгоритмы, описанные в литературе: 1. Алгоритм с инверсией бита {bit flipping algorithm, BF), он же -«жесткое» решение по Галлагеру; 2. Алгоритм с итеративным распространением доверия {iterative belief propagation algorithm, IBP), мягкое решение по Галлагеру. Этот алгоритм является частным случаем, известного как сумма-произведений {sum-product algorithm, SP); 3. Алгоритм быстрого декодирования uniformly most powerful belief propagation (UMP BP); 4. Алгоритм многопорогового декодирования - МПД {multihreshold algorithm, MT), является дальнейшим усовершенствованием алгоритма UMP ВР; 5. Алгоритм быстрого декодирования минимум-суммы {min-sum algorithm, MS), является упрощением алгоритма sum-product. Для каждого из алгоритмов составлена схема, последовательно отражающая суть каждого этапа итерации. Суть разбиения на логические блоки одна - сгруппировать схожие математические операции и наглядно представить сложные преобразования над кодовым словом. На рис. (2.5) приведена схема, иллюстрирующая взаимосвязи алгоритмов. С её помощью показано развитие и оптимизация основных методов декодирования LDPC-кодов, начиная от алгоритмов Галлагера для жесткого и мягкого решения. Далее следует кратко прокомментировать эту схему. Самым простым для понимания сути декодирования LDPC -кодов является «жесткое» решение по Галлагеру, или алгоритм с инверсией бита. На основании алгоритма с инверсией бита строится алгоритм декодирования с итеративным распространением доверия, использующего не «жесткий» (кодовое слово), а «мягкий» выход демодулятора - метрики, основанные условные вероятностях передачи того или иного бита кодового слова. Применение такого подхода существенно повышает качество декодирования за счет использования дополнительной информации из канала связи. Недостатком же является высокая вычислительная сложность декодирования, что накладывает ограничения на производительность и пропускную способность всей системы передачи в целом, а так же существенно повышает её стоимость. Выходом из этой ситуации является упрощение алгоритма с вычислительной точки зрения с допустимой потерей качества декодирования. Продуктом такого упрощения являются алгоритмы min-sum и алгоритм быстрого декодирования по надёжностям. Дальнейшим развитием алгоритма быстрого декодирования по надёжностям является многопороговое декодирование. На схеме схожие алгоритмы декодирования выделены одним цветом. «Жесткое» декодирование - это схема декодирования для двоичного симметричного канала при небольшом количестве ошибок в канале. Алгоритм декодирования инвертированием битов - самая простая по сложности схема декодирования кодов с низкой плотностью проверок на четность. В качестве основы используется модель ДСК без памяти. На каждом шаге происходит пересчет проверок на четность в каждом проверочном узле графа Таннера и инвертирование битов, для которых не выполнилась половина проверок на четность, превышающее некоторую заранее заданную величину. Как правило, это половина от всех проверок, связанных с рассматриваемым битом. Таким образом, одна итерация «жесткого» декодирования инвертированием битов производится следующим образом (рис. 2.6): 1. Для принятого вектора вычисляются все проверки; 2. Проверяется, не превышено ли максимальное число итераций; 3. Если некоторый бит принятого вектора участвовал более чем в половине не выполнившихся проверок, бит инвертируется; 4. После такого анализа всех символов принятого вектора вектор проверяется на принадлежность коду. Если вектор является кодовым словом, то есть выполнились все проверки на четность, декодирование заканчивается. В противном случае выполняется следующая итерация алгоритма.
Алгоритм быстрого взвешенного мажоритарного декодирования UMPBP
В таком случае, оптимальной, с точки зрения быстродействия, сложности и стоимости будет схема с частично-параллельной архитектурой. Достоинство такой схемы ещё и в том, что схема с полностью параллельной архитектурой создаётся под код с конкретной длиной кодового слова, равной числу вычислителей VNU.
Качество декодирования повышается за счет использования дополнительной информации на выходе канала. Однако качество работы такого алгоритма зависит от инициализации: чем точнее она произведена, тем точнее будет конечный результат.
Несмотря на то, что декодирование пересчетом вероятностей является эффективным методом для каналов с непрерывным выходом, тот факт, что сложность его значительно выше, чем сложность «жесткого» декодирования, оставляет место для поиска более быстрых алгоритмов декодирования, обладающих приемлемым качеством. Среди известных алгоритмов быстрого декодирования кодов с низкой плотностью проверок на четность для каналов с непрерывным выходом наиболее известен алгоритм «min-sum», являющийся упрощением декодера «belief propagation», а также алгоритм UMP ВР (Uniformly Most Powerful Belief Propagation [8]) который будет рассмотрен далее. Пусть из канала был принят вещественный («мягкий») вектору = {у0,..., уп_1}. Надежностью /-го символа вектора у будем считать величину г(, характеризующую удаление принятого значения у, от некоего порогового значения thr, при котором все значения переданных символов равновероятны Для случая двоичной модуляции, при которой все биты кодового слова отображаются во множество {-1, +1} и передаются по симметричному каналу с двоичным входом и мягким выходом, пороговое значение thr = 0, поэтому надежность принятого символа у, будет равна абсолютной величине принятого значения, т.е. Быстрое декодирование по надежностям является чем-то средним между «жестким» декодированием и декодированием по вероятностям. При декодировании используется вектор «жестких» решений х = {х0,...,хп_г} (вектор, состоящий из 0 и 1 и представляющий собой набор дискретных решений) и вектор надежностей г = {Уо --- Уп-і} (вектор, состоящий из вещественных величин). По аналогии с вероятностным декодированием, каждому ненулевому символу проверочной матрицы приписываются два числа: хч и rtJ, представляющие собой «жесткое» решение относительно символа у, полученное при помощи всех проверок, кроме і-й, и надежность символов і-й проверки без учетау-го символа соответственно. Декодирование также является итеративным. Одна итерация представляет собой следующую последовательность действий. 1. Для всех проверок и всех символов проверок вычисляется надежность проверок относительно символа J, представляющая собой минимальное значение надежностей всех символов, входящих в проверку, кроме самого символа./: r i,i = minkeBjMj rkJ (2.11) 2. Для всех символов принятого вектора и всех проверок производится пересчет надежностей символов проверок: если проверка, в которую входил некоторый символ, не выполняется, то надежность гч уменьшается на величину надежности проверки в противном случае надежность rtJ увеличивается на r ld, учитываются все проверки, кроме г -й. Если после, применения всех проверок для какого-то символа j, величина r,j стала меньше нуля, то обновленная надежность Гц берется по модулю, а жесткое решение xtJ инвертируется. 3. Аналогично пересчитываются надежности принятого вектора: если /-я проверка, в которую входиту -й символ, нарушается, то из надежности rt вычитается надежность г -й проверки, иначе надежность символа увеличивается на надежность проверки. Если после приме нения всех проверок для какого-то символа j величина г,- стала меньше нуля, то обновленная надежность rtJ берется по модулю, а «жесткое» решение xtJ инвертируется. 4. Если «жесткое» решение х является кодовым словом, декодирование заканчивается, иначе декодер начинает следующую итерацию. Сложность декодера UMP значительно ниже, чем сложность декодера, пересчитывающего вероятности, за счет того, что пересчет надежностей выполняется по упрощенной схеме (схеме «взвешенного» мажоритарного голосования, где в качестве «весов» используется надежность проверок), а также за счет возможности использования исключительно целочисленных операций сложения и сложения по модулю два. Также к достоинствам быстрого декодера по надежностям можно отнести то, что декодеру не требуется знать характеристики шума в канале (дисперсию и т. д.), и, следовательно, такой декодер может работать в любом симметричном канале с двоичным входом [8].
Недостатком такого декодера является оценка вероятности ошибки декодирования, которая для канала с аддитивным гауссовским шумом оказывается на 0,5 дБ хуже, чем вероятность ошибки декодирования вероятностного декодера.
Модификацией быстрого декодера по надежностям, позволяющей добиться приближения вероятности ошибки декодирования к вероятности, получаемой при вероятностном декодировании, является многопороговое декодирование.
Быстрый декодер по надежностям (UMP) принимает решения относительно символов принятого вектора на основе пересчета надежностей и инвертирования символов «жесткого» решения, причем инвертирование символов производится всегда, когда соответствующая надежность после пересчета становится меньше нуля. Нуль в данном случае является порогом инвертирования символа, причем на всех итерациях этот порог остается неизменным, несмотря на то, что на первых итерациях декодирования надежности символов битов еще плохо определены, и инвертирование таких символов может привести как к исправлению ошибок, так и, наоборот, к внесению новых и последующему их размножению [31, 36, 39].
Выявление характерных особенностей алгоритмов декодирования на примере алгоритма min-sum
ASIC - application specified integrated circuit, интегральная схема, специализированная для решения конкретной задачи. Они имеют узкий круг применения, так как выполняют строго ограниченные функции, характерные только конкретному устройству, где они применяются. Помехоустойчивые кодеки (кодер + декодер) являются как раз такими устройствами. Есть еще одно название устройств этого класса - SOC - system-on-a-chip {система на кристалле).
Достоинство: качественная микросхема с предопределённой логикой работы будет иметь самые высокие показатели производительности. Недостатки: ограниченная функциональность, определяемая специализацией конкретного набора микросхем; продолжительный цикл разработки и отладки аппаратной и программной частей создаваемого оборудования. ПЛИС - программируемая логическая интегральная схема {programmable logic device, PLD) — электронный компонент, используемый для создания цифровых интегральных схем. В отличие от обычных цифровых микросхем, логика работы ПЛИС не определяется при изготовлении, а задаётся посредством программирования. Гибкость логической структуры ПЛИС делает её одним из самых удобных инструментов для создания самых разнообразных аппаратных и аппаратно-программных средств, используемых в самых различных сферах, где применяются цифровое оборудование и технологии, в том числе и при передаче данных. При создании кодека на ПЛИС на выходе, при грамотном проектировании, мы получаем устройство, сравнимое по качеству и скорости декодирования с заказной интегральной схемой. При этом, мы имеем возможность перепрограммировать его в любое время при появлении такой необходимости, например при смене стандартов передачи, или перепрофилированию приёмо-передающей аппаратуры.
Однако, несмотря на все очевидные плюсы применения ПЛИС для реализации декодеров, существует один важный недостаток, на который в условиях современных рыночных отношений невозможно закрыть глаза -это относительно высокая стоимость самих ПЛИС и сопутствующего оборудования. CPU и GPU - central processing unit (центральный процессор, ЦП) и graphic processing unit (графический процессор) также могут являться аппаратной платформой для создания декодера, который будет представлять из себя аппаратный модуль преобразования интерфейсов и/или первичной обработки цифрового потока на плате со стандартным PCI-разъёмом и программу, реализующую сам процесс декодирования. Смысл включения их в рассмотрение состоит в том, что, хоть декодеры на ASIC и ПЛИС являются самыми эффективными, зачастую их реализация оказывается очень затратной. Так же, в современных системах связи, наблюдается устойчивая тенденция к тотальному переходу на цифровую обработку сигналов и, как следствие, к отказу от большинства классических аппаратных частей приемного тракта.
На основании специфических свойств тех или иных аппаратных платформ, а так же исходя из анализа характерных особенностей алгоритма декодирования, можно сформулировать рекомендации для реализации декодера с учетом достоинств и недостатков различных аппаратных платформ. Например, такая характерная особенность алгоритма, как внутренний параллелизм, наводит на мысль об использовании векторных вычислителей или иных платформ, позволяющих распараллелить обработку. На сегодняшний момент существует множество критериев сравнения и оценки помехоустойчивых кодов, например по кодовому расстоянию (исправляющей способности), информационной скорости, задачам и областям применения; что касается алгоритмов декодирования, то это, в первую очередь, качество и скорость. В таких условиях ощущается необходимость в едином, централизованном подходе к общей, комплексной оценке кодов. В качестве итога приводится общее содержание методики оценки, справедливой для любого класса помехоустойчивых кодов. Все проделанные выше операции для оценки LDPC-кодов и декодеров, работающих по алгоритму min-sum, и соответствующие выводы по ним приведены в рамках данной предлагаемой методики комплексной оценки помехоустойчивых кодов, которая включает: 1. Сравнительный анализ помехоустойчивых кодов и определение областей применения рассматриваемых типов кодов; 2. Анализ алгоритмов кодирования/декодирования, характерных для данных типов кодов и выбор наиболее релевантного алгоритма для рассматриваемой системы передачи данных; 3. Оценка сложности выбранного алгоритма, разбиение его на логические блоки, составление схемы данного алгоритма; 4. Определение вычислительно сложных этапов алгоритма для аппаратной или аппаратно-программной реализации; 5. Выработка рекомендаций по реализации данного алгоритма на различных классах вычислителей 1) В рамках комплексной оценки помехоустойчивых кодов, на примере алгоритма декодирования LDPC-кодов минимум-суммы: получены аналитические выражения, позволяющие быстро оценить ресурсоёмкость алгоритма, зная лишь параметры используемого кода; проведено исследование алгоритма декодирования минимум-суммы на предмет выявления характерных особенностей данного алгоритма, таких как, например, внутренний параллелизм в вычислениях; сформулирован критерий определения ресурсоёмких этапов алгоритма декодирования, приведён пример его использования для (9, 2, 3) - LDPC-кода; рассмотрены возможные варианты аппаратной реализации декодера с учетом выявленных характерных особенностей и ресурсоёмких этапов, сформулированы рекомендации по практический реализации декодеров с учетом этих особенностей. 2) Сформулировано содержание методики комплексной оценки помехоустойчивых кодов. В данной работе рассматривались способы обеспечения защиты информации от угроз нарушения целостности в высокоскоростных каналах передачи данных. Основное внимание уделялось вопросам помехоустойчивого кодирования, которое выполняется с целью защиты информации от случайных помех и искажений, вносимых в неё при передаче по каналу связи. Была разработана методика комплексной оценки помехоустойчивых кодов, применяемая на предварительном этапе построения систем, реализующих защиту информации от угроз нарушения целостности в высокоскоростных каналах передачи данных. В работе данная методика была приведена на примере LDPC-кодов. В ходе исследований получены следующие новые теоретические и практические результаты: 1. Выявлена взаимосвязь алгоритмов декодирования LDPC-кода; 2. Предложен критерий определения вычислительно сложных этапов алгоритмов кодирования/декодирования для итеративно декодируемых кодов, применяемых в высокоскоростных каналах передачи данных;
