автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.19, диссертация на тему:Защита информации от угроз нарушения целостности в высокоскоростных каналах передачи данных

п

005004963

V/

СОЛТАНОВ Андрей Георгиевич

ЗАЩИТА ИНФОРМАЦИИ ОТ УГРОЗ НАРУШЕНИЯ ЦЕЛОСТНОСТИ В ВЫСОКОСКОРОСТНЫХ КАНАЛАХ ПЕРЕДАЧИ ДАННЫХ

Специальность 05.13.19 - Методы и системы защиты информации, информационная безопасность

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

- в ДЕК 2011

Москва 2011 г.

005004963

Диссертационная работа выполнена в отделе разработки и внедрения средств защиты информации в корпоративных информационных системах и технологиях ФГУП «Всероссийский научно-исследовательский институт проблем вычислительной техники и информатизации»

Научный руководитель: доктор технических наук

Конявский Валерий Аркадьевич

Официальные оппоненты: доктор технических наук,

старший научный сотрудник Скиба Владимир Юрьевич

кандидат технических наук Сизов Алексей Юрьевич

Ведущее предприятие: ФГУП «Концерн «Системпром»

Защита состоится «21» декабря 2011 года в 12 час. 00 мин. на заседании диссертационного совета Д 219.007.02 во ФГУП «Всероссийский научно-исследовательский институт проблем вычислительной техники и информатизации» (ВНИИПВТИ) по адресу: 115114, Москва, 2-й Кожевнический пер., дом 8, ауд.213.

С диссертацией можно ознакомиться в библиотеке ВНИИПВТИ. Адрес: 115114, Москва, 2-й Кожевнический пер., дом 8, строение 1.

Автореферат разослан «19» ноября 2011 г.

Ученый секретарь диссертационного совета, кандидат экономических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В настоящее время деятельность любой организации невозможно представить без использования корпоративных сетей (КС), которые играют значительную роль в жизненном цикле производства продукции или оказании услуг. Их роль и влияние на обеспечение качества продукции и услуг постоянно растет.

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

Основной функцией КС является обеспечение возможности постоянного получения, обработки, передачи и модификации информации. Эффективность выполнения данной функции определяется контролем над тремя основными свойствами информации: конфиденциальностью, целостностью, доступностью.

В теории компьютерной безопасности выделяют три вида преобразования информации, применяемых для защиты от угроз нарушения целостности информации: криптографическое шифрование, помехоустойчивое кодирование и сжатие (эффективное кодирование). Общим для всех трех видов преобразования является то, что информация неким образом меняет форму представления, сохраняя смысл. Выбор тех или иных видов кодирования определяется целью проводимых преобразований.

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

Криптографические методы защищают информацию от атак, связанных с действиями злоумышленника - несанкционированного доступа, разрушения и/или искажения информации. Однако при передаче

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

Для решения проблем передачи информации в реальных системах связи необходимо комплексное использование различных методов и средств. Криптографическое шифрование, помехоустойчивое кодирование и сжатие дополняют друг друга, и их комплексное применение помогает эффективно использовать каналы связи для надежной защиты передаваемой информации.

Увеличение скоростей передачи данных в канале влечет за собой возрастание количества случайных помех, способных исказить хранимые, обрабатываемые и передаваемые данные. Это обуславливает актуальность разработки и использования новых алгоритмов и методов, позволяющих обнаруживать и корректировать подобные ошибки. В данных условиях особого внимания заслуживают помехоустойчивые коды, позволяющие, в отличие от криптографического шифрования и сжатия, эффективно бороться со случайными ошибками в канале.

Скорость передачи данных по каналу связи напрямую связана с качеством и скоростью декодирования. Возникает противоречие между потребностью в увеличении скорости передачи и ограничениями со стороны аппаратуры помехоустойчивого кодирования. Разрешение противоречия возможно при разработке быстродействующих систем

кодирования/декодирования, соответствующих скоростям передачи и характеристикам помех и позволяющих эффективно бороться с угрозами нарушения целостности данных в высокоскоростных каналах передачи данных. По мнению большинства специалистов в области защиты информации решение данной проблемы разбивается на множество важных научных, инженерных, практических и прикладных задач, таких как разработка методик оценки помехоустойчивых кодов, разработка методик определения типа используемого помехоустойчивого кода в канале, разработка отечественных алгоритмов помехоустойчивого кодирования и т.д.

Корректирующие коды получили широкое применение в задачах защиты информации. В настоящее время такие коды представлены в многочисленных технических приложениях, например, в стандартах 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-кода).

Для достижения цели были поставлены и решены следующие задачи:

1. Проведен сравнительный анализ различных методов помехоустойчивого кодирования и определение областей применения LDPC-кодов.

2. Проанализированы алгоритмы кодирования/декодирования LDPC-кодов, применяемые в оптоволоконных системах связи и радиоканалах.

3. Проведена оценка сложности алгоритма на примере алгоритма min-sum и выделены структурные логические блоки в составе данного алгоритма.

4. Разработан программный моделирующий комплекс для проверки функционирования параметрически настраиваемого алгоритма декодирования LDPC-кода.

5. Предложен критерий определения вычислительно сложных этапов алгоритмов декодирования LDPC-кода для аппаратной и программно-аппаратной реализации.

6. Проведена оценка вычислительной сложности алгоритма декодирования LDPC-кода.

7. Сформулированы рекомендации по реализации алгоритмов декодирования LDPC-кода на различных классах вычислителей в зависимости от параметров.

Теоретические и методологические основы исследования.

Теоретической основой диссертационного исследования явились разработки зарубежных и российских ученых и специалистов по проблемам защиты информации, помехоустойчивого кодирования, теории информации.

Информационную базу исследования составляют сведения, публикуемые в научных изданиях, в периодической печати, материалы международных и российских научных конференций по рассматриваемой проблеме, стандарты в области защиты информации, цифровой радиосвязи.

Для решения поставленных задач использовались аналитические методы исследования математических моделей, имитационное моделирование и экспериментальное исследование описываемых кодов, теории помехоустойчивого кодирования, теории вероятностей и математической статистики, теории графов. Экспериментальные исследования проведены с использованием пакета математического, статистического и имитационного моделирования МАТЬАВ.7.01.

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

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

2. Выявлена взаимосвязь алгоритмов декодирования ЬОРС-кода, которая позволяет раскрыть иерархическую вложенность данных алгоритмов и сделать вывод о том, какой алгоритм является наиболее релевантным для определенной системы передачи данных с заданными параметрами.

3. Разработан способ оценки сложности алгоритмов декодирования кода, реализуемый путем разбиения алгоритмов декодирования выбранного кода на логические блоки, составления схем данных алгоритмов и подсчета количества операций. Данный способ позволяет оценить ресурсоемкость алгоритма и выработать рекомендации по аппаратному и программно-аппаратному составу комплексов помехоустойчивого кодирования, реализующих данный код.

4. Предложен критерий определения вычислительно сложных этапов алгоритма для аппаратной и программно-аппаратной реализации, позволяющий выработать рекомендации по его реализации на различных классах вычислителей за счет выявления характерных особенностей данного алгоритма.

Теоретическая и практическая значимость исследования. Теоретическая значимость исследования заключается в формировании нового подхода к совершенствованию способов обеспечения защиты от угроз нарушения целостности информации в высокоскоростных каналах передачи данных и реализации устройств помехоустойчивого кодирования для каналов связи на основе алгоритмов, использующих коды с малой плотностью проверок на чётность. Предлагаемый подход не призван заменить существующие методики реализации устройств, а применяется на предварительном этапе анализа канала связи и оценки помехоустойчивого кода.

Практическая значимость диссертационного исследования состоит в том, что разработанные рекомендации и методики могут быть использованы при разработке систем, реализующих защиту информации от угроз нарушения целостности в корпоративных сетях. Кроме того, результаты также могут быть использованы в образовательном процессе высших учебных заведений, при написании учебников и учебных пособий (по специальностям - 090102.65 «Компьютерная безопасность», 090900.62 «Информационная безопасность», 230400.68 «Информационные системы и технологии» и т.п.).

Работа соответствует паспорту специальности 05.13.19 - Методы и системы защиты информации, информационная безопасность (пункт 5 -методы и средства (комплексы средств) информационного противодействия угрозам нарушения информационной безопасности в открытых компьютерных сетях, включая Интернет).

На защиту выносятся следующие положения диссертации:

1. Взаимосвязь алгоритмов декодирования помехоустойчивого ЬОРС-кода

2. Критерий определения вычислительно сложных этапов алгоритмов кодирования/декодирования для итеративно декодируемых кодов, применяемых в высокоскоростных каналах передачи данных

3. Методика комплексной оценки помехоустойчивых кодов, применяемых в высокоскоростных каналах передачи данных

