Разработка и исследование характеристик LDPC кодов для спутникового канала тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Ле Ван Шон

• Ле Ван Шон
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Ле Ван Шон

СПИСОК СОКРАЩЕНИЙ

ВВЕДЕНИЕ

ГЛАВА 1. Проблема помехоустойчивого кодирования в системах передачи информации

1.1 Основы теории помехоустойчивого кодирования

1.1.1 Задача помехоустойчивого кодирования

1.1.2 Принципы построения помехоустойчивых кодов

1.1.3 Классификация помехоустойчивых кодов

1.1.4 Основные параметры помехоустойчивых кодов

1.2 Линейные блочные коды

1.2.1 Способы задания линейных блочных кодов

1.2.2 Синдром и контроль ошибок

1.2.3 Корректирующая способность и минимальное расстояние кода

1.2.4 Вероятность ошибки декодирования

ГЛАВА 2. Коды с низкой плотностью проверок на четность. Основные алгоритмы декодирования. Оптимизированные алгоритмы декодирования32

2.1 Общие положения

2.1.1 Кодирование LDPC кодов

2.1.2 Алгоритмы декодирования LDPC кодов

2.1.3 Алгоритм декодирования с инверсией бита

2.1.4 Алгоритм декодирования сумма-произведение

2.1.5 Алгоритм декодирования минимум-сумма

2.1.6 Сравнительные характеристики различных алгоритмов декодирования LDPC кодов

2.2 Модифицированные алгоритмы декодирования, основанные на алгоритме «min-sum»

2.2.1 Алгоритм «min-sum normalized»

2.2.2 Алгоритм «min-sum offset»

2.2.3 Комбинированный алгоритм «min-sum»

2.2.4 Сравнение различных вариантов модификации алгоритма «min-sum»

ГЛАВА 3. Разработка методов получения совместимых по скорости кодов с низкой плотности проверок на четность

3.1 Проблема получения совместимых по скорости кодов в современных системах передачи данных

3.2 Общее описание известных методов получения совместимых по скорости ЬБРС кодов

3.2.1 Метод выкалывания

3.2.2 Метод расширения

3.2.3 Метод объединения и разделения строк

3.3 Разработанные методы получения совместимых по скорости ЬБРС кодов

3.3.1 Классификация разработанных методов дублирования бит

3.3.2 Метод внутреннего дублирования бит

3.3.3 Метод внешнего дублирования бит

3.3.4 Комбинированный метод дублирования бит

3.3.5 Сравнение вычислительной сложности разработанных методов

3.4 Модификации разработанных методов получения совместимых по скорости ЬБРС кодов

3.4.1 Зависимость эффективности кода от плотности распределения единичных элементов в проверочной матрице

3.4.2 Многократное дублирование бит

3.5 Результаты моделирования

3.5.1 Сравнение методов внутреннего и внешнего дублирования бит с методом выкалывания информационных бит

3.5.2 Сравнение комбинированного метода с методами внутреннего и внешнего дублирования бит

3.5.3 Исследование влияния плотности распределения единичных элементов в проверочной матрице и многократности при дублировании на эффективность кода

3.5.4 Проблема разработки базовой проверочной матрицы для методов дублирования бит

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

Приложение

Приложение

Приложение

Приложение

Приложение

Приложение

СПИСОК СОКРАЩЕНИЙ

LDPC - код с низкой плотностью проверок на чётность (low-density parity-check code)

R - скорость передачи данных

Q - пропускная способность канала связи

Рег - средняя вероятность ошибки

Per,max - максимальная вероятность ошибки

L - длина блока

AF - полоса частот канала

Рс - мощность сигнала

Рш - мощность шума

п - длина кода

к - количество информационных символов в кодовом слове

т - количество проверочных символов в кодовом слове

г - скорость кодирования

Rc - коэффициент избыточности кода

М - мощность кода

w - вес кодовой комбинации

d - кодовое расстояние

d-min - расстояние Хэмминга

t0 - кратность обнаруживаемых ошибок

tu - кратность исправляемых ошибок

q - основание кода

С - кодовое слово

G - порождающая матрица

Р - матрица четности

I - единичная матрица

Н - проверочная матрица

р - вероятностью ошибки в двоичном симметричном канале связи е - вектор ошибок S - синдром

V - принятая кодовая комбинация

Ри(е) - вероятность необнаруживаемой ошибки

Pd (е) - вероятность обнаруживаемой ошибки

Aj - количество кодовых комбинаций с весовым коэффициентом j

BER - вероятность битовой ошибки (bit error rate)

SNR - отношение сигнал-шум (signal-to-noise ratio)

dr - количество единичных элементов в каждой строке проверочной матрицы dc - количество единичных элементов в каждом столбце проверочной матрицы Ci - битовой узел i lj - проверочный узел j

LLR - логарифмическое отношение правдоподобия (log-likelihood ratio)

АБГШ - аддитивный белый гауссовский шум

BPSK - двоичная фазовая манипуляция (binary phase shift keying)

QPSK - квадратурная фазовая манипуляция (quadrature phase shift keying)

Eb /N0 - отношение энергии бита к спектральной плотности мощности шума

а - коэффициент нормализации

ß - коэффициент сдвига

PIB - метод выкалывания информационных бит

MUX - мультиплексор

DMUX - демультиплексор

PCB - метод выкалывания контрольных бит

k-SR - узел восстанавливаемый за fc-шагов

PEG - алгоритм последовательного добавления ребер

г0 - скорость материнского кода

HRSEV - алгоритм иерархического разделения строк с изменением ребер IBD - метод внутреннего дублирования бит

IBD* - улучшенная версия метода внутреннего дублирования бит

IBD** - улучшенная версия метода внешнего дублирования бит с учётом

изменения структуры проверочной матрицы

11 - длина исходного сообщения

10 - длина последовательности нулей

1а - общая длина дублированной части

EBD - метод внешнего дублирования бит

EBD* - улучшенная версия метода внешнего дублирования бит

EBD** - улучшенная версия метода внешнего дублирования бит с учётом

изменения структуры проверочной матрицы

CBD - комбинированный метод дублирования бит

CBD* - улучшенная версия комбинированного метода дублирования бит

CBD** - улучшенная версия комбинированного метода дублирования бит с

учётом изменения структуры проверочной матрицы

1й. - длина внутренней дублированной части

1йе - длина внешней дублированной части

^сво - сложность комбинированного метода дублирования бит

- сложность метода внутреннего дублирования бит ^ево - сложность метода внешнего дублирования бит

Введение диссертации (часть автореферата) на тему «Разработка и исследование характеристик LDPC кодов для спутникового канала»

ВВЕДЕНИЕ

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

LDPC коды впервые были представлены американским учёным Робертом Галлагером в 1963 году. Но в то время мощности вычислительных средств были достаточно низкими, поэтому потенциал LDPC кодов не был полностью раскрыт. Только спустя почти 35 лет благодаря своим уникальным возможностям данные коды вновь привлекли внимание исследователей в области помехоустойчивого кодирования. На данный момент существуют различные методы синтеза LDPC кодов, которые позволяют максимально приблизиться к пределу Шеннона, благодаря чему они стали частью многих стандартов. Например, LDPC коды были использованы в многих современных стандартах передачи данных (IEEE 802.3, IEEE 802.11, IEEE 802.16), а также стандартах цифрового телевещания (DVB-S2, DVB-T2, DVB-C2, DTMB и ATSC 3.0) и других.

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

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

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

