Матричный анализ кодов, Поиск параметров LDPC Опции

[Loona]

Всем привет. Пишу диплом. Нужна помощь следующего характера. Мой руководитель дал мне запись ЦИФРОВОГО ПОТОКА после демодуляции QPSK сигнала. Видна структура на периоде. Путем перебора удалось подобрать правильную фазу для устранения фазовой неоднозначности. Уровень сигнала при приеме 22 дБ - ошибок быть просто не должно!

Теперь собственно вопрос - как получить проверочную или порождающую матрицу LDPC-кода из имеющегося потока?

Я знаю, как определять параметры кодов Хэмминга - заполнить матрицу и получить диагональную. Это канает для всех блочных циклических кодов - для LDPC тоже?

[roman522]

Приветствую.
Решал данную задачу практически совсем недавно.
У вас есть ошибки к подходу которые нужно устранить.
1. "подбор фазы" - просто так не возможен нужна образцовая последовательность. ну и конечно нудно демодулировать с корректором. и учесть LLR
2. вам представлен вариант записи с реального оборудования. Из этого можно получить ряд послаблений.
2.1 если это LDPC код - то он систематический.
2.2 если разработчики данной железки "не фанаты", то код регулярный или квази циклический.
2.3 число проверок в строке H мало (<=10).

Первым шагом будет подготовка исходных данных.
1. демодулирование и получение soft bit
2. получение hard bit. анализ в битовом редакторе смещения кодовых слов и выделение кодовых слов в виде [data][check] LLR
3. удаление дубликатов кодовых слов. методом слияния.
4. удаление или корректировка кодовых слов с незначительными различиями. (<10 bit)
5. Выборка из полученного набора не менее 2*N кодовых слов с максимальным LLR.

Второй шаг - по подготовленной выборке "тупым" перебором и статистикой нахождение строк H ;-)
тут нужно задаться числом проверок k (обычно 5-10) длинна кодового слова n
и получаем число возможных вариантов
I =n!/( (n-k)! * k!)
Эти варианты можно ещё сократить если учесть свойства кодов.
и самым сложным является нахождение хотя бы одной строки, далее всё просто.

В итоге я получил скорость перебора ~3000M итераций на cpu-i7-4770, на GPU перевести не успел задача решилась раньше :-)
Решение задачи найдено часов за 5 вместо первоначальных ~30 суток.

[Serg76]

Решение задачи найдено часов за 5 вместо первоначальных ~30 суток.

Характеристики рассчитанного кода можете привести?

[roman522]

Характеристики рассчитанного кода можете привести?

N=720 R=1/2 k=[5,6,7] код оказался QC-LDPC
подробности уже стёрты. всё примерно. Главное декодер ошибки исправляет (проверка по CRC).

[Serg76]

N=720 R=1/2 k=[5,6,7] код оказался QC-LDPC
подробности уже стёрты. всё примерно. Главное декодер ошибки исправляет (проверка по CRC).

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

[roman522]

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

Не вижу смысла в такой постановке вопроса.
Задача вроде была найти H кода. и такую что бы работал декодер. Да я понимаю что эта H может быть не равна H настоящей.
Но если выполняются условия:
1. кривая BER ведёт себя также как у подобных кодов с подобными параметрами.
2. G_new полученная из H_new удовлетворяет условию G_new * [data_old] == G_old * [data_old]
то с практической точки зрения разницы нет.

Для себя открыл вот такие свойства LDPC, можно сказать теория
Декодирование и исправление ошибок возможно при не "полной" H. (можно повторно провести отсев кодовых слов)
Если задан код размером N скорости R и максимальным числом проверок Kmax, то при переборе по k=[3...Kmax] будет получено N*R проверок, собственно сколько и нужно.
Если выполнить перебор по k=Kmax+1 то будет найдено !=0 число проверок. (возможно может пригодится для оптимизации аппаратного декодера)

Главная плюшка метода, он гарантированно работает для псевдо/рандомных LDPC и BER входных кодовых слов 10^-2 (тестировался предварительно на малых кодах с BER=10^-1)

[SKov]

Не вижу смысла в такой постановке вопроса.
Задача вроде была найти H кода. и такую что бы работал декодер. Да я понимаю что эта H может быть не равна H настоящей.
...

Это правильно. Просто участники диспута, задающие вопрос об эквивалентных кодах,
путают понятия эквивалентных кодов и эквивалентых проверочных матриц для одного и того же кода.
Еще народ совершенно зря кошмарит бедного студента по поводу нахождения разреженной матрицы LDPC кода.
На самом деле бедному студенту нафиг не нужен код в разреженном виде (хоть студень, возможно, об этом и не подозревает ).
Похоже, что народ кроме BP и MIN-SUM алгоритмов уже ничего не может сделать с LDPC. Эх, молодежь.. )
Для данного случая вполне подойдет декодирование
по информационным совокупностям с покрывающими полиномами небольшого веса.
В простонародье этот метод называется OSD и он дает вполне приличные результаты
именно в хорошем канале. (интересующимся - гугл в помощь).

Главная плюшка метода, он гарантированно работает для псевдо/рандомных LDPC и BER входных
кодовых слов 10^-2 (тестировался предварительно на малых кодах с BER=10^-1)

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

[andyp]

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

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

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

Так что, никаких понятий эквивалентности я не путал, а говорил именно об эквивалентных линейных кодах.

[SKov]

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

Так что, никаких понятий эквивалентности я не путал, а говорил именно об эквивалентных линейных кодах.

Было сказано, что искомый код систематический. Обычно это означает, что порождающая матрица
кода имеет вид G=[ I | P ], где I - единичная матрица k*k.
Вы набираете (каких попало) k линейно независимых кодовых слов в матрицу,
а потом диагонализируете ее на первых k позициях, приводя к единичной матрице в левой части.
И получаете единственно возможную искомую порождающую матрицу G для систематического кода.
Только, мне кажется, что ТС нужна не порождающая, а проверочная матрица.
И он как-то строит ее в обход порождающей
И вопрос о многовариантности представления кода с помощью проверочной (или порождающей)
матрицы его совершенно не касается, т.к. ему надо ошибки исправлять, а для этого годится
любой из многих вариантов проверочных матриц, главное, чтобы там было единиц поменьше,
т.к. он, видимо, хочет использовать алгоритм, заточенный под низкую плотность единиц в H
А после исправления ошибок он просто возьмет первые k позиций, содержащих полезную информацию.
И истинный вид порождающей матрицы его мало волнует.

[andyp]

Было сказано, что искомый код систематический. Обычно это означает, что порождающая матрица

Не нашел у ТС, что тот LDPC, который он ищет - систематический. Он писал про систематического Хамминга, с которым возился раньше.

кода имеет вид G=[ I | P ], где I - единичная матрица k*k.
Вы набираете (каких попало) k линейно независимых кодовых слов в матрицу,
а потом диагонализируете ее на первых k позициях, приводя к единичной матрице в левой части.
И получаете единственно возможную искомую порождающую матрицу G для систематического кода.

Собственно это я и предлагал - набрать k (в случае TC - n/2) линейнонезависимых кодовых слов и ортогонализовать. Здорово, если только операциями со строками удастся свести G к стандартному виду. Но это вовсе не обязательно даже в случае систематического кода, так как систематические биты не всегда передаются первыми, даже чаще всего не первыми, чтобы упростить кодер. Ну и, разумеется, матрица в стандартной форме уже не будет разреженной.

[SKov]

Не нашел у ТС, что тот LDPC, который он ищет - систематический. Он писал про систематического Хамминга, с которым возился раньше.

В первом сообщении : 2.1 если это LDPC код - то он систематический.

Собственно это я и предлагал - набрать k (в случае TC - n/2) линейнонезависимых кодовых слов и ортогонализовать. Здорово, если только операциями со строками удастся свести G к стандартному виду.

Если исходный код был систематический (в классическом смысле, как я описал выше), то обязательно удастся

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

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