Достоверность и обоснованность полученных результатов обеспечиваются применением корректных исходных данных, апробированного аппарата исследований, проверкой непротиворечивости и адекватности промежуточных и окончательных положений и выводов, подтверждается полученными экспериментальными данными, совпадающими с существующими данными об эффективности известных кодов.

Основные положения и выводы диссертационного исследования были внедрены в ООО «ЦИБИТ». Также отдельные положения диссертации используются при проведении учебных занятий по следующим программам повышения квалификации: «Организация защиты информации», «Безопасность компьютерных систем», «Программно-аппаратные средства защиты информации в распределенных вычислительных системах» в войсковой части №11928.

Апробация работы. Основные положения диссертации доложены и одобрены на Всероссийской межвузовской научно-технической конференции «Микроэлектроника и информатика - 2010» (Москва, 2010); на Международной научно-технической конференции «Системные проблемы надежности, качества, информационно-телекоммуникационных и электронных технологий в управлении инновационными проектами. «Инноватика-2010» (Москва-Сочи, 2010); на Российской научно-технической конференции «Информатика и проблемы телекоммуникаций» (Москва-Новосибирск, 2011); на ряде научно-практических семинаров в СКГМИ (Москва-Владикавказ, 2008-2011 гг.).

Публикации. Основные результаты диссертации опубликованы в 5 печатных работах, общим авторским объемом 1,9 п.л., в том числе 3 из них в изданиях, рекомендованных ВАК Минобрнауки России.

Структура и объем работы. Диссертация состоит из введения, трех глав и заключения, списка использованных источников. Работа представлена на 110 страницах машинописного текста, включает 2 таблицы и 35 рисунков, библиография из 112 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность рассматриваемой проблемы, сформулированы цели и задачи работы, определены практическая ценность и область применения результатов.

В первой главе диссертации изложены проблемы передачи информации, их комплексное решение, а также основные способы защиты от угроз нарушения целостности информации в высокоскоростных каналах передачи данных.

Отмечено, что вопросы сжатия и криптографического преобразования информации тесно связаны с вопросами помехоустойчивого кодирования сообщений. Это обусловлено, с одной стороны (теоретической), тем, что и при криптографическом шифровании, и при помехоустойчивом кодировании используются одни и те же законы теории компьютерной безопасности. С другой стороны (практической) процессы накопления, хранения и передачи информации протекают в условиях воздействия помех, способных исказить хранимые и обрабатываемые данные. Это обуславливает актуальность разработки и использования методов, позволяющих обнаруживать и

корректировать подобные ошибки. С математической точки зрения задача сводится к синтезу так называемых помехоустойчивых кодов.

О важности развития алгоритмов кодирования и декодирования помехоустойчивых кодов говорят ежегодно появляющиеся работы, посвященные данной тематике. Наиболее актуальными и значимыми работами за последнее время являются работы таких ученых, как Овечкин Г.В., Овечкин П.В., Гринченко H.H., Овчинникова A.A.

Овечкин Г.В. предлагает новые методы конструирования и декодирования двоичных каскадных кодов, основанные на многопороговых алгоритмах декодирования самоортогональных кодов и оценку их эффективности, методику повышения эффективности работы МПД совместно.

В работе Овечкина П.В. предложены алгоритмы, применение которых позволит повысить эффективность работы недвоичного МПД.

Овчинников А.А в своей работе ставит целью получение новых, более эффективных, кодовых конструкций LDPC-кодов, оценку исправляющей способности как полученных, так и некоторых, уже известных кодовых конструкций.

Целью работы Гринченко H.H. является разработка алгоритмов помехоустойчивого кодирования на основе МПД, обеспечивающих высокую достоверность при большом уровне шума.

В этих и других работах не поднимается вопрос, освещенный в данной диссертации - вопрос разработки новой методики комплексной оценки помехоустойчивых кодов, применяемой на предварительном этапе построения систем кодирования/декодирования, реализующих защиту информации в высокоскоростных каналах передачи данных.

Также в первой главе рассмотрены основные положения теории помехоустойчивого кодирования, LDPC-коды как класс линейных блочных кодов, их преимущества и недостатки. Проведено сравнение LDPC-кодов с использующимися на сегодняшний момент помехоустойчивыми кодами.

Рассмотрен класс линейных блочных кодов и их основные характеристики, а так же основные методы кодирования и декодирования.

Приведено описание LDPC-кодов как класса блочных помехоустойчивых кодов и способ их задания с помощью проверочной матрицы. Рассмотрены виды LDPC-кодов, в зависимости от параметров и структуры проверочной матрицы. В их число входят регулярные и нерегулярные (irregular LDPC, iLDPC), систематические и несистематические, структурированные и неструктурированные LDPC-коды. Проведен обзор по способам генерации проверочной матрицы.

Рассмотрен способ описания LDPC-кодов с помощью графа Таннера, который представляет собой двудольный граф, в котором сопоставляются множество кодовых и множество проверочных вершин. Граф иллюстрирует механизм защиты информационных символов в кодовом слове, а так же является основой для построения итеративного декодера.

Отмечено, что работа декодера LDPC-кода ухудшается, если в графе Таннера соответствующего LDPC-кода присутствуют циклы небольшой длины. Как правило, циклы длины 6 не оказывают существенного влияния на качество декодирования, поэтому существующие на сегодня конструкции должны обеспечивать отсутствие циклов длины 4. Для этого достаточно, чтобы любые два столбца проверочной матрицы LDPC-кода не имели более одной общей ненулевой позиции.

Рассмотрены преимущества и недостатки LDPC-кодов. Среди преимуществ отмечены высокая исправляющая способность, растущая с увеличением длины кодового слова, высокая скорость декодирования, по сравнению с турбо-кодами, а так же отсутствие патентов на использование LDPC-кодов. Как недостаток этих кодов отмечено отсутствие четких методик построения кодов с заданными наперёд характеристиками и высокая вычислительная сложность оптимального декодера.

Приведены сравнения двоичных и недвоичных (Non-Binary) LDPC-кодов с лидерами в соответствующих классах помехоустойчивых кодов - с турбо-кодами в классе двоичных кодов и с кодами Рида-Соломона в классе недвоичных (рис. 1).

Vs N ---FI-C ипс^кЫ ---Сг.975 standard FKC ■ - l.DPC simulation/analysis * LI) PC* measured -

Vs Г \ ¥ N

\ V \ \ Ч Ч

V V \ 1 \ V N Ч Ч ч Ч ч \

\ V ч ч V

2.( > \ \ сЮ ^ 6.3 d3 \ -

I | \

(, 7 8 9 10 И 12 13 U 15 Hi

KleclrkalSNK I ill! I GWS.tJI.n

Рис. 1. (ITU-T G.975.1) сравнение BER для NB-LDPC и кода Рида-Соломона

(G.975 standard FEC).

Отмечено, что LDPC-код, вместо турбо-кода, стал частью стандарта DVB-S2 спутниковой передачи данных для цифрового телевидения, аналогичная замена произошла и в стандарте DVB-T2 для цифрового наземного телевизионного вещания. Кроме этого LDPC-коды вошли в

стандарты IEEE 802.3ап сети Ethernet 10G, IEEE 802.16e сетей 4G Mobile WiMax, содержаться в рекомендации ITU-T Ree. G.975.1 (02.2004).

Из результатов сравнений сделан вывод, что двоичные LDPC-коды имеют потенциальное превосходство над лидерами в классе двоичных линейных блочных кодов - турбо-кодами произведения, а недвоичные LDPC-коды имеют существенное преимущество над кодами Рида-Соломона, тоже лидерами в своём классе. Это преимущество увеличивается по мере увеличения длины кодового слова.

Во второй главе рассмотрены основные модели каналов связи, двоичный и д-ичные симметричные каналы без памяти, а так же канал с аддитивным белым гауссовским шумом.

Алгоритме инверсией бита (Bit Flipping)

Метрики (мягкий выход демодулятора)

Упрощенные метрики и процедура декодирования

Алгоритм с итеративным распространением доверия (IBP)

Алгоритм быстрого декодирования по надёжностям (UMP BP)

Уменьшение

вычислительной

сложности

Пересчет порога на каждой итерации

Алгоритм многопорогового декодирования (МПД)

Алгоритм декодирования минимум-суммы (min-sum)

Рис. 2. Взаимосвязь алгоритмов декодирования LDPC-кодов.

Приведены основные алгоритмы декодирования LDPC-кодов:

1. Алгоритм с инверсией бита (bit flipping algorithm, BF), он же -жесткое решение по Галлагеру;

2. Алгоритм с итеративным распространением доверия (iterative belief propagation algorithm, IBP), мягкое решение по Галлагеру; этот алгоритм является частным случаем, известного как сумма-произведений (sum-product algorithm, SP);

3. Алгоритм быстрого декодирования uniformly most powerful belief propagation (UMP BP), является развитием порогового алгоритма декодирования Месси;

4. Алгоритм многопорогового декодирования (multi-threshold algorithm, МТ) (МПД), является дальнейшим усовершенствованием алгоритма UMP BP.

5. Алгоритм быстрого декодирования минимум-суммы (min-sum algorithm, MS), является упрощением алгоритма sum-producf,

Схема, иллюстрирующая взаимосвязи алгоритмов приведена на рис. 2.

Для каждого из алгоритмов составлена схема, последовательно отражающая суть каждого этапа итерации. Основой для разбиения на логические блоки послужил принцип группировки схожих математических операций и наглядного представления сложных преобразований над кодовым словом (рис. 3).

1. Алгоритм с инверсией бита (BF).

«Жесткое» декодирование - это схема декодирования для двоичного симметричного канала при небольшом количестве ошибок в канале. Алгоритм декодирования инвертированием битов - самая простая по сложности схема декодирования кодов с низкой плотностью проверок на четность. В качестве основы используется модель двоичного симметричного канала без памяти. На каждом шаге происходит пересчет проверок на четность в каждом проверочном узле графа Таннера и инвертирование битов, для которых не выполнилась половина проверок на четность, превышающих некоторую заранее заданную величину.

Таким образом, одна итерация «жесткого» декодирования инвертированием битов производится следующим образом:

1. Для принятого вектора вычисляются все проверки;

2. Проверяется, не превышено ли максимальное число итераций;

3. Если некоторый бит принятого вектора участвовал более чем в половине не выполнившихся проверок, бит инвертируется;

4. После такого анализа всех символов принятого вектора вектор проверяется на принадлежность коду. Если вектор является кодовым словом, то есть выполнились все проверки на четность, декодирование заканчивается. В противном случае выполняется следующая итерация алгоритма.

Рис. 3. Схема декодирования ЬЭРС-кодов по алгоритму тт-5ит.

2. Алгоритм с итеративным распространением доверия (IBP).

Этот алгоритм работает не с двоичными значениями принятой реализации, а с их надёжностями. Он наиболее важен для рассмотрения, как алгоритм, показывающий теоретическое качество декодирования, наиболее близкое к оптимальному, что показал в своей работе Галлагер. Используется модель канала связи с аддитивным белым гауссовским шумом. Надежностью /-го символа принятого вектора будем считать величину, характеризующую удаление принятого значения от некоторого порогового значения, при котором все значения переданных символов равновероятны. Источником надёжностей для декодера является демодулятор с мягким выходом. В процессе работы алгоритма проверочные и битовые узлы обмениваются сообщениями, представляющими собой пересчеты надёжностей битов. Поэтому алгоритмы, реализующие такой подход, называются алгоритмами обмена сообщениями (message passing). Условные обозначения, используемые при описании:

• qij - сообщения от /-го битового узла>му проверочному узлу;

• Гц- ответы от j-го проверочного узла /'- му битовому узлу;

• LLRj - логарифмическое отношение правдоподобия (log-likehood ratio) для /-го символа;

• Bj - множество номеров битовых узлов, входящих в j-ю проверку;

• С, - множество проверок, в которых участвует /'-й битовый узлел;

• tanh(x) - функция вычисления гиперболического тангенса. Перед декодированием необходимо произвести инициализацию, которая

включает в себя установку максимального числа, равного т, формирование надёжностей каждого символа в виде логарифмических отношений правдоподобия и обнуление всех ответов проверочных узлов, т.е. rjti = 0 для

всех j = 1... п - к,, i = 1... п.

Одна итерация алгоритма sum-product включает:

1. Вычисляются надежности символов в форме LLR и формируются сообщения проверочным узлам:

qij = LLRi + ЕкбС;,к*|гм;

2. Вычисляются проверки и формируются сообщения кодовым узлам:

rJJL = 2 tanh"1 (Гtanh^f). (2)

3. Формируется выходной вектор, то есть выносится жесткое решение по надёжностям для каждого бита, по правилу:

bt = sign(LLR,+Zkec,»-w); (3)

4. Проверка принадлежности полученного вектора bt к пространству кодовых слов, суть пересчет проверок на чётность, как в алгоритме BF;

5. Если полученный вектор принадлежит коду, то декодирование завершается.

6. Если вектор не принадлежит коду и число выполненных итераций не превышает порога т, то переходим к шагу 2;

7. Если число выполненных итераций превысило порог, то фиксируется отказ от декодирования (ошибка) и на выход декодера идёт просто принятое слово без изменения.

Число т, как правило, определяется эмпирически, исходя из приблизительной дисперсии шума в канале, исправляющей способности кода и латентности декодирующей системы (времени, необходимом для декодирования одного слова) которая, в свою очередь, зависит от вычислительных ресурсов и длины кодового слова.

3. Алгоритм быстрого декодирования по надежностям (UMP ВР). Несмотря на то, что декодирование пересчетом вероятностей является эффективным методом для каналов с непрерывным выходом, тот факт, что сложность его значительно выше, чем сложность «жесткого» декодирования, оставляет место для поиска более быстрых алгоритмов декодирования, обладающих приемлемым качеством.

Пусть из канала был принят вещественный («мягкий») вектор "у = [у0,..., уп1}. Надежностью /-го символа вектора у будем считать величину Г/, характеризующую удаление принятого значения у, от некоего порогового значения thr, при котором все значения переданных символов равновероятны : thr: Р( 1 /у,) = Р(0/у,), = |yf — thr|. Для случая двоичной модуляции, при которой все биты кодового слова отображаются во множество {-1, +1} и передаются по симметричному каналу с двоичным входом и мягким выходом, пороговое значение ihr = 0, поэтому надежность принятого символа yt будет равна абсолютной величине принятого значения, т.е. П = |yi|. При декодировании используется вектор «жестких» решений х = {х0,...,хп_1} (вектор, состоящий из 0 и 1 и представляющий собой набор дискретных решений) и вектор надежностей г = [у0,..., yn_j} (вектор, состоящий из вещественных величин). По аналогии с вероятностным декодированием, каждому ненулевому символу проверочной матрицы приписываются два числа: Хц и rtJ, представляющие собой «жесткое» решение относительно символа j, полученное при помощи всех проверок, кроме й, и надежность символов /-й проверки без учета j-го символа соответственно. Декодирование также является итеративным. Одна итерация представляет собой следующую последовательность действий.

1. Для всех проверок и всех символов проверок вычисляется надежность проверок относительно символа j, представляющая собой минимальное значение надежностей всех символов, входящих в проверку, кроме самого символа j:

r'jx= mintEB.kfJrtj (4)

2. Для всех символов принятого вектора и всех проверок производится пересчет надежностей символов проверок: если проверка, в которую входил некоторый символ, не выполняется, то надежность Гц уменьшается на величину надежности проверки

г'ц, в противном случае надежность гц увеличивается на г'ф учитываются все проверки, кроме /-й. Если после, применения всех проверок для какого-то символа_/, величина стала меньше нуля, то обновленная надежность гК1 берется по модулю, а жесткое решение хц инвертируется.

3. Аналогично пересчитываются надежности принятого вектора: если г'-я проверка, в которую входиту'-й символ, нарушается, то из надежности г, вычитается надежность /-й проверки, иначе надежность символа увеличивается на надежность проверки. Если после применения всех проверок для какого-то символа ] величина г, стала меньше нуля, то обновленная надежность гч берется по модулю, а «жесткое» решение хц инвертируется.

4. Если «жесткое» решение х является кодовым словом, декодирование заканчивается, иначе декодер начинает следующую итерацию.

Сложность декодера ОмР значительно ниже, чем сложность декодера, пересчитывающего вероятности, за счет того, что пересчет надежностей выполняется по упрощенной схеме (схеме взвешенного мажоритарного голосования, где в качестве весов используется надежность проверок), а также за счет возможности использования исключительно целочисленных операций сложения и сложения по модулю два.

4. Алгоритм многопорогового декодирования (МПД)

Модификацией быстрого декодера по надежностям, позволяющей добиться приближения вероятности ошибки декодирования к вероятности, получаемой при вероятностном декодировании, является многопороговое декодирование. Быстрый декодер по надежностям (1МР) принимает решения относительно символов принятого вектора на основе пересчета надежностей и инвертирования символов «жесткого» решения, причем инвертирование символов производится всегда, когда соответствующая надежность после пересчета становится меньше нуля. Нуль в данном случае является порогом инвертирования символа, причем на всех итерациях этот порог остается неизменным. Поскольку на первых итерациях декодирования надежности символов еще плохо определены, то инвертирование таких символов может привести не к исправлению ошибок, а к внесению новых и, последующему их размножению.

Основная идея многопорогового декодирования по надежностям состоит в том, чтобы изменять значения порогов инвертирования символов от одной итерации к другой следующим образом:

• на первых итерациях порог инвертирования символов выбирается так, чтобы количество инвертированных символов было минимальным (вплоть до инвертирования только одного символа на первой итерации);

• на последующих итерациях пороги инвертирования постепенно повышаются.

5. Алгоритм быстрого декодирования минимум-суммы.

Качество декодирования по алгоритму с итеративным распространением доверия повышается за счет использования дополнительной информации на выходе канала. В IBP-алгоритме при формировании сообщения от проверочного узла битовым используется достаточно сложная для вычисления функция определения гиперболического тангенса и обратная от нее, а также операция умножения. Кроме того, качество работы такого алгоритма зависит от инициализации: чем точнее она произведена, тем точнее будет конечный результат. Для канала с гауссовским шумом инициализация может быть произведена при помощи информации о дисперсии шума в канале. Для других распределений шума в канале или при неизвестных характеристиках шума точная инициализация алгоритма может являться сложной задачей. Алгоритм минимум-суммы, являющийся удобным для реализации упрощением алгоритма IBP, лишен этих недостатков. Основное различие алгоритмов min-sum и sum-product состоит в способе вычисления значений r,j. В min-sum для вычисления сообщений от проверочных узлов к битовым, вместо выражения (2), используется более простое с вычислительной точки зрения:

rix = minkes fc=ti(|i7fcjl) rLceB^iSignCqk,/), (4)

причём проигрыш от применения подобного упрощения составляет примерно 0,5 дБ.

Отмечено, что именно данный алгоритм используется на данный момент для практической реализации известных LDPC-декодеров, поэтому ему в работе уделено особое внимание.

Существуют три типа архитектуры декодера LDPC-кода, это:

• полностью параллельная архитектура;

• частично-параллельная архитектура;

• последовательная архитектура.

Отмечено, что наилучшей производительностью будет обладать декодер с полностью параллельной архитектурой, но он же имеет самую высокую сложность реализации (с учетом схемотехнических ограничений) и, следовательно, высокую стоимость. Кроме того, такой декодер будет наименее гибким. Напротив, самой плохой производительностью будет обладать схема с последовательной архитектурой, но она проще и дешевле в реализации.

В третьей главе приведены процедуры оценки сложности реализации алгоритма декодирования и поиска вычислительно сложных этапов алгоритма декодирования.

Приведена методика подсчета числа математических операций для декодирования одного кодового слова на примере алгоритма min-sum. Для того чтобы оценить количество операций, необходимых вычислителю для

декодирования одного кодового слова, рассмотрена абстрактная модель (п, j, к)- LDPC-кода с информационной скоростью R = К/п.

Введены обозначения: N+.N^.N^.N^.Nq - число операций сложения, умножения, взятия по модулю, сравнения и сложения по модулю 2 соответственно. Общее число операций (АО, необходимых для декодирования одного кодового слова вычисляется из количества операций на одной итерации декодирования (W/), умноженных на общее число итераций (т).

N = mN, (5)

Количество операций на одной итерации декодирования, исключая первый шаг - инициализацию, определяется по формуле 6:

N, = \\Н\\ Nfaj) + ||И|| ЛГ(гу) + nWCöi) + %+ N(m) (6)

В этой формуле использованы:

• п - длина кодового слова в битах;

. Ц.. число проверок на четность (строк проверочной матрицы);

• ||Н|| = п] - количество ненулевых элементов проверочной матрицы;

• - число операций на 2 шаге декодирования при вычислении одного сообщения Цц\

• N(rLj)- число операций на 3 шаге декодирования при вычислении одного сообщения ri;-;

• N(bi) - число операций на 4 шаге декодирования при вычислении полной метрики одного бита кодового слова, с учетом поправок Гц и вынесении относительно этого бита «жесткого» решения

• N(ct) - число операций на 5 шаге декодирования при вычислении всех проверок (q) по жестким решениям из шага 4 и вынесении вердикта о принадлежности полученного вектора к пространству кодовых слов.

• N(m) - число операций на 6 шаге декодирования при сравнении значения счетчика итераций с максимальным числом итераций т;

Группируя одинаковые операции, получили итоговую формулу:

N = m[N+ + Nx+ N[a{ + N</> + Nq] = (7)

\nj2)+ + (nj(2j ~ 3) + n + !)</>+ (nj(k - l))x +'

+(«/(*-ч)1в1+(

В этом выражении:

• N+ = n;2;

• /V<7> = nj(2j - 3) + n + 1; . Nx = nj(k - 1);

• W|a| = nj(k -

Подсчитано общее количество операций на одно кодовое слово, зависящее только от параметров (,пк)- ЬОРС-кода:

ЛЬ = т[п/(;+£ + 4(Л-1))+п + 1] (8)

Таким образом, получены формулы для вычисления количества необходимых операций различного типа и общего количества операций для декодирования одного кодового слова в зависимости от параметров используемого ЬОРС-кода и числа итераций декодирования по алгоритму тт-вит.

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

Таким образом, имеются два массива одинакового размера, формирующиеся по очереди друг из друга. Каждый элемент одного массива вычисляется с использованием нескольких элементов другого массива. За исключением возможности одновременного обращения к одному элементу не обрабатываемого в данный момент массива, вычисления ведутся независимо, следовательно, они могут быть распараллелены. Этот вывод очень важен для выбора аппаратной платформы и особенностей реализации декодера.

Так же в третьей главе был сформулирован критерий определения вычислительно сложных этапов алгоритма декодирования. Вычислительно сложным этапом алгоритма декодирования помехоустойчивого кода называется этап, число элементарных математических операций на котором превышает порог, определяемый как отношение общего числа элементарных операций в алгоритме к числу логических блоков:

=га <*>

Под элементарными математическими операциями подразумеваются операции сложения, умножения, сравнения, взятия по модулю и сложения по

модулю 2. В основе построения данного критерия лежит следующий принцип: пороговый уровень равен такому числу операций, когда нельзя выделить ни один шаг алгоритма, для которого число операций, выполняемых на нём, было больше или меньше, чем для остальных. Таким образом, он определяется средним значением количества операций на блок при декодировании одного кодового слова.

Для (9, 6, 3) - LDPC-кода, опуская инициализацию (шаг 1), можно легко подсчитать, что:

• на шаге 2 выполняется: = nj(J — 1) = 18;

• на шаге 3 выполняется: Nfcj) = nj(Ak - 5) = 126;

• на шаге 4 выполняется: N(brf = n(J + 1) = 27;

• на шаге 5 выполняется: N(cJ = —(к — 1) = 12;

• на шаге 6 выполняется 1 операция.

Всего: 184 операции.

Очевидно, что самым вычислительно сложным является шаг 3 каждой итерации. По формуле (9) получаем значение порога: Nthr - [36,81 = 37 операций. Порог в 37 операций превышает только шагЗ. Таким образом, шаг 3 на каждой итерации является самым ресурсоёмким этапом алгоритма min-sum.

Рассмотрены возможные варианты аппаратной платформы LDPC-декодера, такие как ASIC (SOC), ПЛИС, CPU, GPU. ASIC - application specified integrated circuit, интегральная схема, специализированная для решения конкретной задачи. ПЛИС - программируемая логическая интегральная схема (programmable logic device, PLD) — электронный компонент, используемый для создания цифровых интегральных схем. В отличие от обычных цифровых микросхем, логика работы ПЛИС не определяется при изготовлении, а задаётся посредством программирования. CPU и GPU - central processing unit (центральный процессор, ЦП) и graphic processing unit (графический процессор) также могут являться аппаратной платформой для создания декодера, который будет функционировать в совокупности с аппаратным модулем преобразования интерфейсов или первичной обработки цифрового потока на плате со стандартным PCI-разъёмом и программу, реализующую сам процесс декодирования. При рассмотрении возможных вариантов реализации LDPC-декодера и выборе аппаратной части мы приходим к выводу, что определяющую роль играют:

• архитектура реализуемого декодера (последовательная, параллельная, частично параллельная);

• пропускная способность и гибкость готового декодера.

• стоимость аппаратной платформы и сопутствующего ПО;

Под гибкостью понимается, насколько велико множество поддерживаемых декодером кодов с различными длинами и кодовыми скоростями.

На основании комплексного анализа помехоустойчивого кода и анализа специфических свойств тех или иных аппаратных платформ, а так же исходя из анализа характерных особенностей алгоритма декодирования, можно сформулировать рекомендации для реализации декодера с учетом достоинств и недостатков различных аппаратных платформ.

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

1. Сравнительный анализ помехоустойчивых кодов и определение областей применения рассматриваемых типов кодов;

2. Анализ алгоритмов кодирования/декодирования, характерных для данных типов кодов и выбор наиболее релевантного алгоритма для рассматриваемой системы передачи данных;

3. Оценка сложности выбранного алгоритма, разбиение его на логические блоки, составление схемы данного алгоритма;

4. Определение вычислительно сложных этапов алгоритма для аппаратной или аппаратно-программной реализации;

5. Выработка рекомендаций по реализации данного алгоритма на различных классах вычислителей

В заключении сформулированы основные результаты работы, полученные автором. В ходе исследований получены следующие новые теоретические и практические результаты:

1. Выявлена взаимосвязь алгоритмов декодирования ЬБРС-кода;

2. Предложен критерий определения вычислительно сложных этапов алгоритмов кодирования/декодирования для итеративно декодируемых кодов, применяемых в высокоскоростных каналах передачи данных;

3. Разработана методика комплексной оценки помехоустойчивых кодов, применяемых в высокоскоростных каналах передачи данных.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в изданиях, внесенных в перечень ВАК Минобрнауки России

1. Солтанов А.Г. Схемы декодирования и оценка эффективности 1Л)РС-кодов. Применение, преимущества и перспективы развития // Безопасность информационных технологий. М.: 2010, №2, с. 61-68 (0,6 п.л.)

2. Солтанов А.Г.Перспективность ЬЭРС-кодов для систем передачи информации и предпосылки их применения в волоконно-оптических линиях связи // Информатизация и связь. М.: 2011, №2, с. 16-18 (0,2 пл.)

3. Солтанов А.Г. Помехоустойчивое кодирование в системах связи: особенности и отличительные характеристики ЬОРС-кодов // Информатизация и связь. М.: 2011, №2, с. 18-22 (0,3 п.л.)

Публикации в других изданиях

4. Солтанов А.Г. Преимущественные характеристики помехоустойчивых кодов, применяемых для обработки и анализа кадров в смешанных сетях передачи данных. Корректирующая способность кода Хемминга и циклического кода (9,5) // Бюллетень Владикавказского Института Управления. Владикавказ.: 2010, №34, с. 112-128 (0,7 п.л.)

5. Солтанов А.Г. Реализация на ПЛИС алгоритмов помехоустойчивого кодирования, Сборник материалов Всероссийской межвузовской научно-технической конференции «Микроэлектроника и информатика -2008». Москва.: 2008 (0,1 п.л.)

СПИСОК ИСПОЛЬЗОВАННЫХ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1. Защита информации от угроз нарушения целостности. Основные положения теории помехоустойчивого кодирования. LDPC-коды как класс линейных блочных кодов, их преимущества и недостатки.

1.1. Защита информации от угроз нарушения целостности.

1.2. Основы теории помехоустойчивого кодирования. Место системы помехоустойчивого кодирования в современных системах передачи информации.

1.3. Описание LDPC-кодов.

1.4. Преимущества и недостатки LDPC-кодов. Сравнение LDPC-кодов с использующимися в современных системах связи помехоустойчивыми кодами.

ГЛАВА 2. Основы кодирования и декодирования LDPC-кодов. Основные алгоритмы декодирования, их преимущества и недостатки. Сравнение алгоритмов декодирования LDPC-кодов.

2.1. Математические модели каналов связи.

2.2. Алгоритмы декодирования LDPC-кодов. Обзор. Сравнение.

2.2.1. Алгоритм с инверсией бита (BF).

2.2.2. Алгоритм с итеративным распространением доверия (IBP).

2.2.3. Алгоритм быстрого взвешенного мажоритарного декодирования UMPBP.

2.2.4. Алгоритм многопорогового декодирования (МПД).

2.2.5. Алгоритм быстрого декодирования минимум-суммы.

ГЛАВА 3. Методика комплексной оценки помехоустойчивых кодов и алгоритмов декодирования.

3.1. Подсчет числа операций, выполняемых для декодирования одного кодового слова для алгоритма пип-эит.

3.2. Выявление характерных особенностей алгоритмов декодирования на примере алгоритма пип-бши.

3.3. Критерий определения вычислительно сложных этапов алгоритма декодирования.

3.4. Особенности аппаратной реализации 1Л>РС-декодера.

3.5. Содержание методики оценки кодов.

Актуальность темы. В настоящее время деятельность любой организации невозможно представить без использования корпоративных сетей (КС), которые играют значительную роль в жизненном цикле производства продукции или оказании услуг. Их роль и влияние на обеспечение качества продукции и услуг постоянно растет.

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

Основной функцией КС является обеспечение возможности постоянного получения, обработки, передачи и модификации информации. Эффективность выполнения данной функции определяется контролем над тремя основными свойствами информации: конфиденциальностью, целостностью, доступностью.

В теории компьютерной безопасности выделяют три вида преобразования информации, применяемых для защиты от угроз нарушения целостности информации: криптографическое шифрование, помехоустойчивое кодирование и сжатие (эффективное кодирование). Общим для всех трех видов преобразования является то, что информация неким образом меняет форму представления, сохраняя смысл. Выбор тех или иных видов кодирования определяется целью проводимых преобразований.

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

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

Для решения проблем передачи информации в реальных системах связи необходимо комплексное использование различных методов и средств. Криптографическое шифрование, помехоустойчивое кодирование и сжатие дополняют друг друга, и их комплексное применение помогает эффективно использовать каналы связи для надежной защиты передаваемой информации.

Увеличение скоростей передачи данных в канале влечет за собой возрастание количества случайных помех, способных исказить хранимые, обрабатываемые и передаваемые данные. Это обуславливает актуальность разработки и использования новых алгоритмов и методов, позволяющих 8 обнаруживать и корректировать подобные ошибки. В данных условиях особого внимания заслуживают помехоустойчивые коды, позволяющие, в отличие от криптографического шифрования и сжатия, эффективно бороться со случайными ошибками в канале.

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

Корректирующие коды получили широкое применение в задачах защиты информации. В настоящее время такие коды представлены в многочисленных технических приложениях, например, в стандартах 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, низкоплотностный код) были впервые предложены Р. 9

Галлагером и позднее исследовались во многих научных трудах В.Д. Колесника, C.B. Федоренко, В.В. Золотарева, Г.В. Овечкина, Е.А. Крука, В.Б. Афанасьева, Е.Т. Мирончикова, Э.М. Габидулина. Работы этих ученых создали базу для проведения исследований в вопросах анализа различных алгоритмов помехоустойчивого кодирования с применением LDPC-кодов, однако ряд вопросов по-прежнему требует исследования.

Несмотря на то, что в течение долгого времени LDPC коды были практически исключены из рассмотрения, в последние годы наблюдается увеличение количества исследований в этой области. Это связано с тем, что коды с малой плотностью проверок на четность обеспечивают высокую степень исправления ошибок несмотря на то, что обладают плохим минимальным расстоянием. Было показано, что с ростом длины кодового слова некоторые LDPC-коды могут превосходить турбо-коды и приближаться к пропускной способности канала с аддитивным белым гауссовским шумом (АБГШ). В настоящее время максимальное приближение к границе Шеннона даёт LDPC-код с примерной длиной блока в 10 миллионов бит. Вместе с тем, многие предложенные конструкции LDPC-кодов являются циклическими или квазициклическими, что позволяет производить не только быстрое декодирование, но и эффективные процедуры кодирования. Кроме того, для LDPC-кодов, не обладающих свойством цикличности, были предложены эффективные процедуры кодирования.

LDPC-коды становятся востребованы в системах передачи информации, требующих максимальной скорости передачи при ограниченной полосе частот. Основным конкурентом LDPC-кодов на данный момент являются турбо-коды, которые нашли своё применение в системах спутниковой связи, некоторых стандартах цифрового телевидения и мобильных системах связи третьего поколения.

В отличие от турбо-кодов, LDPC-коды более предпочтительны в каналах с меньшими вероятностями ошибок. С развитием методов передачи ю информации каналы передачи улучшаются, что даёт хорошую перспективу для развития LDPC-кодов.

Имеет место также и правовой аспект применения LDPC-кодов и турбо-кодов. Компании France Telecom и Télédiffusion de France запатентовали широкий класс турбо-кодов, что ограничивает возможность их свободного применения и в то же время стимулирует развитие и использование других методов кодирования, таких как LDPC. LDPC-коды под патентные ограничения не попадают.

Существуют также и объективные причины, по которым LDPC-коды до недавнего времени не занимали лидирующих позиций в линейке помехоустойчивых кодов - высокая ресурсоемкость и вычислительная сложность алгоритмов декодирования с применением LDPC-кодов. Но, в связи с развитием мощности и быстродействия средств вычислительной техники, на данный момент LDPC-коды могут рассматриваться как одни из наиболее эффективных кодов, применение которых актуально на скоростях 10, 40 и 100 Гбит/с для оптоволоконных систем связи. Актуальность этих кодов объясняется следующими преимуществами их использования по сравнению с другими классами кодов:

- при большой длине кодового слова LDPC коды достигают границы Шеннона;

- при правильном построении кода отсутствует нижний предел ошибок (error floor);

- существуют эффективные алгоритмы декодирования LDPC кодов.

Объектом исследования являются методы и средства информационного противодействия угрозам нарушения информационной безопасности.

Предметом исследования являются средства обеспечения защиты от угроз нарушения целостности информации в высокоскоростных каналах передачи данных.

Целью диссертационного исследования является разработка новой методики комплексной оценки помехоустойчивых кодов, применяемой на предварительном этапе построения систем, реализующих защиту информации в высокоскоростных каналах передачи данных (на примере ЫЭРС-кода).

Для достижения цели были поставлены и решены следующие задачи:

1. Проведен сравнительный анализ различных методов помехоустойчивого кодирования и определение областей применения 1ЛЗРС-кодов.

2. Проанализированы алгоритмы кодирования/декодирования ЫЭРС-кодов, применяемые в оптоволоконных системах связи и радиоканалах.

3. Проведена оценка сложности алгоритма на примере алгоритма гшп-Бит и выделены структурные логические блоки в составе данного алгоритма.

4. Разработан программный моделирующий комплекс для проверки функционирования параметрически настраиваемого алгоритма декодирования ЫЭРС-кода.

5. Предложен критерий определения вычислительно сложных этапов алгоритмов декодирования ЬЭРС-кода для аппаратной и программно-аппаратной реализации.

6. Проведена оценка вычислительной сложности алгоритма декодирования Ы)РС-кода.

7. Сформулированы рекомендации по реализации алгоритмов декодирования ЫЭРС-кода на различных классах вычислителей в зависимости от параметров.

Теоретические и методологические основы исследования. Теоретической основой диссертационного исследования явились разработки зарубежных и российских ученых и специалистов по проблемам защиты информации, помехоустойчивого кодирования, теории информации.

12

Информационную базу исследования составляют сведения, публикуемые в научных изданиях, в периодической печати, материалы международных и российских научных конференций по рассматриваемой проблеме, стандарты в области защиты информации, цифровой радиосвязи.

Для решения поставленных задач использовались аналитические методы исследования математических моделей, имитационное моделирование и экспериментальное исследование описываемых кодов, теории помехоустойчивого кодирования, теории вероятностей и математической статистики, теории графов. Экспериментальные исследования проведены с использованием пакета математического, статистического и имитационного моделирования МАТЬАВ.7.01.

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

1. Разработана новая, научно обоснованная методика комплексной оценки помехоустойчивых кодов, которая может применяться на начальном этапе разработки систем помехоустойчивого кодирования, позволяющих с заданной достоверностью гарантировать защищенность целостности данных от разрушающих воздействий в высокоскоростных каналах передачи данных, реализуя механизмы защиты информационных символов. Отличительной особенностью данной методики является то, что она оперирует комплексным набором показателей для оценки кода, учитывает различные аспекты использования данного типа кодов и предназначена для оценки возможности и способов построения систем декодирования с применением рассматриваемого типа кодов. Методика приведена на примере ЬБРС-кода.

2. Выявлена взаимосвязь алгоритмов декодирования ЬБРС-кода, которая позволяет раскрыть иерархическую вложенность данных алгоритмов и сделать вывод о том, какой алгоритм является наиболее релевантным для определенной системы передачи данных с заданными параметрами.

3. Разработан способ оценки сложности алгоритмов декодирования кода, реализуемый путем разбиения алгоритмов декодирования выбранного кода на логические блоки, составления схем данных алгоритмов и подсчета количества операций. Данный способ позволяет оценить ресурсоемкость алгоритма и выработать рекомендации по аппаратному и программно-аппаратному составу комплексов помехоустойчивого кодирования, реализующих данный код.

4. Предложен критерий определения вычислительно сложных этапов алгоритма для аппаратной и программно-аппаратной реализации, позволяющий выработать рекомендации по его реализации на различных классах вычислителей за счет выявления характерных особенностей данного алгоритма.

Теоретическая и практическая значимость исследования. Теоретическая значимость исследования заключается в формировании нового подхода к совершенствованию способов обеспечения защиты от угроз нарушения целостности информации в высокоскоростных каналах передачи данных и реализации устройств помехоустойчивого кодирования для каналов связи на основе алгоритмов, использующих коды с малой плотностью проверок на чётность. Предлагаемый подход не призван заменить существующие методики реализации устройств, а применяется на предварительном этапе анализа канала связи и оценки помехоустойчивого кода.

Практическая значимость диссертационного исследования состоит в том, что разработанные рекомендации и методики могут быть использованы при разработке систем, реализующих защиту информации от угроз нарушения целостности в корпоративных сетях. Кроме того, результаты также могут быть использованы в образовательном процессе высших

14 учебных заведений, при написании учебников и учебных пособий (по специальностям - 090102.65 «Компьютерная безопасность», 090900.62 «Информационная безопасность», 230400.68 «Информационные системы и технологии» и т.п.).

Работа соответствует паспорту специальности 05.13.19 - Методы и системы защиты информации, информационная безопасность (пункт 5 -методы и средства (комплексы средств) информационного противодействия угрозам нарушения информационной безопасности в открытых компьютерных сетях, включая Интернет).

На защиту выносятся следующие положения диссертации:

1. Взаимосвязь алгоритмов декодирования помехоустойчивого ЫЭРС-кода

2. Критерий определения вычислительно сложных этапов алгоритмов кодирования/декодирования для итеративно декодируемых кодов, применяемых в высокоскоростных каналах передачи данных

3. Методика комплексной оценки помехоустойчивых кодов, применяемых в высокоскоростных каналах передачи данных

Достоверность и обоснованность полученных результатов обеспечиваются применением корректных исходных данных, апробированного аппарата исследований, проверкой непротиворечивости и адекватности промежуточных и окончательных положений и выводов, подтверждается полученными экспериментальными данными, совпадающими с существующими данными об эффективности известных кодов.

Основные положения и выводы диссертационного исследования были внедрены в ООО «ЦИБИТ». Также.отдельные положения диссертации используются при проведении учебных занятий по следующим программам повышения квалификации: «Организация защиты информации», «Безопасность компьютерных систем», «Программно-аппаратные средства защиты информации в распределенных вычислительных системах» в войсковой части №11928.

Апробация работы. Основные положения диссертации доложены и одобрены на Всероссийской межвузовской научно-технической конференции «Микроэлектроника и информатика - 2010» (Москва, 2010); на Международной научно-технической конференции «Системные проблемы надежности, качества, информационно-телекоммуникационных и электронных технологий в управлении инновационными проектами. «Инноватика-2010» (Москва-Сочи, 2010); на Российской научно-технической конференции «Информатика и проблемы телекоммуникаций» (Москва-Новосибирск, 2011); на ряде научно-практических семинаров в СКГМИ (Москва-Владикавказ, 2008-2011 гг.).

Публикации. Основные результаты диссертации опубликованы в 5 печатных работах, общим авторским объемом 1,9 п.л., в том числе 3 из них в изданиях, рекомендованных ВАК Минобрнауки России.

Структура и объем работы. Диссертация состоит из введения, трех глав и заключения, списка использованных источников. Работа представлена на 110 страницах машинописного текста, включает 2 таблицы и 25 рисунков, библиография из 112 наименований.

Выводы по главе 3:

1) В рамках комплексной оценки помехоустойчивых кодов, на примере алгоритма декодирования 1Л)РС-кодов минимум-суммы:

• получены аналитические выражения, позволяющие быстро оценить ресурсоёмкость алгоритма, зная лишь параметры используемого кода;

• проведено исследование алгоритма декодирования минимум-суммы на предмет выявления характерных особенностей данного алгоритма, таких как, например, внутренний параллелизм в вычислениях;

• сформулирован критерий определения ресурсоёмких этапов алгоритма декодирования, приведён пример его использования для (9, 2, 3) - ЬЭРС-кода;

• рассмотрены возможные варианты аппаратной реализации декодера с учетом выявленных характерных особенностей и ресурсоёмких этапов, сформулированы рекомендации по практический реализации декодеров с учетом этих особенностей.

2) Сформулировано содержание методики комплексной оценки помехоустойчивых кодов.

ЗАКЛЮЧЕНИЕ

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

1. Выявлена взаимосвязь алгоритмов декодирования 1ЛЭРС-кода;

2. Предложен критерий определения вычислительно сложных этапов алгоритмов кодирования/декодирования для итеративно декодируемых кодов, применяемых в высокоскоростных каналах передачи данных;

3. Разработана методика комплексной оценки помехоустойчивых кодов, применяемых в высокоскоростных каналах передачи данных.

ITU-T Rec. G.975.1 (02.2004) (перевод)

1. Shannon CI. E.communication in the Presence of Noise. IRE National Convention. New York, N. Y., March 24, 1948.

2. Владимиров C.M. Использование кодов с малой плотностью проверок на чётность // Московский физико-технический институт, УДК 519.688

3. Gallager R. G. Low density parity check codes // IRE Trans. Inform. Theory. Jan. 1962. Vol. IT-8.

4. Золотарев B.B. Овечкин Г.В. Помехоустойчивое кодирование. Методы и алгоритмы. М.: Горячая линия Телеком, 2004

5. Овчинников А.А. К вопросу о построении LDCP-кодов на основе евклидовых геометрий // Вопросы передачи и защиты информации: Сборник статей под ред. А. Крука. СПбГуаП. СПб., 2006. 226 с.