Степень разработанности темы. В направлении исследования, разработки и оптимизации различных алгоритмов декодирования LDPC кодов можно отметить труды следующих авторов: Башкирова А.В., Зигангирова Д.К., Зяблова В.В., Овечкина Г.В., Roberts M. K., Gunnam K., Johnson S. J., Fossorier M., Lin S., Savin V. В данной диссертации предложен один метод оптимизации алгоритм «min-sum» для регулярного LDPC кода, результаты исследования которого были получены в среде моделировании Matlab с помощью статистического метода анализа данных.

В направлении исследования и разработки методов совместимости по скорости кодирования LDPC кодов следует отметить труды таких авторов, как Wei Y., Tian T., Ha J., Kim D., Kim J., Asvadi R., Xiao M., Zhou L., Deka K., Choi E., Chu T., Casado A.I.V., Zhao P., Hu X.Y., Yazdani M., Li Z., Jacobsen N., Li J., Liu Z.

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

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

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

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

2. Исследование существующих алгоритмов декодирования ЬЭРС кодов.

3. Разработка нового алгоритма декодирования ЬЭРС кодов.

4. Оценка вычислительной сложности алгоритмов декодирования ЬЭРС кодов.

5. Анализ и исследование существующих методов получения совместимых по скорости кодирования ЬЭРС кодов.

6. Разработка новых методов получения совместимых по скорости кодирования ЬЭРС кодов.

7. Разработка способов для улучшения предложенных методов получения совместимых по скорости кодирования ЬЭРС кодов.

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

Методология и методы исследования. Для решения вышепредставленных задач использованы следующие методы:

• теории кодирования;

• теории цифровой обработки сигналов;

• теории блоковых кодов;

• теории алгоритмов;

• теории вероятностей и математической статистики;

• математической логики;

• вычислительной математики;

• моделирования и программирования.

Научная новизна. Научная новизна диссертации состоит в следующем:

1. Предложен комбинированный метод для оптимизации алгоритма декодирования «минимум-сумма» LDPC кодов.

2. Предложены методы получения совместимых по скорости кодирования LDPC кодов.

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

4. Разработаны комплексные программы для оценки и исследования предложенных методов.

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

Теоретическая значимость. Теоретическая значимость работы заключается в разработке новых алгоритмов и методов для исследования характеристик LDPC кодов.

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

Основные положения, выносимые на защиту:

1. Модификация алгоритма декодирования «минимум-сумма» на 0.1-0.2 дБ превосходящая алгоритм «минимум-сумма» во всем диапазоне отношений сигнал-шум.

2. Метод дублирования бит для получения совместимых по скорости кодирования ЬЭРС кодов (ШЭ, ЕВЭ и СВЭ). В различных модификациях позволяющий получить выигрыш по сравнению с методом выкалывания бит на 0.1-0.5 дБ для скоростей кодирования от 1/4 до 2/5.

3. Модификация предложенного метода дублирования бит - метод многократного дублирования бит, опирающийся на плотность распределения единичных элементов в проверочной матрице, дающий выигрыш по сравнению с исходным методом на 0.07-0.13 дБ для скорости кодирования 1/4.

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

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

1. 63-я Всероссийская научная конференция МФТИ (МФТИ, г. Москва, 2020

г).

2. VII Международная конференция «Инжиниринг & Телекоммуникации Еп&Т 2020» (МФТИ, г. Москва, 2020 г).

3. 14-я Всероссийская конференция «Радиолокация и радиосвязь» (ИРЭ им. В.А. Котельникова РАН, г. Москва, 2020 г).

4. Международная научно-практическая конференция «Информационные технологии и интеллектуальные системы принятия решений» (РосНОУ, г. Москва, 2021 г).

5. XV Международная отраслевая научно-техническая конференция «технологии информационного общества» (МТУСИ, г. Москва, 2021 г).

6. XXIII Международная конференция «Цифровая обработка сигналов и ее применение - DSPA-2021» (ИПУ РАН, г. Москва, 2021 г).

7. XCIII Международная научно-практическая конференция «Инновационные подходы в рамках естественных и технических наук: современные реалии и перспективы развития» (ОНТ, г. Казань, 2021 г).

Публикация. Основные результаты, полученные в ходе выполнения диссертационной работы, были опубликованы в 8 научных работах, из них 1 статья была опубликована в научном журнале, входящем в перечень ВАК, 3 статьи опубликованы в изданиях, индексируемых в международной безе цитирования SCOPUS.

Объём и структура диссертации. Диссертация состоит из введения, трёх глав, заключения и шести приложений. Общий объём диссертации составляет 135 страниц, в том числе 63 рисунка и 7 таблиц. Список литературы содержит 100 наименований.

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

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

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

Во второй главе исследованы два подхода к декодированию LDPC кодов -декодирование с «жёстким» решением (например, алгоритм «bit-flip») и декодирование с «мягким» решением (например, алгоритмы «sum-product» и «min-sum»). При исследовании методов оптимизации алгоритма «min-sum» предложен комбинированный вариант, исходящий из существующих оптимизированных алгоритмов «min-sum normalized» и «min-sum offset». А также приведены сравнительный анализ и расчёт вычислительной сложности различных алгоритмов декодирования.

В третьей главе изложены основные идеи диссертационной работы. В ней описаны распространённые методы получения совместимых по скорости кодирования LDPC кодов такие, как выкалывание, расширение, объединение и разделение строк. В результате анализа и исследования данных методов предложены три метода получения совместимых по скорости LDPC кодов: дублирование бит - внутреннее, внешнее и комбинированное дублирование. Для улучшения эффективности предложенных методов разработаны различные принципы и способы, связанные с плотностью распределения единичных элементов в проверочной матрице материнского кода. А также приведены результаты исследования в среде моделирования Matlab для оценки эффективности разработанных методов и из модификаций.

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

ГЛАВА 1. Проблема помехоустойчивого кодирования в системах передачи информации

1.1 Основы теории помехоустойчивого кодирования

1.1.1 Задача помехоустойчивого кодирования

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

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

1.1.2 Принципы построения помехоустойчивых кодов

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

с этим в общую систему связи включаются дополнительные устройства - кодер канала и декодер канала.

На рисунке 1.1 показана обобщенная структурная схема цифровой системы связи, использующей помехоустойчивое кодирование [5].

Шум

Рисунок 1.1 - Обобщенная структурная схема цифровой системы связи

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

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

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

рассматривать как сумму передаваемого сигнала и шума, действующего в канале связи ut = st + nt, где nt - это шумовой вектор. Принятый сигнал поступает в демодулятор для преобразования его в последовательность символов одного из кодовых слов zt. Но из-за шума в канале связи демодулятор не будет работать правильно, то есть полученное кодовое слово будет искажаться.

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

