нужно ли узнать код чтобы произвести декодирование

Код Хэмминга. Пример работы алгоритма

Прежде всего стоит сказать, что такое Код Хэмминга и для чего он, собственно, нужен. На Википедии даётся следующее определение:

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

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

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

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

Как это работает.

Для того, чтобы понять работу данного алгоритма, рассмотрим пример.

Подготовка

Допустим, у нас есть сообщение «habr», которое необходимо передать без ошибок. Для этого сначала нужно наше сообщение закодировать при помощи Кода Хэмминга. Нам необходимо представить его в бинарном виде.

На этом этапе стоит определиться с, так называемой, длиной информационного слова, то есть длиной строки из нулей и единиц, которые мы будем кодировать. Допустим, у нас длина слова будет равна 16. Таким образом, нам необходимо разделить наше исходное сообщение («habr») на блоки по 16 бит, которые мы будем потом кодировать отдельно друг от друга. Так как один символ занимает в памяти 8 бит, то в одно кодируемое слово помещается ровно два ASCII символа. Итак, мы получили две бинарные строки по 16 бит:

и

После этого процесс кодирования распараллеливается, и две части сообщения («ha» и «br») кодируются независимо друг от друга. Рассмотрим, как это делается на примере первой части.
Прежде всего, необходимо вставить контрольные биты. Они вставляются в строго определённых местах — это позиции с номерами, равными степеням двойки. В нашем случае (при длине информационного слова в 16 бит) это будут позиции 1, 2, 4, 8, 16. Соответственно, у нас получилось 5 контрольных бит (выделены красным цветом):

Было:

Стало:

Таким образом, длина всего сообщения увеличилась на 5 бит. До вычисления самих контрольных бит, мы присвоили им значение «0».

Вычисление контрольных бит.

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

Здесь знаком «X» обозначены те биты, которые контролирует контрольный бит, номер которого справа. То есть, к примеру, бит номер 12 контролируется битами с номерами 4 и 8. Ясно, что чтобы узнать какими битами контролируется бит с номером N надо просто разложить N по степеням двойки.

Но как же вычислить значение каждого контрольного бита? Делается это очень просто: берём каждый контрольный бит и смотрим сколько среди контролируемых им битов единиц, получаем некоторое целое число и, если оно чётное, то ставим ноль, в противном случае ставим единицу. Вот и всё! Можно конечно и наоборот, если число чётное, то ставим единицу, в противном случае, ставим 0. Главное, чтобы в «кодирующей» и «декодирующей» частях алгоритм был одинаков. (Мы будем применять первый вариант).
Высчитав контрольные биты для нашего информационного слова получаем следующее:

и для второй части:

Вот и всё! Первая часть алгоритма завершена.

Декодирование и исправление ошибок.

Теперь, допустим, мы получили закодированное первой частью алгоритма сообщение, но оно пришло к нас с ошибкой. К примеру мы получили такое (11-ый бит передался неправильно):

Вся вторая часть алгоритма заключается в том, что необходимо заново вычислить все контрольные биты (так же как и в первой части) и сравнить их с контрольными битами, которые мы получили. Так, посчитав контрольные биты с неправильным 11-ым битом мы получим такую картину:

Как мы видим, контрольные биты под номерами: 1, 2, 8 не совпадают с такими же контрольными битами, которые мы получили. Теперь просто сложив номера позиций неправильных контрольных бит (1 + 2 + 8 = 11) мы получаем позицию ошибочного бита. Теперь просто инвертировав его и отбросив контрольные биты, мы получим исходное сообщение в первозданном виде! Абсолютно аналогично поступаем со второй частью сообщения.

Заключение.

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

Примечание.

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

Источник

Тест по информатике Способы кодирования для 5 класса

Тест по информатике Способы кодирования для 5 класса с ответами. Тест включает в себя 2 варианта, в каждом варианте 8 заданий с выбором ответа.

1 вариант

1. Какой код используют немые люди?

1) азбука Морзе
2) числовой код
3) код Брайля
4) язык жестов

2. Что происходит во время игры в «Морской бой»?

