Перейти к содержанию
    

Вопросы по мягкому декодированию кодов рида-соломона

Всем доброго дня. Ковыряясь в документах по кодированию, наткнулся на алгоритм мягкого декодирования кодов рида-соломона на основе метода обобщенных упорядоченных статистик (OSD) от Stefan Scholl . По смыслу, метод сильно напоминает смесь декодирования расширенного кода Голлея, методом "ловли ошибок" и алгоритма Чейза. Но для работы метода требуется представление проверочной матрицы кода на уровне битов. Собственно вопрос заключается в том, как ее получить?

Сложность у меня вот в чем. Рассмотрим код хэминга (7,4,3) который одновременно является кодом БЧХ в поле GF(2^3) с примитивным полиномом x^3 + x + 1.

Проверочная матрица кода хэминга H = [[1 0 0 1 0 1 1];[0 1 0 1 1 1 0]; [0 0 1 0 1 1 1]];

Проверочная матрица кода БЧХ Hb = [[1 a a^2 a^3 a^4 a^5 a^6]; [1 a^2 a^4 a^6 a^1 a^3 a^5]]; где a - элемент поля GF(2^3) == 1, a....a^6 = [001 010 100 011 110 111 101];

Если сделать подстановку битовых значений элементов поля, то можно увидеть что матрица хэминга равна первой строке матрицы БЧХ. И тут кучка вопросов:

1. Как быть со второй строкой, получается она не нужна?

2. Значит ли это, что ее используют только для арифметического декодирования БЧХ для составления полной системы уравнений?

3. Почему выкидывают именно вторую строку, а не первую?

4. Если рассмотреть коды в старших полях, то как определить какие именно строки будут нужны? По ссылке https://ru.bmstu.wiki/Код_Боуза_—_Чоудхури_—_Хоквингема приведено условие выбрасывания строк, но вот туплю и вьехать не могу, почему именно эти строки они удаляют.

Спасибо.  

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Судя по всему, дело в свойствах расширения поля Галуа GF(2^3). там есть такой эффект как смежные корни многочленов a, a^(2^[1:3]), тогда получаются корни a, a^2, a^4 относятся к одному классу смежности. В принципе это бы обьяснило удаление строк проверочной матрицы БЧХ. Но тогда возникает вопрос:

1. БЧХ (15,11,3) - проверочная матрица слов 2х15 -> убираем строку a^2 -> проверочная матрица бит 4х15 (ок. 4 проверочных бита)

2. БЧХ (15,7,5) - проверочная матрица слов 4х15 -> убираем строки a^2 и a^4 -> проверочная матрица бит 8х15 (ок. 8 проверочных бит)

3. БЧХ (15,5,7) - проверочная матрица слов 6х15 -> убираем строки a^2, a^4, a^6 -> проверочная матрица бит 12х15 (bad. всего 10 проверочных бит). - как существет такой код в поле GF(2^4)?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

9 hours ago, des00 said:

Судя по всему, дело в свойствах расширения поля Галуа GF(2^3). там есть такой эффект как смежные корни многочленов a, a^(2^[1:3]), тогда получаются корни a, a^2, a^4 относятся к одному классу смежности. В принципе это бы обьяснило удаление строк проверочной матрицы БЧХ. Но тогда возникает вопрос:

1. БЧХ (15,11,3) - проверочная матрица слов 2х15 -> убираем строку a^2 -> проверочная матрица бит 4х15 (ок. 4 проверочных бита)

a^3 и a^6 - тоже один класс смежности (cyclotomic coset)

Для кодов БЧХ длины 15 и кодового расстояния d (designed distance) имеем d-1 строчек проверочной матрицы вида b^i, I = 0..14, b = a^j, j = 1...d-1 вместе с линейно зависимыми, а - генерирующий элемент поля GF(2^4)

Косеты поля GF(2^4) по степеням генерирующего элемента