Современные теории кодирования информации базируются на некоторых фундаментальных теоремах, одной из которых является теорема американского ученого К. Шеннона, предложенная им в 1948г [2,6,7]. Данная теорема гласит, что если скорость передачи сообщения (R) не превосходит величину пропускной способности канала связи Q, то есть R < Q, то существуют такие коды, что средняя и максимальная вероятности ошибки (Per, Perimax) при декодировании блока стремятся к нулю по мере увеличения длины блока (п) к бесконечности, то есть Per ^ 0, Per,max ^ 0 при п ^ ю. Иными славами, для канала с шумами всегда существуют помехоустойчивые коды с их методами декодирования, с помощью которых сообщения могут быть переданы со сколь угодно большой достоверностью, при условии, что производительность источника информации не должна превышать пропускной способности канала [8]. Пропускная способность канала может определяться по следующей формуле [7]:

(1.1)

где

• АР - полоса частот канала, Гц;

• Рс - мощность сигнала, Вт;

• Рш - мощность шума, Вт.

В литературе формула (1.1) имеет название «предел Шеннона».

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

1.1.3 Классификация помехоустойчивых кодов

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

Рисунок 1.2 - Классификация помехоустойчивых кодов по структуре кода

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

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

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

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

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

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

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

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

Рисунок 1.3 - Структурная схема системы связи с использованием двухкаскадного кодирования

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

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

В некаскадных кодах используется лишь одноступенчатое кодирование и декодирование.

1.1.4 Основные параметры помехоустойчивых кодов

Помехоустойчивые коды характеризуются следующими параметрами [1]:

• Длина кода (п);

• Количество информационных символов в кодовом слове (к);

• Количество проверочных символов в кодовом слове (т = п — к);

• Скорость кодирования (г);

• Коэффициент избыточности кода (Яс = 1 — г);

• Мощность кода (М);

• Вес кодовой комбинации

• Кодовое расстояние (й);

• Расстояние Хэмминга )

• Кратность обнаруживаемых ошибок (¿0);

• Кратность исправляемых ошибок (^);

Длина кода (п) - это общее количество символов в кодовой комбинации, которая включает в себя информационные (к) и проверочные символы (т).

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

к

г = ~. (1.2)

п

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

т п — к к

Яс=- =-=1--. (1.3)

п п п

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

Мощность кода (М) - количество разрешённых кодовых комбинаций (М =

21

qk). Соотношение мощности кода к общему количеству кодовых комбинаций (N = qn) выражается следующей формулой:

М _qk _ qk _ 1

~N =q™ = qm+k = q™' ( ' )

Общее количество единиц в кодовой комбинации называется ее весом (w).

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

d(Ai,Aj) = w(Ai®Aj)' (1.5)

Наименьшее расстояние между любыми двумя разрешёнными кодовыми комбинациями называется кодовым расстоянием (d) или расстоянием Хэмминга

(Amin ).

dmin = mind(Ai,Aj) = minw^At 0 Aj). (1.6)

1Ф] 4 1Ф] 4

Минимальное расстояние Хэмминга является главным параметром, определяющим способность обнаружения и исправления ошибок кода. Кратность обнаруживаемых ошибок (t0) и кратность исправляемых ошибок (tu) связаны с расстоянием Хэмминга по следующим формулам [1,7]:

dmin >to + 1, (17)

dmin > 2tu + 1, (1.8) d-min > ^0 + tu + 1 (при to > tu). (1.9)

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

кода.

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

информационных символов (к). Наиболее важными являются граница Хэмминга, граница Плоткина и граница Гилберта. Эти границы построены для выяснения того, насколько полученные коды близки к оптимальным.

Граница Хэмминга, используемая для оценки высокоскоростных кодов, определяется следующим соотношением [2,9]: • В случае двоичного кода

п-к> ^2

1=0

(1.10)

• В случае недвоичного кода

п-к>

1=0

(1.11)

Границу Плоткина, целесообразно использовать для низкоскоростных кодов, она выражается следующим соотношением [2]: • В случае двоичного кода

п • 2к-1 ¿тт — 2к -1

(1.12)

• В случае недвоичного кода

—

п •&-!)• як-1 дк-1

(1.13)

Граница Гилберта определяется следующим соотношением [2,10]: • В случае двоичного кода

г

и

г

и

2п-к> £ С^^ (1.14)

1=0

• В случае недвоичного кода

&тт-2

Яп-к > £ Си^Ч-Ъ1. (1.15)

1 = 0

1.2 Линейные блочные коды

Код (п, к) называют линейным блочным кодом, представляющим собой множество N = 2к последовательностей длины п, образующих ^-мерное подпространство п-мерного векторного пространства над двоичным полем СР(2) [11-13]. Особенность данного кода заключается в том, что сумма по модулю 2 любых двух кодовых слов и произведения любого кодового слова на элемент поля также являются кодовыми словами. В двоичном поле использованы две операции: сложение и умножение, которые производятся по правилам для алгебраического поля (таблица 1.1) [14].

Таблица 1. 1 Правила двоичной арифметики

а Ь а © Ь а • Ь

0 0 0 0

0 1 1 0

1 0 1 0

1 1 0 1

1.2.1 Способы задания линейных блочных кодов

Любой нужный вектор С линейного блочного кода можно получить из набора

к линейно независимых кодовых комбинаций, называемых базисом У2,..., Ук).

Таким образом, вектор С можно представить в следующем виде [11]:

24

С = + П2^2 + ■■■ + икУк ,

(1.16)

где щ Е {0,1}, I = 1,..., к.

Базисные кодовые комбинации представлены в виде (к х п)-матрицы, так порождающей матрицы:

'"1,1 "1,2

в = У2 = V2,1 V2,2

Ук. -Ук,1 Ук,2

VI,и

у3,к

-

(1.17)

Следовательно, генерируемое из сообщения и = (и1,и2, ..,ик) кодовое слово С может быть записано следующим образом:

Список литературы диссертационного исследования кандидат наук Ле Ван Шон, 2021 год

СПИСОК ЛИТЕРАТУРЫ

1. Березюк Н. Т., Андрющенко А. Г. Кодирование информации: Двоичные коды: справочник. - «Вища школа», 1978. - 252 с.

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

3. Муттер В. В. Основы помехоустойчивой телепередачи информации. - Л.: Энергоиздат, 1990.

4. Лидовский В.В. Теория информации. Учебное пособие. - М.: Компания Спутник+, 2004.

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

6. Дворкович В. П., Дворкович А.В. Цифровые видеоинформационные системы (теория и практика). М.: Техносфера. - 2012. - 1008 с.

7. Солтанов А. Г. Защита информации от угроз нарушения целостности в высокоскоростных каналах передачи данных: дис. ... канд. тех. наук: 05.13.19/ Солтанов Андрей Георгиевич. - М., 2011. - 110 с.

8. Королев А. И. Коды и устройства помехоустойчивого кодирования. - Мн.: ООО «Норд», 2002.

9. Касами Т. и др. Теория кодирования: Пер. с япон. - М: Мир, - 1978. - 586 с.

10.Витерби А., Омура Дж. К. Принципы цифровой связи и кодирования. - М.: Радио и связь, 1982.

