des00 25 11 октября, 2018 Опубликовано 11 октября, 2018 · Жалоба Всем доброго дня. Ковыряясь в документах по кодированию, наткнулся на алгоритм мягкого декодирования кодов рида-соломона на основе метода обобщенных упорядоченных статистик (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/Код_Боуза_—_Чоудхури_—_Хоквингема приведено условие выбрасывания строк, но вот туплю и вьехать не могу, почему именно эти строки они удаляют. Спасибо. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
des00 25 11 октября, 2018 Опубликовано 11 октября, 2018 · Жалоба Судя по всему, дело в свойствах расширения поля Галуа 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)? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
andyp 9 11 октября, 2018 Опубликовано 11 октября, 2018 (изменено) · Жалоба 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 инф бит) Изменено 11 октября, 2018 пользователем andyp Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
des00 25 15 октября, 2018 Опубликовано 15 октября, 2018 · Жалоба On 10/12/2018 at 3:46 AM, andyp said: ....Степени минимальных полиномов для косетов равны 4 , 4, 2, 4 - по количеству элементов в каждом косете. Получается, что lcm полиномов трех косетов есть полином 10 степени (5 инф бит) Перевариваю. Спасибо. Эх, говорила же мне мама, учи линейную алгебру сынок (с) :) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
andyp 9 15 октября, 2018 Опубликовано 15 октября, 2018 · Жалоба 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. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
des00 25 26 октября, 2018 Опубликовано 26 октября, 2018 · Жалоба On 10/15/2018 at 7:32 PM, andyp said: Из хороших книжек по кодированию, которые достаточно алгебраичны и в то же время без лишней алгебры ;), мне нравится Vera Pless, Introduction to the Theory of Error-Correcting Codes. Спасибо за разьяснение, книжка реально хороша) Ставлю голову на место, по совету советской средней школы: математику уже затем учить надо, что она ум в порядок приводит (с) плакат с Ломоносовым в моей школе)) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться