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

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

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

То есть вам априори ничего неизвестно о коде? Например, его скорость, длина блока и т.д. Это задача слепой идентификации кода. Смотреть статьи по темам "Blind Identification of LDPC Codes", "Identification of LDPC Codes" и т.д.

Спасибо, что откликнулись!
Совсем забыл про это написать! Скорость кода известна - 0.5. Длина кодового слова тоже известна, но так как у меня все данные в академии я не помню точно сколько - но длина блока известна.
Соответственно мне надо написать декодер этого кода, а чтобы его написать надо получить матрицу.

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

Кстати, про фазу. У вас после демодуляции должен быть битовый поток - последовательность 0 и 1. Как вы могли подбирать фазу?

В случае мягкой демодуляции на выходе последовательность LLR. Здесь тоже непонятно, как вы что-то делали с фазой.

Наверное, по преамбуле

Вопрос не очень корректен по двум причинам:
1. Существует много линейных кодов, соответствующих одному и тому же набору кодовых слов (см. эквивалентные коды). Их порождающие матрицы могут быть получены линейными преобразованиями друг из друга.
2. В потоке может быть недостаточно кодовых слов, чтобы получить порождающую матрицу (на сколько я это представляю, должно быть как минимум n/2 линейно независимых кодовых слов в Вашем случае)

Если 2 выполняется, то можно выписать кодовые слова в строки и с помощью линейных преобразований привести полученную матрицу к виду [I -P], I - единичная, размером n/2. Получите порождающую матрицу эквивалентного кода в стандартной форме. Ирония в том, что у LDPC в строках и столбцах должно быть не больше определенного количества единиц (ну или четко определенное количество, если код регулярный). Полученная матрица этому условию скорее всего удовлетворять не будет, так как про систематические LDPC коды что-то не слышно. Мало того, даже если и удастся найти матрицу, удовлетворяющую этому условию (для этого надо знать макcимальную связность (parity and chеck node degree)), то не факт, что найденный эквивалентный код соответствует исходному (он, например, может быть получен из исходного простой перестановкой строк порождающей матрицы).

на мой взгляд это не реально из потока софт LLR восстановить H матрицу, особенно для больших матриц (количество chack node более тысячи), к тому же irregular
Честно не могу представить как это будет выглядеть, если H матрица изначальна не известна

Ну так и я про это. ТСу хочется странного.

Сигнал записан простым спутниковым модемом, кажется CDM какой-то, на его выходе БИТОВЫЙ поток. Код оказался систематическим - явно можно отделить проверочную часть от информационной. Так как модуляция 4-х позиционная, то путем перебора удалось подобрать фазу путем проворота созвездия, отсюда же и удалось выяснить истинную преамбулу (уникальное слово). Конец повествованию.


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

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

Как это бывает в России. Преподаватель вынес на диплом задачку уровня кандидата наук, если не доктора... Авось, ТС выплывет и чтото придумает.

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

Лучше помоги советом или просто направь в нужном направлении

Это все данные для этой задачи?

Если вопрос в дипломе именно в такой постановке, то всё, что требуется - это
- указать метод - например, constrained brute force attack (простой перебор по ограниченному множеству)
- приблизительно оценить ограничения
- оценить, сколько времени потребуется на нахождение матрицы на современном уровне техники и при разумных затратах.

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

Приветствую.
Решал данную задачу практически совсем недавно.
У вас есть ошибки к подходу которые нужно устранить.
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 суток.

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

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

Ок, спасибо. В том то и дело, что декодер ошибки исправлять будет, но как справедливо заметил 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)

Другими словами, матрицу можно рассчитать по сигналу с ошибками в кодовых словах?

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


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

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

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

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

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

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



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

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


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


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

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

Вышесказанным полностью согласен. Впрочем Вы описали все верно.
В первую очередь найти G. И эта G (порождающая матрица) - будет верной, поскольку в левой части должны быть по диагонали только одна "1" - что и говорит о правильности матрицы. А вот потом ищем H. Как получить H - в литературе много описано.

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

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

Да, но декодирование с помощью полученной матрице же возможно? Об оптимизации речи не идёт.

Вы пробовали декодировать ? Какие
результаты ?

Так вроде суть вопроса решить систему независимых лин кодов слов и используя результат решения декодировать. КТО сказал что НЕЛЬЗЯ. Вопрос КАК ?

Нихрена себе! Моя программа ищет матрицу ну минут 5, может 6, но не 5 часов - это ваще капец



То что ты тут понаписал очень здорово, но на все отвечать нет времени. Не такой я глупый, чтобы не знать о разряженности. Матрицу получил пораждающую и прорядил, не переживай. По поводу алгоритма - ты можешь плеваться и понтоваться, на ПК для декодирования в лдпс в реальном времени подходит только один алгориьм и только с разряженной матрицей. Даде уточню - на процессоре. На 1. Да и нахрена использовать какие то гавеные алгоритмы если есть старые добрые?



Почитайте как строятся flex ldpc и fast link ldpc. Там инфа рассыпана по слову перемешана с проверками


Я все сделал ты не переживай, а что такое ТС? Тупой студент?



Да все получилось, ссылок нету есть все на компе могу скинуть кусок потока и полученные матрицы g и h в каноне и разряженную h. Декодер написал жесткий bf. Пробовал abp, но он тока под плисину пошел, на pc ну очень уж долго хреначит

ТС - топик стартер.
Тот кто тему сформировол.
abp - это Asynchronous Decoding of LDPC Codes или что-то другое?

Наверное, belief propagation algorithm

Спасибо.
а " жесткий bf" - это наверное бит флиппинг?

Видимо, да, с перевертыванием бита