1) кодирование графической информации
2) декодирование информации
3) первое и второе действия

3. Маша закодировала слово «портфель», получилось «ьлеф­троп». Каким способом кодирования пользовалась Маша?

1) символьным
2) числовым
3) графическим

4. Турист в другой стране, какой способ кодирования он не выберет?

1) графический (карта города)
2) язык страны, в которой находится турист
3) английский язык
4) язык математики

5. Выберите неверное утверждение. Информацию кодируют

1) для удобства представления
2) для засекречивания
3) для красоты представления
4) для сокращения записи

6. Почему код замка от сейфа называют шифр?

1) код числовой
2) код короткий
3) код применяется к механическим частям
4) код для засекречивания

7. Какое действие из нижеперечисленных называется декодированием?

1) из символов «нбнб» получили слово «мама»
2) из слова «мама» получили «овов»
3) из слова «папа» получили 17 1 17 1
4) ни одно из перечисленных

8. Нужно ли узнать код, чтобы произвести декодирование?

2 вариант

1. Какой код используют плохо видящие люди?

1) азбука Морзе
2) числовой код
3) код Брайля
4) язык жестов

2. Маша закодировала слово «тетрадь», получилось «ьдартет». Каким способом кодирования пользовалась Маша?

1) символьным
2) числовым
3) графическим

3. Какой способ кодирования не используется при выступлении на конференции?

1) графический
2) флажковая азбука
3) английский язык
4) язык математики

4. Что происходит во время игры в шарады?

1) кодирование информации
2) декодирование информации
3) первое и второе действия

5. Выберите верное утверждение.

Способ кодирования информации зависит

1) от цели кодирования
2) от знания кодировщика информации
3) от умения декодировщика информации
4) от размера исходной информации

6. Как иначе можно назвать шифр?

1) числовой код
2) короткий код
3) секретный код
4) код

7. Миша получил шифровку. Сможет ли он, не узнав кода, прочитать записку?

8. Какое действие из нижеперечисленных называется декодированием?

1) из слова «кофе» получили «лпхё»
2) из символов «лпхё» получили слово «кофе»
3) из слова «папа» получили 17 1 17 1
4) ни одно из перечисленных

Ответы на тест по информатике Способы кодирования для 5 класса
1 вариант
1-4
2-3
3-1
4-4
5-3
6-4
7-1
8-1
2 вариант
1-3
2-1
3-2
4-3
5-1
6-3
7-2
8-2

Источник

Тест. 5 класс. Вариант 1. Кодирование. Способы кодирования информации.

Список вопросов теста

Вопрос 1

Среди предложенных высказываний выберите то, ко­торое наиболее полно и верно характеризует понятие ко­дирование:

Варианты ответов

Вопрос 2

Какой код используют немые люди?

Варианты ответов

Вопрос 3

Что происходит во время игры в «Морской бой»?

Варианты ответов

Вопрос 4

Маша закодировала слово «портфель», получилось «ьлеф­троп». Каким способом кодирования пользовалась Маша?

Варианты ответов

Вопрос 5

Выберите неверное утверждение. Информацию кодируют

Варианты ответов

Вопрос 6

Нужно ли узнать код, чтобы произвести декодирование?

Варианты ответов

Вопрос 7

Чтобы узнать зашифрованное слово, возьмите только первые слоги из данных слов:

КОЛОБОК, МЕТАЛЛ, ТАКЕЛАЖ

Вопрос 8

Чтобы узнать зашифрованное слово, возьмите только первые слоги из данных слов:

БАЗАР, РАДИУС, БАННЕР

Вопрос 9

Чтобы узнать зашифрованное слово, возьмите только вторые слоги из данных слов:

ПУГОВИЦА, СТОЛОВАЯ, СОВА

Вопрос 10

Восстановите информацию с помощью перестановки букв в слове:

Вопрос 11

Каждой букве алфавитасоответствует ее порядковый номер:

Расшифруйте слово: 3-10-15-25-6-19-20-6-18

Источник

Нужно ли узнать код чтобы произвести декодирование

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

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

Код состоит из определенного количества знаков (имеет определенную длину), которое называется длиной кода. Например, текстовое сообщение состоит из определенного количества букв, число — из определенного количества цифр.

Преобразование знаков или групп знаков одной знаковой системы в знаки или группы знаков другой знаковой системы называется перекодированием.

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

Кодирование может быть равномерным и неравномерным. При равномерном кодировании все символы заменяются кодами равной длины; при неравномерном кодировании разные символы могут кодироваться кодами разной длины (это затрудняет декодирование). Неравномерный код называют еще кодом переменной длины.

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

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

Коды Морзе для некоторых букв.

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

Декодирование информации

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

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

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

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

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

Например, код Морзе не является префиксным — для него не выполняется условие Фано. Поэтому в кодовый алфавит Морзе, кроме точки и тире, входит также символ–разделитель — пауза длиной в тире. Без разделителя однозначно декодировать код Морзе в общем случае нельзя.

Конспект урока по информатике «Кодирование и декодирование информации».

Источник

Все, что вы хотели узнать об LDPC кодах, но стеснялись спросить (наверное)

Предисловие

С кодами малой плотности проверок на чётность, которые дальше мы будем именовать коротко LDPC (Low-density parity-check codes), мне удалось познакомиться более или менее близко, работая над семестровым научным проектом в ТУ Ильменау (магистерская программа CSP). Моему научному руководителю направление было интересно в рамках педагогической деятельности (нужно было пополнить базу примеров, а также посмотреть в сторону недвоичных LDPC), а мне из-за того, что эти коды были плюс-минус на слуху на нашей кафедре. Не все удалось рассмотреть в том году, и поэтому исследование плавно перетекло в мое хобби… Так я набрал некоторое количество материала, которым сегодня и хочу поделиться!

Кому может быть интересна данная статья:

В общем, присоединяйтесь!

Внимание:
Предполагается, что читатель знаком с основами помехоустойчивого кодирования. Если тема совсем нова, то от себя в качестве ликбеза могу предложить данный материал: Channel codes basics (CommPy).

Содержание

Краткая историческая справка

LDPC коды — идея довольно старая, впервые они были описаны Робертом Галлагером ещё в 1963 г. в его работе на степень PhD [1]. Однако, из-за своей неоправданной сложности (по тем временам) они не находили применения в технике относительно долгое время.

И только в 1990-х годах эти коды были, так сказать, заново открыты М. Дэви и Д. Маккеем, которые предложили инновационные на тот момент способы построения LDPC кодов с уменьшенной сложностью [2].

Сейчас LDPC коды это:

Кроме того, все больше LDPC коды проникают и в спутниковую связь. В свое время, я делал небольшой обзор по малым спутникам CubeSat (посмотреть можно по ссылке) — там тенденция однозначная и обусловлена внедрением стандартов DVB-S2/S2X.

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

Азы блочного кодирования

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

Соответсвенно, процедура кодирования (encoding) — есть ничто иное, как перемножение вектора информационного сообщения длинной на некоторую порождающую матрицу :

где символ — это умножение по модулю (см. modulo). Для двоичных кодов это modulo 2, для недвоичных modulo q, исходя из полей Галуа .

Соответственно, и кодовая скорость тоже задается через порождающую матрицу:

Порождающая матрица состоит из двух конкатенированных (соединенных) частей:

где — это, так называемая, четная (parity) часть, а — единичная (identity) матрица.

Дело в том, что при умножении и сложении по модулю нужно соблюдать правила сопоставления отрицательных и положительных чисел:

На двоичном случае все это незаметно, и поэтому минус иногда пропускают.

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

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

Порождающая матрица напрямую связана с другой важнейшей матрицей, использующейся во время процедуры декодирования: с матрицей проверки на четность (parity-check matrix).

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

Ее основную идею очень удобно объяснять с помощью графа Таннера:

То есть существует два вида узлов: так называемые, узлы переменных (variable nodes), количество которых соответствуют числу столбцов , и узлы проверки (check nodes), соответствующие числу строк (). Узлы связаны между собой, и связь определяется положением единиц в матрице . Картинка справа — это моя собственная мнемоничка моего же производства. Как мне кажется, это самый простой способ уловить суть структуры: если элемент матрицы равен 1, значит связь между узлами есть, если равен 0 — связи нет.

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

Собственно говоря, эта матрица и определяет последние две буквы в аббревиатуре LDPC (Parity-Check).

Азы LDPC кодов

Но всё выше описанное — это общие моменты для большинства блочных кодов. Чем же тогда LDPC отличаются от тех же кодов Хэмминга?

В общем-то, тем, что и определяет их как low-density: их матрицы проверки на четность должны быть разряженными (sparce), то есть нулей в них должно быть значительно больше, чем чего-либо другого:

«Low density parity check codes are codes specified by a parity check matrix containing mostly zeros and only small number of ones.» [1]

Например, у того же Галлагера данная матрица была такой:

(3,4)-регулярная матрица проверки на четность длинною 12. Пояснение: кодовое слово, которое будет закодировано с помощью такого кода, будет иметь длину 12 бит; в каждом столбце 3 единицы, а в каждой строке 4, отсюда обозначение (3,4); количество единиц в строках и столбцах — это константы (в нашем случае 3 и 4), а значит код — регулярный.

У Маккея и Нила матрица проверки на четность была такой:

(3,4)-регулярная матрица проверки на четность длинною 12.

В стандарте DVB-S2 приняты уже нерегулярные (irregular) матрицы проверки на четность. См.:

Eroz M., Sun F. W., Lee L. N. DVB‐S2 low density parity check codes with near Shannon limit performance //International Journal of Satellite Communications and Networking. – 2004. – Т. 22. – №. 3. – С. 269-279.

Связано это с лучшей помехоустойчивостью нерегулярных схем.

Однако, ничего не замечаете? Правильно: эти матрицы не попадают под стандартную форму из формулы (3), ведь для LDPC кодов мы стремимся сделать проверочные матрицы разреженными. А если матрицы проверки не попадают под стандартную форму, значит не совсем понятно, как для них формировать порождающие матрицы.

Ответ, конечно, есть (и не один). Допустим, такой: изначальную матрицу приводят к стандартной форме через метод Гаусса (Gaussian elimination), из стандартной формы получают порождающую матрицу, а ее используют для кодирования.

Приведем пример из данного учебного материала:

Была такая матрица :

От нее, путем перемещений и преобразований строк по модулю 2, а также перемещений столбцов, перешли к матрице :

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

Формируем порождающую матрицу:

Создаем кодовое слово:

И проверяем синдром (то есть закодировали мы слово матрицей, произведенной от , а в процессе декодирования будем использовать разреженную матрицу ):

Магия линейной алгебры сработала!

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

Декодирование LDPC кодов

По LDPC кодам есть неплохой подбор материалов на Medium:

Однако, лично мне объяснение одного из центральных и самых, наверное, популярных алгоритмов декодирования — алгоритма Belief propagation (aka SPA — Sum-product algorithm) показалось, мягко говоря, слишком формальным (там просто прикреплена научная статья). Душа просит картинок и примеров!

За основу возьмем уже знакомый нам учебный материал:

Итак, во-первых, предположим, что у нас есть некая система связи:

Система связи состоит из:

Передатчик состоит из :

Приемник состоит из:

Договоримся, что под цифровыми модемами будем понимать в первую очередь самые популярные их разновидности: PSK и QAM.

Чем интересны для нас данные типы модуляции? Во-первых, тем, что именно они входят в стандарты современных беспроводных систем (LTE, Wi-Fi, DVB и т.д. ).

А, во-вторых, тем, что они умеют представлять зашумленные значения, полученные из канала связи, в форме, так называемых, мягких значений демодуляции (soft decisions). Или, если выражаться более наукообразно, в форме логарифмированных коэффициентов правдоподобия (LLR — log likelihood ratios):

где обозначает вероятность, а обозначает некоторое событие.

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

Итак, Belief propagation.