6. MacKay D.J.C., Neal R.M. Near Shannon limit performance of low density parity check codes // IEEE Electronics Letters. Aug. 1996. V.32. №18.

7. Ю.Б. Зубарев, Г.В. Овечкин. Помехоустойчивое кодирование в цифровых системах передачи данных // Электросвязь, 2005.

8. Крук Е.А. Вопросы защиты и передачи информации. Сборник статей, Санкт-Петербург, 2006; С. 25-37.

9. Овечкин Г.В. Применение min-sum алгоритма для декодирования блоковых самоортогональных кодов, УДК 681.391; С. 1-2.

10. Mansour М. М., Shanbhag N. R. High&Throughput LDPC decoders// IEEE Transactions on VLSI Systems. 2003. Vol. 11. N 6.

11. Дж. Кларк мл., Дж. Кейн. Кодирование с исправлением ошибок вцифровых системах связи, Москва «Радио и Связь», 1986.99

12. Amin Shokrollahi. LDPC Codes. An Introduction, Digital Fountain, Inc. 2003.

13. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования кодирования. Методы, алгоритмы, применение, Мир Связи, 2005.

14. Золотарев В.В. Теория и алгоритмы многопорогового декодирования. М.: Радио и связь, Горячая линия — Телеком, 2006.

15. Д.П. Зегжда, A.M. Ивашко. Как построить защищенную информационную систему. СПб: Мир и семья. - 1997г.

16. П.Н. Девянин, О.О. Михальский, Д.И. Правников, А.Ю. Щербаков. Теоретические основы компьютерной безопасности. М.: Радио и связь.- 2000г.

17. С.С. Корт. Теоретические основы защиты информации. Учебное пособие. М.:«Гелиос». 2004г.

18. Зубарев Ю.Б., Золотарев В.В., Овечкин Г.В., Обзор методов помехоустойчивого кодирования с использованием многопороговых алгоритмов // Цифровая обработка сигналов, 2008, №1, С.2-11.

19. Valenti М.С., Cheng S., Iyer Seshadri R. Turbo and LDPC codes for digital video broadcasting // Chapter 12 of Turbo Code Applications: A Journey from a Paper to Realization, Springer, 2005.

20. Белоголовый А. В., Крук E. А. Многопороговое декодирование кодов с низкой плотностью проверок на четность // Вопросы передачи и защиты информации: Сборник статей под ред. А. Крука СПбГуаП. СПб., 2006. 7 с.

21. Золотарев В. В., Овечкин Г. В. Обзор исследований и разработок методов помехоустойчивого кодирования (по состоянию на 2005 год).

22. Солтанов А.Г. Схемы декодирования и оценка эффективности LDPC-кодов. Применение, преимущества и перспективы развития // Безопасность информационных технологий. М.: 2010, №2, с. 61-68.

23. Солтанов А.Г.Перспективность LDPC-кодов для систем передачи информации и предпосылки их применения в волоконно-оптических линиях связи // Информатизация и связь. М.: 2011, №2, с.16-18.

24. Солтанов А.Г. Помехоустойчивое кодирование в системах связи: особенности и отличительные характеристики LDPC-кодов // Информатизация и связь. М.: 2011, №2, с. 18-22.

25. PC Codes, Application to Next Generation Communication Systems -Dr. Lin-Nan Lee Vice President. Hughes Network Systems, Germantown, Maryland 20854, October 8, 2003.

26. Воробьев К. А. методы построения и декодирования недвоичных низкоплотностных кодов // Теория и практика системного анализа. 2010. Т. II.

27. Золотарев В.В., Овечкин Г.В. Помехоустойчивое кодирование. Методы и алгоритмы. Справочник. М.: Горячая линия Телеком, 2004.

28. Витерби А. Границы ошибок для сверточных кодов и асимптотически оптимальный алгоритм декодирования // Некоторые вопросы теории кодирования. М.: Мир, 1970.

29. Золотарев В.В., Овечкин Г.В. Многопороговые декодеры для каналов с предельно высоким уровнем шума // Телекоммуникации. 2005. №9.

30. Richardson Т., Shokrollahi М., Urbanke R. Design of capacity-approaching irregular low-density parity-check codes // IEEE Trans. Inform. Theory. 2001. V.47.

31. Berrou C., Glavieux A., Thitimajshima P. Near Shannon Limit Error Correcting Coding and Decoding: Turbo Codes // Proc. of the Intern. Conf. on Commun. 1993. May.

32. Press Release, AHA announces Turbo Product Code Forward Error Correction Technology. 1998.

33. Williams D. Turbo Product Code FEC Contribution // IEEE 802.16.1pc 00/35. 2000.

34. Золотарев B.B., Овечкин Г.В. Использование многопорогового декодера в каскадных схемах // Вестник РГРТА. 2003. Вып.11.

35. Золотарев В.В. Параллельное кодирование в каналах СПД // Вопросы кибернетики. 1986. Вып.120.

36. Месси Дж. Пороговое декодирование / Пер. с англ.; Под ред. Э.Л. Блоха. М.: Мир, 1966.

37. Золотарев В.В., Овечкин Г.В. Сложность реализации эффективных методов декодирования помехоустойчивых кодов // 6-я межд. конф. и выст. DSPA-2006. М.: 2004. Т.1.

38. Jin Н, Khandekar A., McEliece R. Irregular repeat-accumulate codes // Proc. 2nd Int. Symp. on Turbo Codes and Related Topics. 2000, Sept.

39. Ф.Дж. Мак-Вильямс, Н.Дж.А. Слоэн. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

40. A. А. Овчинников. Об одном классе кодов, исправляющих пакеты ошибок Тез. докл. Второй международной школы-семинара БИКАМП'99, СПб, 1999.

41. Золотарев В.В., Овечкин Г.В., Овечкин П.В. Эффективность каскадных схем кодирования на базе многопорогового декодера // Межвузовый сборник научных трудов «Математическое и программное обеспечение вычислительных систем». Рязань, РГРТА, 2005.

42. Р. Блейхут. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.

43. Р. Грэхем, Д. Кнут, О. Паташник. Конкретная математика. Основание информатики. М.: Мир, 1998.

44. B.В. Зяблов, М.С. Пинскер. Оценка сложности исправления ошибок низ-коплотностными кодами Галлагера. Проблемы передачи информации, XI(1), 1975.

45. Т. Касами, Н. Токура, Е. Ивадари, Я. Инагаки. Теория кодирования. М.: Мир, 1978.

46. Р. Кеннеди. Каналы связи с замираниями и рассеянием. М.: Советское радио, 1973.

47. Дж. Кларк, мл., Дж. Кейн. Кодирование с исправлением ошибок в системах цифровой связи. М.: Радио и связь, 1987.

48. В.Д. Колесник, Е. Т. Мирончиков. Декодирование циклических кодов. М.: Связь, 1968.

49. В.И. Коржик, Л.М. Финк. Помехоустойчивое кодирование дискретныою сообщений в каналах со случайной структурой. М.: Связь, 1975.

50. Е. Крук. Комбинаторное декодирование линейных блоковых кодов. Диссертация на соискание ученой степени доктора технических наук, СПбГУАП, 1999.

51. А. А. Овчинников. Метрики для марковских каналов. VI Научная сессия аспирантов СПбГУАП: Тез. докл. СПб, 2003.

52. А. А. Овчинников. Некоторые замечания о спектральных свойствах EG-кодов. VII Научная сессия аспирантов СПбГУАП: Тез. докл. СПб, 2004.

53. У. Питерсон, Э. Уэлдон. Коды, исправляющие ошибки. М.: Мир, 1976.

54. Дж. Прокис, Цифровая связь. М.: Радио и связь, 2000.

55. А. Н. Banihashemi. Iterative Coding for Broadband Communications: New Trends in Theory and Practice. Broadband Communications and Wireless Systems (BCWS) Centre Dept of Systems and Computer Engineering Carleton University.

56. А. А. Овчинников. Моделирование канала связи для систем МС-CDMA. V Научная сессия аспирантов СПбГУАП: Тез. докл. СПб, 2002.

57. G. Caire, G. Taricco,, Е. Biglieri. Bit-interleaved coded modulation. IEEE Trans. Inform. Theory, 44(3), May 1998.

58. C.-L. Chen. On Majority-Logic Decoding of Finite Geometry Codes. IEEE Transactions on Information Theory, IT-17(3):332-336, May 1971.

59. J. Chen, M. P. C. Fossorier. Decoding low-density parity-check codes with normalized APP-based algorithm, in Proc. IEEE Globecom, pages 10261030, Nov. 2001.

60. M. C. Davey, D. J. C. MacKay. Low density parity check codes over GF(q). IEEE Communications Letters, 2(6):165-167, June 1998.104

61. E. Elefitheriou, T. Mittelholzer,, A. Dholakia. Reduced-complexity decoding algorithm for low-density parity-check codes. IEE Electronics Letters, 37:102-104, Jan. 2001.

62. P. G. Neumann. A note on Gilbert burst-correcting codes. IEEE Transactions on Information Theory, IT-11:377, July 1965.

63. L. R. Bahl, R. T. Chien. On Gilbert Burst-Error-Correcting Codes. IEEE Transactions on Information Theory, 15(3), May 1969.

64. D. Burshtein, M. Krivelevich, S. Litsyn,, G. Miller. Upper bounds on the rate f ldpc codes. IEEE Transaction on Information Theory, 48(9):2437, Sept. 002.

65. D. Burshtein, G. Miller. Bounds on the performance of belief propagation decoding. IEEE Trans. Inform. Theory, 48:112-122, Jan. 2002.

66. H. Niu, M. Shen, J. Ritcey, H. Liu. Iterative Channel Estimation and LDPC Decoding over Flat-Fading Channels: A Factor Graph Approach. 2003 Conference on Information Sciences and Systems, The Johns Hopkins University, March 12-U;, 2003.

67. E. O. Elliott. Estimates of error-rates for codes on burst-noise channels. Bell Sys. Tech. J., 42:1977-1997, Sept. 1963.

68. G. D. Forney, T. J. Richardson, R. L. Urbanke,, S.-Y. Chung. On the Design of Low-Density Parity-Check Codes within 0.0045 db of the Shannon Limit. EEE Communications Letters, 5(2), Feb. 2001.

69. M. Fossorier, M. Mihaljevic,, H. Imai. Reduced Complexity Iterative Decoding of Low-Density Parity-Check Codes Based on Belief Propagation. IEEE Transactions on Communicationsi 47(5), May 1999.

70. G. D. Forney Jr. Codes on graphs: Normal realizations. IEEE Trans. Inform. Theory, 47, Feb. 2001.

71. Е. N. Gilbert. Capacity of a burst-noise channel. BellSys. Tech. J.,39:1253-1265, Sept. 1960.

72. E. N. Gilbert. A problem in binary encoding. In Proceedings of the Symposium in Applied Mathematics, volume 10, pages 291-297, I960.

73. J. Hou, P. H. Siegel,, L. B. Milstein. Performance Analysis and Code Optimization of Low Density Parity-Check Codes on Rayleigh Fading Channels. IEEE Journal on Selected Ares in Communications, 19:924-934, May 5.

74. D. Hush, E. Svensson,, D. Arnold. High-rate low-density parity-check codes: construction and application, in Proc. 2nd Int. Symposium on Turbo Codes and Related Topics, Brest, France, pages 447-450, Sept. 2000.

75. R. G. Gallager. Low Density Parity Check Codes. Cambridge, MA: MIT Press, 1963.

76. H. Imai, S. Hirakawa. A new multilevel coding method using error correcting codes. IEEE Transactions on Information Theory, 23(3):371-377, May 1977.

77. T. Kasami, S. Lin. On Majority-Logic Decoding for Duals of Primitive Polynomial Codes. IEEE Transactions on Information Theory, IT-17(3):322-331, May 1971.

78. T. Kasami, S. Lin,, W. W. Peterson. Polynomial Codes. IEEE Transactions on Information Theory, 14, 1968.

79. Г.В. Басалова, Основы криптографии., Интуит, М.2008.

80. Y. Kou, S. Lin,, M.P.C. Fossorier. Construction of low-density parity-check odes: A geometric approach. In Proc. 2nd Int. Symp. Turbo Codes and Related Topics, pages 137-140, Brest, France, Sept. 2000.

81. E. A. Krouk, S. V. Semenov. Low-density parity-check burst error-correcting codes. In 2 International Workshop "Algebraic and combinatorial coding heory", Leningrad, pages 121-124, 1990.

82. F. R. Kschischang, B. Frey,, H.-A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Trans. Inform. Theory, 47(2), 2001.

83. G. Lechner. Convergence of Sum-Product Algorithm for Finite Length Low-Density Parity-Check Codes. Winter School on Coding and Information Theory, Monte Verita, Switzerland, Feb. 24-21, 2003.

84. J. Hou, P. H. Siegel, L. B. Milstein,, H. D. Pfister. Capacity-approaching bandwidth-efficient coded modulation schemes based on low-density parity-check codes. IEEE Transactions On Information Theory, 49(9):2141-2155, September 2003.

85. X.-Y. Hu, E. Eleftheriou,, D.-M. Arnold. Regular and Irregular Progressive Edge-Growth Tanner Graphs. IBM Research, Zurich Research Laboratory, 2003.

86. S. Lin. On the Number of Information Symbols in Polynomial Codes. IEEE Transactions on Information Theory, 18(6):785-794, Nov. 1972.

87. S. Lin. Shortened Finite Geometry Codes. IEEE Transactions on Information Theory, 18(5):692-696, Sept. 1972.

88. S. Litsyn, V. Shevelev. On ensembles of low-density parity-check codes: distance distributions. IEEE Trans. Inform. Theory, submitted for publication.

89. M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi,, D. A. Spielman. Improved ow-density parity-check codes using irregular graphs and belief propagation, n Proceedings of the IEEE International Symposium on Informati on Theory ISIT), page 117, 1998.

90. M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman,, V. Stemann. Practical loss-resilient codes, in Proc. 29th Annual ACM Symp. Theory of Computing, 1997.

91. R. Lucas, M. P. C. Fossorier, Y. Kou„ S. Lin. Iterative decoding of one-step majority logic decodable codes based on belief propagation. IEEE Trans. Commun., June 2000.

92. D. MacKay. Good error correcting codes based on very sparse matrices. IEEE Transactions on Information Theory, 45, Mar. 1999.

93. D. MacKay, R. Neal. Near Shannon Limit Performance of Low-Density Parity-Check Codes. IEEE Transactions on Information Theory, 47(2), Feb. 2001.

94. T. Woerz, J. Hagenauer. Iterative decoding for multilevel codes using reliability information. In Proceedings of GLOBECOM'92, volume 3, pages 1779-1784, December 1992.

95. G. Miller, D. Burshtein. Bounds on the maximum likelihood decoding error probability of low density parity check codes. IEEE Trans. Inform. Theory, 47:2696-2710, Nov. 2001.

96. D. J. C. MacKay, S. T. Wilson,, M. C Davey. Comparison of constructions of irregular Gallager codes, in Proc. 36th Allerton Conf Communication, Control, and Computing, Sept. 1998.

97. Y. Mao, A. H. Banihashemi. Decoding low-density parity-check codes with robabilistic scheduling. IEEE Commmunications Letters, 5:414-416, Oct. 001.

98. U, Wachsmann, R. F. H. Fischer,, J. Huber. Multilevel codes: Theoretical concepts and practical design rules. IEEE Transactions On Information Theory, 45(5): 1361-1391, July 1999.

99. W. Zhang, J. Wolf. A Class of Binary Burst Error-Correcting Quasi-Cyclic Codes. IEEE Transactions on Information Theory, IT-34:463-479, May 1988.

100. Гринченко H.H., Золотарев B.B., Овечкин Г.В., Овечкин П.В. Применение многопорогового декодера в каналах со стираниями // труды 61-й научной сессии, посвященной Дню радио. М.: 2006.

101. Б.Скляр Цифровая связь. Теоретические основы и практическое применение. // Москва, Санкт-Петербург, Киев: Вильяме, 2003.

102. L. Ping, W. К. Leung. Decoding low density parity check codes with finite quantization bits. IEEE Commun. Lett, 4:62-64, Feb. 2000.

103. E. A. Ratzer. Low-density parity-check codes on Markov channels. In Second IMA Conference on Mathematics in Communications, Dec. 2002.

104. S. Reiger. Codes for the Correction of "clustered" Errors. IRE Trans. Inform. Theory, IT-6:16-21, May 1960.109.110. 111] [112]

105. T. Tian, C. Jones, J. Villasenor,, R, Wesel. Construction of Irregular LDPC Codes with Low Error Floors. In Proceedings of ICC2003.

106. T. J. Richardson, R. L. Urbanke. The Capacity of low-Density Parity-Check Codes Under Message-Passing Decoding. IEEE Transactions on Information Theory, 47(2), Feb. 2001.

107. M. Tanner. A Recursive Approach to Low Complexity Codes. IEEE Transactions on Information Theory, IT(27):533-547, Sept. 1981.

108. M. Tanner. Minimum distance bounds by graph analysis. IEEE Trans. Inform. Theory, 47:808-821, Feb. 2001.

109. T. J. Richardson, R. L. Urbanke,, S.-Y. Chung. Analysis of Sum-Product Decoding of low-Density Parity-Check Codes Using a Gaussian Approximation. IEEE Transactions on Information Theory, 47(2), Feb.2001.