1 2 4 8

3 6 12 9

5 10

7 4 13 11

Для нижней границы числа информационных бит:

Для d = 3 имеем две строчки j = 1,2. Один косет лидер. Оставляем одну строчку получаем 15 - 4*1 = 11 инф бит

Для d = 5 имеем четыре строчки j = 1,2,3,4. Два косет лидера. Оставляем две строчки и получаем 15 - 4*2 = 7 инф бит

Для d = 7 имеем 6 строчек матрицы, три косет лидера. Оставляем 3 строчки и получаем 15 - 4*3 = 3 инф бит

Еще раз, это является НИЖНЕЙ границей числа информационных бит (n-k <= m(d-1)/2). В нашем случае n = 2^m - 1= 15, m = 4. Как пишут Лин с Костелло:

There is no simple formula for enumerating n-k, but if t is small n-k = mt, t = (d-1)/2.

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

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

Степени минимальных полиномов для косетов равны 4 , 4, 2, 4 - по количеству элементов в каждом косете. Получается, что lcm полиномов трех косетов есть полином 10 степени (5 инф бит)  

 

 

 

Изменено пользователем andyp

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

On 10/12/2018 at 3:46 AM, andyp said:

....Степени минимальных полиномов для косетов равны 4 , 4, 2, 4 - по количеству элементов в каждом косете. Получается, что lcm полиномов трех косетов есть полином 10 степени (5 инф бит)  

 

 

 

 

Перевариваю. Спасибо.

Эх, говорила же мне мама, учи линейную алгебру сынок (с) :)

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

4 hours ago, des00 said:

Перевариваю. Спасибо.

Я когда ПО для BCH делал, плясал от структуры косетов.  Для параметров кода n = 2^m - 1 и d - design distance рассчитать ее можно концептуально следующим образом:

Есть список от 1 до n.

1. Инициализируем лидера L = 1;

2. В косет записываем все (2*L*I) mod n, I = 1,2,.., пока снова не наткнемся на лидера. Вычеркиваем записанные в косет степени из списка. 

3. Находим нового лидера L, как минимальное невычеркнутое целое. Если L >= d, останавливаемся. Все нужные косеты получены. Иначе переходим снова к 2.

 

Например для БЧХ длины 15, для первого косета  минимальный полином m_1(x) = (х-a)*(x-a^2)*(x-a^4)*(x-a^8), a - генерирующий элемент поля GF(2^4). Для второго:

m_2(x) = (х-a^3)*(x-a^6)*(x-a^12)*(x-a^9)

Для остальных - аналогично. Генерирующй полином кода БЧХ (15,5,7) g(x) = m_1(x) * m_2(x)*m_3(x) - произведение минимальных полиномов косетов, включающих степени 1..d-1 генерирующего элемента.

Он автоматом получится с коэффициентами 0 и 1. g(х) имеет степень n-k. Генерирующая матрица состоит из строчек со сдвигами g(х).

Если нужна проверочная матрица, то алгоритмом Евклида находишь проверочный полином h(x) = (x^n-1)/g(x).  Делится без остатка по свойствам циклических кодов, h(x) имеет степень k. Затем его reciprocal:

r(X) = (X^k)*h(x^-1). В сущности у reciprocal polynomial те же коэффициенты, что и у h(х), только в обратном порядке. Проверочная матрица формируется как сдвиги reciprocal polynomial. Она же является генерирующей матрицей дуального кода.

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

Из хороших книжек по кодированию, которые достаточно алгебраичны и в то же время без лишней алгебры ;), мне нравится Vera Pless, Introduction to the Theory of Error-Correcting Codes.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

On 10/15/2018 at 7:32 PM, andyp said:

Из хороших книжек по кодированию, которые достаточно алгебраичны и в то же время без лишней алгебры ;), мне нравится Vera Pless, Introduction to the Theory of Error-Correcting Codes.

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

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

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...