11.Скляр Б. Цифровая связь: Теоретические основы и практическое применение. Изд. 2-е, испр: пер. с англ. - М.: Издательский дом «Вильямс», - 2003. - 1104 с.

12.Котоусов А. С. Теоретические основы радиосистем. Радиосвязь, радиолокация, радионавигация. - М.: Радио и связь, 2002. - 224 с.

13.Липкин И. А. Статистическая радиотехника. Теория информации и кодирования. - М.: "Вузовская книга", 2002. - 216 с.

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

15.Вернер М. Основы кодирования: Учебник для вузов: Пер. с нем //ДК Зигангиров. М.: Техносфера. - 2004. - 288 с.

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

17.Лихобабин Е.А. Исследование быстрых алгоритмов декодирования кодов с низкой плотностью проверок на четность // Труды РНТОРЕС имени А.С.Попова. Серия: Цифровая обработка сигналов и ее применения. М. - 2009. - № XI-1 - С. 55-59.

18.Gallager R. G. Low-Density Party-Check Codes // Monograph, M.I.T. Press. -1963.

19.Зубарев Ю. Б., Овечкин Г. В. Помехоустойчивое кодирование в цифровых

системах передачи данных //Электросвязь. - 2008. - №. 12. - С. 58-61.

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

21. Кирьянов И. А. Исследование статистических характеристик декодирования низкоплотностных кодов //Информационно-измерительные и управляющие системы. - 2012. - Т. 10. - №. 10. - С. 20-25.

22.Астахов Н. В. и др. Верификация LDPC-кодов // Вестник Воронежского государственного технического университета. - 2017. - Т. 13. - №2. 1. - С. 74-77.

23.Коротков Л. Н., Башкиров А. В., Свиридова И. В. Использование LDPC-кодов // Вестник Воронежского государственного технического университета. - 2013. -Т. 9. - №. 6-3.

24.Valenti M. C., Cheng S., Seshadri R. I. Turbo and LDPC codes for digital video broadcasting //Turbo Code Applications. - Springer, Dordrecht. - 2005. - С. 301-319.

25.Быков В. В., Меньшиков К. В. Помехоустойчивые коды цифрового телевидения // T-Comm-Телекоммуникации и Транспорт. - 2013. - №. 9. - С. 30-33.

26.Кравченко А.Н. Снижение сложности декодирования низкоплотностного кода // Цифровая обработка сигналов. - 2010. - №. 2. - С. 35-41.

27.Leiner B. M. J. LDPC Codes-a brief Tutorial //Apr. - 2005. - Т. 8. - С. 1-9.

28.Владимиров С. М. Использование кодов с малой плотностью проверок на чётность //Труды. - 2007. - С. 4-7.

29.Астахов Н. В. и др. Верификация LDPC-кодов // Вестник Воронежского государственного технического университета. - 2017. - Т. 13. - №2. 1. - С. 74-77.

30.Лихобабин Е.А., Упрощенные алгоритмы декодирования кодов с низкой плотностью проверок на четность, основанные на алгоритме распространения доверия // Цифровая обработка сигналов. - 2013. - №. 3. - С. 54-60.

31.Ardakani M. Efficient analysis, design and decoding of low-density parity-check codes. - University of Toronto. - 2004.

32.Новиков Р. С., Астраханцев А. А. Выбор параметров LDPC кодов для каналов с АБГШ // Системы обработки информации. - 2014. - №. 1. - С. 195-199.

33.Коротков Л. Н., Башкиров А. В., Свиридова И. В. Использование LDPC-кодов // Вестник Воронежского государственного технического университета. - 2013. -Т. 9. - №. 6-3.

34.Башкиров А. В., Свиридова И. В., Муратов А. В. Эффективное многопороговое декодирование недвоичных кодов с предварительной оценкой ошибочности проверок //Вестник Воронежского государственного технического университета. - 2015. - Т. 11. - №. 3.

35.Коротков Л. Н., Свиридова И. В. Алгоритмы декодирования двоичных кодов с малой плотностью проверок на четность с жестким входом // Вестник Воронежского государственного технического университета. - 2015. - Т. 11. -№. 6. - С. 108-111.

36.El Alami R. et al. Bit flipping-sum product algorithm for regular LDPC codes //2010 5th International Symposium On I/V Communications and Mobile Network. - IEEE. - 2010. - С. 1-4.

37.Кирьянов И.А. Моделирование работы LDPC-декодера по алгоритму с распространением доверия по надежностям // Информационные технологии в проектировании и производстве, изд. ФГУП ВИМИ. - 2012. -№. 4. - С. 57-60.

38.Кирьянов И.А. Моделирование работы LDPC-декодера по алгоритму с распространением доверия по надёжностям // Сборник докладов 1-ой межвузовской студенческой научно-технической конференции «Современные

состояния и перспективы развития сложных радиоэлектронных систем», изд. ОАО «ГСКБ Алмаз-Антей», М.: - 2012. - С. 16-22.

39.Niu H. et al. Iterative channel estimation and LDPC decoding over flat-fading channels: A factor graph approach //Proc. Conf. Inf. Sci. Syst.(CISS). - 2003.

40.Fossorier M. P. C., Mihaljevic M., Imai H. Reduced complexity iterative decoding of low-density parity check codes based on belief propagation //IEEE Transactions on communications. - 1999. - Т. 47. - №. 5. - С. 673-680.

41.Richardson T. J., Urbanke R. L. The capacity of low-density parity-check codes under message-passing decoding //IEEE Transactions on information theory. - 2001. - Т. 47. - №. 2. - С. 599-618.

42.Важенин Н. А., Кирьянов И. А. Оценка статистических характеристик функционирования LDPC-декодера на имитационной модели [Электронный ресурс] // Электронный журнал «Труды МАИ». - 2012. - № 59. http: //www. mai. ru/science/trudy/published.php.

43.Лихобабин Е. А. Методы и алгоритмы декодирования кодов с низкой плотностью проверок на четкость: дис. ... канд. тех. наук: 05.12.04 // Лихобабин Евгений Александрович. - Рязань. - 2015. - 164 с.

44. Овинников А. А. Алгоритмы анализа и синтеза помехоустойчивых низкоплотностных кодов в системах телерадиовещения: дис. ... канд. тех. наук: 05.12.04 // Овинников Алексей Анатольевич. - Рязань. - 2017. - 179 с.

45. Лихобабин Е.А., Дворкович А.В. Использование квазиоптимальных алгоритмов декодирования LDPC кодов в системе цифрового телевизионного вещания стандарта DVB-T2 // Труды РНТОРЕС имени А.С.Попова. Серия: Цифровая обработка сигналов и ее применения. М. - 2010. - № XI-1 - С. 25-27.

46.Santini P. et al. Analysis of the error correction capability of LDPC and MDPC codes under parallel bit-flipping decoding and application to cryptography //IEEE Transactions on Communications. - 2020. - Т. 68. - №. 8. - С. 4648-4660.

47.Ismail M. et al. Low latency low power bit flipping algorithms for LDPC decoding //21st Annual IEEE International Symposium on Personal, Indoor and Mobile Radio

Communications. - IEEE. - 2010. - С. 278-282.

108

48.Jiang M. et al. An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes //IEEE Communications Letters. - 2005. - Т. 9. - №. 9. -С. 814-816.

49.Zhou X. S., Cockburn B. F., Bates S. Improved iterative bit flipping decoding algorithms for LDPC convolutional codes //2007 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing. - IEEE. - 2007. - С. 541-544.

50.Zhang J., Fossorier M. P. C. A modified weighted bit-flipping decoding of low-density parity-check codes //IEEE Communications Letters. - 2004. - Т. 8. - №. 3. - С. 165167.

51.Wu X., Ling C., Jiang M., Xu E., Zhao C., You X. Towards Understanding Weighting Bit-Flipping Decoding // Information Theory, IEEE International Symposium on, Nice. - 2007. - С. 1666-1670.

52. Ле Ш.В., Лихобабин Е.А. Исследование итеративных алгоритмов декодирования кодов с низкой плотностью проверок на чётность // 14-я Всероссийская конференция «Радиолокация и радиосвязь». Сборник трудов. -Москва.: ИРЭ им. В.А. Котельникова РАН. - 2020. - С. 31-35.

53.Кирьянов И. А. Декодирование кодов с малой плотностью проверок на четность: дис. ... канд. тех. наук: 05.12.13// Кирьянов Иван Андреевич. - М. - 2015. - 129 с.

54. Ле Ш.В. Оптимизация алгоритма декодирования min-sum для кодов с низкой плотностью проверок на четность // Труды МФТИ. - 2021. - Т.13. - №2.1. - С. 1623.

55.Hu X. Y. et al. Efficient implementations of the sum-product algorithm for decoding LDPC codes //GLOBECOM'01. IEEE Global Telecommunications Conference (Cat. No. 01CH37270). - IEEE, 2001. - Т. 2. - С. 1036-1036.

56.Chen J., Fossorier M. P. C. Density evolution for two improved BP-based decoding algorithms of LDPC codes //IEEE communications letters. - 2002. - Т. 6. - №. 5. -С. 208-210.

57.Zhang H., Yuan D., Wang C. X. An improved normalized BP based decoding algorithm for LDPC codes //IET 2nd international conference on wireless, mobile and multimedia networks (ICWMMN 2008). - IET, 2008. - С. 223-226.

58.Chung S. Y., Richardson T. J., Urbanke R. L. Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation //IEEE Transactions on Information theory. - 2001. - Т. 47. - №. 2. - С. 657-670.

59.Hagenauer J., Offer E., Papke L. Iterative decoding of binary block and convolutional codes //IEEE Transactions on information theory. - 1996. - Т. 42. - №. 2. - С. 429445.

60.Johnson S. J. Introducing low-density parity-check codes //University of Newcastle, Australia. - 2006. - Т. 1. - С. 2006.

61.Roberts M. K. Combined Normalized and Offet Min-Sum Decoding Algorithm for Irregular LDPC Codes //National Conference on Networking, Embedded and Wireless Systems (NEWS-2016), BMS College of Engineering, Bangalore, INDIA. - 2016. -С. 30-33.

62.Gunnam K., Choi G. A low power architecture for min-sum decoding of ldpc codes //TAMU, ECE Technical Report, May. - 2006.

63.Хлынов А. А. Исследование итеративных алгоритмов декодирования кодов с низкой плотностью проверок на четность // Труды МФТИ. - 2016. - Т.8, № 4. -С. 13-17.

64.Islam M. R., Shafillah D. S., Faisal M. M. A., Rahman I. Optimized min-sum decoding algorithm for low density parity check codes //International Journal of Advanced Computer Science and Applications. - 2011. - Т. 2. - №.12. - P. 168-174.

65.Башкиров А. В., Хорошайлова М. В., Борисов В. И. Реализации LDPC декодера низкой сложности с использованием алгоритма Min-sum Борисов // Вестник Воронежского государственного технического университета. -2016. - №5. -Воронеж. - С. 82-86.

66.Овечкин Г.В.Применение Min-sum алгоритма для декодирования блоковых самоортагональных кодов // Межвуз. сб. науч. тр. «Математическое и

программное обеспечение вычислительных систем» - Москва, Горячая линия -Телеком. - 2010. С. 99-105.

67.Zhao J., Zarkeshvari F., Banihashemi A. H. On implementation of min-sum algorithm and its modifications for decoding low-density parity-check (LDPC) codes //IEEE transactions on communications. - 2005. - Т. 53. - №. 4. - С. 549-554.

68.Zhong Z. et al. Modified min-sum decoding algorithm for LDPC codes based on classified correction //2008 Third International Conference on Communications and Networking in China. - IEEE. - 2008. - С. 932-936.

69.Витязев В. В., Лихобабин Е. А. Алгоритмы декодирования кодов с низкой плотностью проверок на четность, основанные на структуре алгоритма" минимум-сумма" //Успехи современной радиоэлектроники. - 2014. - №. 6. - С. 26-35.

70.Zhang J., Fossorier M., Gu D. Two-dimensional correction for min-sum decoding of irregular LDPC codes //IEEE Communications Letters. - 2006. - Т. 10. - №. 3. - С. 180-182.

71.Savin V. Self-corrected min-sum decoding of LDPC codes // IEEE International symposium on Information Theory. - 2008. - pp. 146-150.

72.Vityazev V. V., Likhobabin E. A., Ustinova E. A. Min-sum algorithm-structure based decoding algorithms for LDPC codes //2014 3rd Mediterranean Conference on Embedded Computing (MECO). - IEEE. - 2014. - С. 256-259.

73.MacKay D. J. C. Encyclopedia of Sparse Graph Codes, http://www.inference.org.uk/mackay/codes/data.html. - 2014.

74.Jiang M. et al. Adaptive offset min-sum algorithm for low-density parity check codes //IEEE communications letters. - 2006. - Т. 10. - №. 6. - С. 483-485.

75.Wei Y. et al. Joint shortening and puncturing optimization for structured LDPC codes //IEEE communications letters. - 2012. - Т. 16. - №. 12. - С. 2060-2063.

76.Tian T., Jones C. R. Construction of rate-compatible LDPC codes utilizing information shortening and parity puncturing //EURASIP Journal on wireless communications and networking. - 2005. - Т. 2005. - №. 5. - С. 1-7.

77.Ha J., Kim J., McLaughlin S. W. Rate-compatible puncturing of low-density parity-check codes //IEEE Transactions on information Theory. - 2004. - T. 50. - №. 11. -C. 2824-2836.

78.Ha J. et al. Rate-compatible punctured low-density parity-check codes with short block lengths //IEEE Transactions on Information Theory. - 2006. - T. 52. - №. 2. -C. 728-738.

79.Kim D. Hybrid-ARQ with rate compatible LDPC codes //International Conference on Hybrid Information Technology. - Springer, Berlin, Heidelberg, 2012. - C. 25-32.

80.Kim J., Ramamoorthy A., McLaughlin S. W. The design of efficiently-encodable rate-compatible LDPC codes-[transactions papers] //IEEE transactions on communications. - 2009. - T. 57. - №. 2. - C. 365-375.

81.Asvadi R., Banihashemi A. H. A rate-compatible puncturing scheme for finite-length LDPC codes //IEEE communications letters. - 2012. - T. 17. - №. 1. - C. 147-150.

82.Xiao M. Design of finite-length rate-compatible LDPC codes //2015 IEEE International Conference on Communication Software and Networks (ICCSN). -IEEE, 2015. - C. 232-235.

83.Zhou L. et al. A non-greedy puncturing method for rate-compatible LDPC codes //Journal of Communications and Networks. - 2017. - T. 19. - №. 1. - C. 32-40.

84.Deka K., Rajesh A., Bora P. K. An improved puncturing method for rate-compatible LDPC codes //2014 Twentieth National Conference on Communications (NCC). -IEEE, 2014. - C. 1-6.

85.Choi E., Suh S. B., Kim J. Rate-compatible puncturing for low-density parity-check codes with dual-diagonal parity structure //2005 IEEE 16th International Symposium on Personal, Indoor and Mobile Radio Communications. - IEEE, 2005. - T. 4. - C. 2642-2646.

86.Hu X. Y., Eleftheriou E., Arnold D. M. Progressive edge-growth Tanner graphs //GLOBECOM'01. IEEE Global Telecommunications Conference (Cat. No. 01CH37270). - IEEE, 2001. - T. 2. - C. 995-1001.

87.Yazdani M., Banihashemi A. H. On construction of rate-compatible low-density parity-check codes //2004 IEEE International Conference on Communications (IEEE Cat. No. 04CH37577). - IEEE, 2004. - Т. 1. - С. 430-434.

88.Li Z., Kumar B. V. K. V. A class of good quasi-cyclic low-density parity check codes based on progressive edge growth graph //Conference Record of the Thirty-Eighth Asilomar Conference on Signals, Systems and Computers, 2004. - IEEE, 2004. - Т. 2. - С. 1990-1994.

89.Jacobsen N., Soni R. Design of rate-compatible irregular LDPC codes based on edge growth and parity splitting //2007 IEEE 66th Vehicular Technology Conference. -IEEE, 2007. - С. 1052-1056.

90.Li J., Narayanan K. Rate-compatible low density parity check codes for capacity-approaching ARQ scheme in packet data communications //Int. Conf. on Comm., Internet, and Info. Tech.(CIIT). - 2002. - С. 201-206.

91.Liu Z. et al. Rate-compatible QC-LDPC codes design based on EXIT chart analysis //2012 8th International Wireless Communications and Mobile Computing Conference (IWCMC). - IEEE, 2012. - С. 921-926.

92.Chu T. et al. Construction of multiple-rate LDPC codes using modified PEG //2017 9th International Conference on Wireless Communications and Signal Processing (WCSP). - IEEE, 2017. - С. 1-5.

93.Casado A. I. V. et al. Multiple-rate low-density parity-check codes with constant blocklength //IEEE Transactions on Communications. - 2009. - Т. 57. - №. 1. - С. 75-83.

94.Zhao P., Wang Z., Wang Q. Construction of multiple-Rate QC-LDPC codes using hierarchical row-splitting //IEEE Communications Letters. - 2016. - Т. 20. - №. 6. -С. 1068-1071.

95.Son Le., Likhobabin E.A. Design of Rate-Compatible Low-Density Parity-Check Codes with Constant Check Matrix // 7th International Conference «Engineering and Telecommunication - En&T-2020». - IEEE, 2020. - С. 1-3.

96. Ле Ш.В., Лихобабин Е.А. Исследование метода внешнего дублирования бит для

совместимых по скорости кодирования кодов с низкой плотностью проверок на

113

четность// Труды 15-й Международной отраслевой научно-технической конференции «Технология информационного общества». М.: МТУСИ, 2021. -С. 49-51.

97.Son Le., Likhobabin E.A. Improvement of the Bit Duplication Method for Rate-Compatible Low-Density Parity-Check Codes // 23th International Conference «Digital Signal Processing and Its Applications - DSPA-2021». - IEEE, 2021. - C. 1-5.

98.Ле Ш.В. Метод изменения скорости кодирования кодов с низкой плотностью проверок на четность // 63-я Всероссийская научная конференция МФТИ, М.: МФТИ. - 2020. - С. 77-78.

99. Le S.V, Likhobabin E.A. External Bit Duplication Method for Rate-Compatible LDPC Codes // International Scientific and Practical Conference «Information Technologies and Intelligent Decision Making Systems» (ITIDMS 2021). - State University of Management. - Russian Federation, Moscow, 2021.

100. Ле Ш.В. Исследование метода выкалывания информационных бит для совместимых по скорости кодирования кодов с низкой плотностью проверок на четность // Вопросы продуктивного взаимодействия в процессе обмена знаниями»: сборник научных трудов, Казань. - 2021. - С. 309-310.

ПРИЛОЖЕНИЕ

Приложение 1. Код программы для построения зависимостей вероятности битовой ошибки (BER) от отношения сигнал-шум (Eb/N0, (дБ)) для различных алгоритмов декодирования LDPC кодов

clc;

close all; clear all;

columnl = load('columnl.txt'); % загрузка проверочной матрицы H(1008*504)

column=column1';

row = load('row1.txt');

[m1 n1] = size(column);

[m2 n2] = size(row);

H=zeros(m2,n1);

for i=1:n1

for j=1:m1

H(column(j,i),i)=1;

end

end

[m n] = size(H); k=n-m;

q=100000; % количество блоков

о

%--------------------------------------------------------------------------

In ter =10;% максимальное количество итераций v=randi([0 1], k, q); % исходное сообщение for i1=1:11 EbNo(i1)=i1-1;

snr(i1)=EbNo(i1)+10*log10(1/2);

hEnc = comm.LDPCEncoder(sparse(H)); % Создание LDPC кодера

hMod =comm.BPSKModulator; % Создание модулятора

hChan = comm.AWGNChannel('EbNo',snr(i1)); % АБГШ канал

hDemod =comm.BPSKDemodulator('DecisionMethod,,,Approximate log-likelihood ratio'); % Создание демодулятора

hError = comm.ErrorRate; % Создание объекта для оценки количество ошибок

x=zeros(n,q); u=zeros(n,q); for i=1:q

x(:,i)=step(hEnc,v(:,i)); % закодированное сообщение

о

%-------------------------------------------------------------------------

y = step(hMod, x(:,i)); % модулированный сигнал %---------------------------------------------

w = step(hChan, y);% модулированный сигнал + Шум %----------------------------------------------

u 1= step(hDemod, w); % демодулированный сигнал u(:,i)=u_1; end

%-------------------------------------------------------------------------

Pri u0=zeros(n,q); for j=1:q

for i=1:n

if u(i,j)>0

Pri_u0(i,j)=0;

end

if u(i,j)<=0

Pri_u0(i,j)=1;

end

end

end

[num0,BER0(i1)] = symerr(x, Pri u0);% вероятность ошибок перед декодированием

r=zeros(n,q); % априорные отношения логарифмического правдоподобия for j=1:q

for i=1:n

r(i,j)=u(i,j); end

end

%-----------------------------------sum-product---------------------------

Pri_u1=Pri_u0; for i2=1:q inte=1;

Es=zeros(m,n); Ms=zeros(m,n); Ls=zeros(1,n);

Ls=r(:,i2); while inte<=In ter

Ms=zeros(m,n); for i=1:n

for j=1:m

if H(j,i)==1

Ms(j,i)=Ls(i)-Es(j,i); % расчёт сообщения от битовых узлов к проверочным end

end

end

Es=zeros(m,n); for j=1:m

for i=1:n

if H(j,i)==1

c=find(H(j, :)); pta=1;

for t=1:length(find(H(j, :))) if c(t)~=i

pta=pta*(tanh(Ms(j,c(t))/2)); end

end

Es(j,i)=2*atanh(pta); % рачёт сообщения от проверочных узлов к

битовым

end

end

end

r1=r(:,i2); Ls=r1'+sum(Es); for i=1:n

if Ls(i)>0

Pri_u1(i,i2)=0;

end

if Ls(i)<=0

Pri_u1(i,i2)=1;

end

end

if nnz(mod(H*Pri u1(:,i2),2))== 0 %проверка выполнения уравнений проверок на четность

inte=In_ter;

end inte=inte+1;

end end

%---------------------------min-sum---------------------------------------

Pri_u2=Pri_u0; for i2=1:q

inte=1;

Em=zeros(m,n); Mm=zeros(m,n); Lm=zeros(1,n);

Lm=r(:,i2); while inte<=In ter

Mm=zeros(m,n); for i=1:n

for j=1:m

if H(j,i)==1 Mm(j,i)=Lm(i)-Em(j,i); end

end

end

Em=zeros(m,n); for j=1:m

for i=1:n

if H(j,i)==1

c=find(H(j, :));

s=[];

sg=1;

for t=1:length(c) if c(t)~=i s(end+1)=abs(Mm(j,c(t))); sg=sg*sign(Mm(j,c(t))); end

end

Em(j,i)=sg*(min(s));

end

end

end

r1=r(:,i2); Lm=r1'+sum(Em); for i=1:n

if Lm(i)>0

Pri_u2(i,i2)=0;

end

if Lm(i)<=0

Pri_u2(i,i2)=1;

end

end

if nnz(mod(H*Pri u2(:,i2),2))== 0 %проверка выполнения уравнений проверок на четности

inte=In_ter; end

inte=inte+1;

end end

%-----------------------bit-flip--------------------------------------

M1=Pri_u0;

for i2=1:q inte=1;

E1=zeros(m,n); while inte<=In ter E1=zeros(m,n); for j=1:m

c=find(H(j, :)); e=0;

for a=1:length(c)

e=e+M1(c(a),i2);

end

for a=1:length(c)

E1(j,c(a))=mod(e,2);

end

end

sum1=zeros(1,n); for i=1:n

sum1(1,i)=length(find(E1(: ,i)));% вычислить средние количества ошибок за m проверок end

[Max,Index]=max(sum1);% выбор номер узел с наибольшим количеством ошибок M1(Index,i2)=mod(M1(Index,i2)+1,2);% инвертируется значение бит-узела с наибольшим количеством ошибок

if nnz(mod(H*M1(:,i2),2))== 0 %проверка выполнения уравнений проверок на четность

inte=In_ter; end inte=inte+1;

end end

[num1,BER1(i1)] = symerr(x, Pri u1);% расчёт вероятности ошибок после декодирования для sum-product алгоритма

[num2,BER2(i1)] = symerr(x, Pri u2);% расчёт вероятности после декодирования для min-sum алгоритма

[num3,BER3(i1)] = symerr(x, M1);% расчёт вероятности после декодирования для bitflip алгоритма end

semilogy(EbNo,BER0,'-k*',EbNo,BER1,'-rs',EbNo,BER2,'-cx',EbNo,BER3,'-b+'); % построение графика зависимости для всех алгоритмов grid on;

legend(,Без декодирования,,,Sum-Product,,,Min-Sum,,,Bit-Flip,);

ylabel('BER');

xlabel('Eb/No(dB)');

Приложение 2. Код программы для поиска оптимальных значений а и р для комбинированного алгоритма «min-sum» при Eb/N0 = 3

clc;

close all; clear all; format long;

columnl = load('column2.txt'); % загрузка проверочной матрицы H(408*204)

column=column1';

row = load('row2.txt');

[m1 n1] = size(column);

[m2 n2] = size(row);

H=zeros(m2,n1);

for i=1:n1

for j=1:m1

H(column(j,i),i)=1;

end

end

[m n] = size(H); k=n-m;

q=20000; % количество блоков %--------------------------------------------------------------------------

v=randi([0 1], k, q); % Исходное сообщение In ter =5;% максимальное количество итераций EbNo=3;

snr=EbNo+10*log10(1/2);

hEnc = comm.LDPCEncoder(sparse(H)); % Создание LDPC кодера

hMod =comm.BPSKModulator; % Создание модулятора hChan = comm.AWGNChannel('EbNo',snr); % АБГШ канал

hDemod =comm.BPSKDemodulator('DecisionMethod', 'Approximate log-likelihood ratio'); % Создание демодулятора

hError = comm.ErrorRate; % Создание объекта для оценки количество ошибок x=zeros(n,q); u=zeros(n,q); for i=1:q

x(:,i)=step(hEnc,v(:,i)); % закодированное сообщение

о

%-------------------------------------------------------------------------

y = step(hMod, x(:,i)); % модулированный сигнал %---------------------------------------------

w = step(hChan, y);% модулированный сигнал + Шум %----------------------------------------------

u 1= step(hDemod, w); % демодулированный сигнал u(:,i)=u_1; end

%-------------------------------------------------------------------------

Pri u0=zeros(n,q); for j=1:q

for i=1:n

if u(i,j)>0

Pri_u0(i,j)=0;

end

if u(i,j)<=0

Pri_u0(i,j)=1;

end end

end

[num0,BER0] = symerr(x, Pri u0);% вероятность ошибок перед декодированием

r=zeros(n,q); %априорные отношения логарифмического правдоподобия for j=1:q

for i=1:n

r(i,j)=u(i,j); end

end

%--------------------------------------Min-Sum Normalized + offset--------

for i1=1:100

alpha(i1)=0.01*i1; for j1=1:100 beta(j1)=0.01*j1; Pri u=Pri u0; for i2=1:q inte=1; E=zeros(m,n); M=zeros(m,n); while inte<=In ter

M=zeros(m,n); for i=1:n

for j=1:m

if H(j,i)==1 d=find(H(:, i)); pro=0;

for t=1:length(find(H(:,i))) pro=pro+E(d(t),i);

end

pro=pro-E(j,i);

M(j,i)=r(i,i2)+pro;

end

end

end

E=zeros(m,n); for j=1:m

for i=1:n

if H(j,i)==1

c=find(H(j, :));

s=[];

sg=1;

for t=1:length(c) if c(t)~=i s(end+1)=abs(M(j,c(t))); sg=sg*sign(M(j,c(t))); end

end

E(j,i)=sg*alpha(i1)*(max(min(s)-beta(j1),0));

end

end

end

r1=r(:,i2); L=r1'+sum(E); for i=1:n

if L(i)>0

Pri_u(i,i2)=0;

end

if L(i)<=0

Pri_u(i,i2)=1;

end

end

if nnz(mod(H*Pri u(:,i2),2))== 0 %проверка выполнения уравнений проверок на четность

inte=In_ter; end

inte=inte+1;

end end

[num,BER(i1,j1)] = symerr(x, Pri u);% вероятность ошибок после декодирования

end end

f min=min(min(BER)) [fx min,fy min]=find(BER==f min); mesh(alpha,beta,BER); grid on;

legend('Eb/No=3'); ylabel('beta'); xlabel('alpha'); zlabel('BER');

Приложение 3. Код программы для сравнения метода внутреннего дублирования бит (IBD) с методом выкалывания информационных бит (PIB) для трёх скоростей кодирования 2/5, 1/3 и 1/4

clc;

close all; clear all; format long ;

q=200000; % количество блоков In ter =50;% количество итераций

%-----------h-----------

H12=dvbs2ldpc(1/2);

[m n] = size(H12);

k=n-m;

alpha=3.6;

beta=0.2;

li=30;

%-----------------------------DVB-S2 code rate-1/2-----------------

for i1=1:li

EbNo(i1)=beta*i1-alpha; snr(i1)=EbNo(i1)+10*log10(1/2);

hEnc = comm.LDPCEncoder(sparse(H12)); % Создание LDPC кодера

hMod =comm.QPSKModulator('BitInput,,true); % Создание модулятора

hChan = comm.AWGNChannel('EbNo',snr(i1) , 'BitsPerSymbol',2); % АБГШ канал

hDemod =comm.QPSKDemodulator('BitOutput,,true,,DecisionMethod,,,Approximate log-

likelihood ratio'); % Создание демодулятора

hDec = comm.LDPCDecoder(sparse(H12)); hDec.MaximumIterationCount=In_ter; v=randi([0 1], k, q); % Исходное сообщение x=zeros(n,q); for i=1:q

x(:,i)=step(hEnc,v(:,i)); % закодированное сообщение %------------------------------------------------------

y = step(hMod, x(:,i)); % модулированный сигнал %---------------------------------------------

w = step(hChan, y);% модулированный сигнал + Шум %----------------------------------------------

z= step(hDemod, w); % демодулированный сигнал u= step(hDec, z); t12(:,i)=double(u); end

[num12,BER12(i1)] = symerr(v, t12);% вероятность ошибок после декодирования end

%--------------------------------IBD code rate-1/3-------------------

[m n]=size(H12);

k=n-m;

for i1=1:li

EbNo(i1)=beta*i1-alpha; snr(i1)=EbNo(i1)+10*log10(1/2);

hEnc = comm.LDPCEncoder(sparse(H12)); % Создание LDPC кодера hMod =comm.QPSKModulator('BitInput',true); % Создание модулятора hChan = comm.AWGNChannel('EbNo,,snr(i1) , 'BitsPerSymbol',2); % АБГШ канал hDemod =comm.QPSKDemodulator('BitOutput,,true,,DecisionMethod,,,Approximate log-likelihood ratio'); % Создание демодулятора hDec = comm.LDPCDecoder(sparse(H12)); hDec.MaximumIterationCount=In_ter; v=randi([0 1], k, q); v(k/3+1:2*k/3,1:q)=0; x=zeros(n,q); for i=1:q

x(:,i)=step(hEnc,v(:,i)); % закодированное сообщение

x(k/3+1:2*k/3,i)=x(1:k/3,i); %----------------------------------------------------

y = step(hMod, x(:,i)); % модулированный сигнал %---------------------------------------------

w = step(hChan, y);% модулированный сигнал + Шум %----------------------------------------------

z= step(hDemod, w); % демодулированный сигнал zr=z;

zr(1:k/3)=zr(1:k/3)+zr(k/3+1:2*k/3); zr(k/3+1:2*k/3)=inf; u= step(hDec, zr); tm13(:,i)=double(u);

end

[numm13,BERm13(i1)] = symerr(v, tm13);% вероятность ошибок после декодирования end

%--------------------------------IBD code rate-1/4-----------------

[m n]=size(H12); k=n-m; for i1=1:li

EbNo(i1)=beta*i1-alpha; snr(i1)=EbNo(i1)+10*log10(1/2);

hEnc = comm.LDPCEncoder(sparse(H12)); % Создание LDPC кодера hMod =comm.QPSKModulator('BitInput',true); % Создание модулятора hChan = comm.AWGNChannel('EbNo',snr(i1) , 'BitsPerSymbol',2); % АБГШ канал hDemod =comm.QPSKDemodulator('BitOutput,,true,,DecisionMethod,,,Approximate log-likelihood ratio'); % Создание демодулятора hDec = comm.LDPCDecoder(sparse(H12)); hDec.MaximumIterationCount=In_ter; v=zeros(k/2, q); v1=randi([0 1], k/4, q); v2=randi([0 1], k/4, q); vr1=zeros(k/4,q); vr2=zeros(k/4,q); v=[v1 vr1 v2

vr2];% Исходное сообщение x=zeros(n,q); xr=zeros(n,q); u=zeros(n,q);

for i=1:q

x(:,i)=step(hEnc,v(:,i)); % закодированное сообщение xr1=x(1:(k/4),i); xr2=x((k/4+1):k/2,i); xr3=x((k/2+1):(3*k/4),i); xr4=x((3*k/4+1):k,i); xr5=x((k+1):n,i); xr(:,i)=[xr1 xr1 xr3 xr1 xr5];

%----------------------------------------------------

y = step(hMod, xr(:,i)); % модулированный сигнал %---------------------------------------------

w = step(hChan, y);% модулированный сигнал + Шум %----------------------------------------------

z= step(hDemod, w); % демодулированный сигнал zr=z;

zr1=zr(1:(k/4)); zr2=zr((k/4+1):k/2); zr3=zr((k/2+1):(3*k/4)); zr4=zr((3*k/4+1):k); zr5=zr((k+1):n);

zr1=(zr1+zr2+zr4);

zr2(1:(k/4))=inf; zr4(1:(k/4))=inf;

zr=[zr1 zr2 zr3

zr4 zr5]; u= step(hDec, zr); tm14(:,i)=double(u); end

[numm14,BERm14(i1)] = symerr(v, tm14);% вероятность ошибок после декодирования end

%--------------------------------IBD code rate-2/5-----------------

[m n]=size(H12);

k=n-m;

for i1=1:li

EbNo(i1)=beta*i1-alpha; snr(i1)=EbNo(i1)+10*log10(1/2);

hEnc = comm.LDPCEncoder(sparse(H12)); % Создание LDPC кодера

hMod =comm.QPSKModulator('BitInput,,true); % Создание модулятора

hChan = comm.AWGNChannel('EbNo',snr(i1) , 'BitsPerSymbol',2); % АБГШ канал

hDemod =comm.QPSKDemodulator('BitOutput,,true,,DecisionMethod,,,Approximate log-