Потому что алгоритм работает с вероятностями. А точнее, с теми натуральными логарифмами от отношений вероятностей, которые мы указали в формуле (5).

Потому что эти вероятности будут итеративно «пересылаться» от узлов переменных к узлам проверки (сообщение V2C — Variable-to-Check) и наоборот (сообщение C2V — Check-to-Variable).

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

На этапе инициализации алгоритма LLR соответствуют априорным вероятностям. SPA является одним из алгоритмов максимальной апостериорной вероятности (MAP — maximum a posteriori probability), а значит он стремится максимизировать апостериорную вероятность, полученную после итеративной пересылки между узлами проверок и переменных.

Предлагаю рассмотреть пошагово.

Предупреждение:
Ниже будет представлено некоторое количество математических формул, и иногда они будут довольно непростыми для визуального восприятия. Поэтому если вы не настроены в данный момент на штудирование, предлагаю перейти сразу к пункту «Пример декодирования через SPA на Python (numpy)». Вернетесь к теории, когда будет время и настроение или когда захочется посмотреть, что лежит в основе скриптов (наверное).

1. Инициализация

Итак, для начала рассмотрим априорные вероятности.

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

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

2. Сообщение V2C

Затем следует, так называемый, горизонтальный шаг: алгоритм требует обработки сообщения (V2C) в области вероятности. Для перехода от LLR к вероятностям воспользуемся отношением между гиперболическим тангенсом и натуральным логарифмом [4, с.32 ]:

Собственно говоря, процедура передачи V2C сообщения — это перемножение ненулевых вероятностей в каждой строке:

где j — это номер определенной строки, i — это номер определенного столбца, — это множество ненулевых значений в j-ой строке, а выражение означает, что мы исключаем i-ый узел переменных (variable node) из рассмотрения.

То есть на данном этапе нам нужно:

Пункт с исключением узла из рассмотрения можно провести двумя способами: 1) выяснять нужное подмножество до перемножения вероятностей или удалять значение из результата после подсчетов. Я, простоты ради, буду пользоваться вторым методом.

Я думаю, кто-то из вас, возможно, слышал названия и других алгоритмов декодирования LDPC кодов. Например, Min-sum [5], Log-SPA [6] или еще какие-нибудь [7]. Такие алгоритмы еще иногда называются субоптимальными. В чем их отличие? Собственно, в данном пункте: данные алгоритмы стремятся снизить сложность декодирования и для этого используют иные формулы для вычисления горизонтального шага. Как правило, здесь начинается подсчет рисков: каким количеством помехоустойчивости мы готовы пожертвовать ради повышения скорости декодирования.

3. Проверка критерия остановки декодирования

Итак, мы подходим к концу первой итерации, а значит пора обновить наши априорные вероятности — сделать их апостериорными:

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

Наложим их на биты через обратный NRZ:

И вычислим синдром по формуле (4). Если вектор нулевой — останавливаем декодирование. Если нет, то переходим к следующему шагу.

4. Сообщение C2V

На этом этапе нужно пересчитать матрицу :

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

Пример декодирования через SPA на Python (numpy)

А теперь давайте перейдем к вещам более интересным — к примерам и скриптам!

Возьмем все тот же пример из [4, с.33 ]:

Начинаем декодировать (должна понадобиться одна итерация).

Попробуем другой пример [4, с.36 ]:

Исправить нужно первый и последний биты.

Готовые решения для моделирования

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

Давайте использовать готовые решения.

Наверное, первое, что придет вам на ум, — это Communication Toolbox от MathWorks (MatLab). Решение, пожалуй, действительно хорошее, но мне оно не нравится по нескольким причинам:

Поэтому я отправился в путешествие по проектам на GitHub и нашел весьма интересный инструментарий: проект aff3ct, написанный на C++.

Прочтем, как проект позиционируют его разработчики:

Работает ПО не только для LDPC кодов, но и для других кодеков (например, можно рассмотреть Turbo-коды и полярные коды).

У проекта есть хорошая документация в формате PDF, в формате WEB-страниц, а также онлайн-версия с визуализацией уже полученных результатов (BER/FER Comparator).

Выберем что-нибудь для примера:

Лучше открыть в новой вкладке для полноты эффекта.

Можно запустить любой эксперимент и под свой вкус. Для этого нужно будет по инструкции (см. Instalation) установить ПО и запустить его из командной строки с нужными параметрами.

Устанавливать нужно путем сборки из исходников. Поэтому не забывайте про суперпользователей и места нахождения make-файлов.

Например, я запустил на досуге такую модель к командной строке Ubuntu 18.04:

В итоге сформировалась такая таблица:

Даже такое аскетичное представление данных — как мне кажется, это уже классная возможность.

Можно, конечно, пойти дальше написать какие-нибудь обертки для отрисовки графиков.

У создателей проекта есть и собственные решения по визуализации. Например, PyBER. Суть «тулзы» заключается в том, что с помощью GUI вы можете выбирать сформированные aff3ct txt-файлы, PyBER вам их распарсит и отрисует (полученное можно даже экспортировать, вроде). Лично мне не понравилось представление: графики представлены через plot, а не через более логичный semilogy. Поэтому оставляю опыт использования PyBER на ваше усмотрение.

Допустим, результаты моделирования можно сохранить в txt-файл, а значения отношений битовых ошибок (BER — bit error ratio) можно вытащить уже из него c помощью простой манипуляции с awk:

Все это передать, допустим, в Python и нарисовать графики под свой вкус.

Для кодовых скоростей 1/2 и 3/4 (AWGN канал) у меня получились такая картинка:

Без изысков, но в качестве первого шага неплохо, как мне кажется.

Послесловие

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

Конструктивная критика только приветствуется. И спасибо за ваше внимание!

Литература

R.G. Gallager Low-Density Parity-Check Codes, IRE Transactions on Information Theory, 1962

D.J.C. MacKay Good Error-Correcting Codes Based on Very Sparse Matrices, IEEE Transactions on Information Theory, VOL.45, NO 2., March 1999

«3GPP RAN1 meeting #87 final report». 3GPP. Retrieved 31 August 2017.

Johnson, S. J. (2006). Introducing low-density parity-check codes. University of Newcastle, Australia, V1

Declercq D., Fossorier M. Decoding algorithms for nonbinary LDPC codes over GF(q) //IEEE transactions on communications. – 2007. – Т. 55. – №. 4. – С. 633-643.

Wymeersch H., Steendam H., Moeneclaey M. Log-domain decoding of LDPC codes over GF (q) //2004 IEEE International Conference on Communications (IEEE Cat. No. 04CH37577). – IEEE, 2004. – Т. 2. – С. 772-776.

Chen J. et al. Reduced-complexity decoding of LDPC codes //IEEE transactions on communications. – 2005. – Т. 53. – №. 8. – С. 1288-1299.

Приложения

Хотите немного линейной алгебры?

Давайте порассуждаем о том, как можно найти подмножества ненулевых вероятностей?

Для второго способа нужна будет, правда, заранее подготовленная матрица, которая будет повторять структуру матрицы H с точностью до наоборот: вместо единиц в ней будут нули, а вместо нулей единицы. Назовем ее «зеркалом» матрицы H:

где — это сложение по модулю (в нашем случае modulo 2).

Соответственно, процедура замены нулей на единицы в матрице — это сложение двух матриц:

После перемножения нужно будет вернуть структуру к исходному виду:

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

Вопрос о сложности и простоте декодирования, может быть, не так хорошо просматривается на двоичных кодах, однако на кодах недвоичных встает, так сказать, во весь рост. Пример для GF(4).

Во-первых, вместо вектора LLR, нам придется работать с матрицей LLR (нужно ведь проверять вероятность уже не только двух событий):

Соответственно, пересылаемые сообщения — это уже тензоры, которые придется разбивать на слои и обрабатывать в цикле:

И уже потом выбирать наиболее вероятное значение:

Сложность будет расти пропорционально увеличению q в выражении GF(q). Волей-неволей задумаешься о более быстрых алгоритмах…

Источник