реклама на сайте
подробности

 
 
3 страниц V  < 1 2 3 >  
Reply to this topicStart new topic
> Матричный анализ кодов, Поиск параметров LDPC
roman522
сообщение Jan 12 2016, 07:10
Сообщение #16





Группа: Новичок
Сообщений: 4
Регистрация: 19-10-07
Пользователь №: 31 504



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

Go to the top of the page
 
+Quote Post
Serg76
сообщение Jan 12 2016, 14:38
Сообщение #17


Профессионал
*****

Группа: Участник
Сообщений: 1 029
Регистрация: 4-04-07
Пользователь №: 26 775



Цитата(roman522 @ Jan 12 2016, 10:10) *
Решение задачи найдено часов за 5 вместо первоначальных ~30 суток.

Характеристики рассчитанного кода можете привести?
Go to the top of the page
 
+Quote Post
roman522
сообщение Jan 12 2016, 18:38
Сообщение #18





Группа: Новичок
Сообщений: 4
Регистрация: 19-10-07
Пользователь №: 31 504



Цитата(Serg76 @ Jan 12 2016, 17:38) *
Характеристики рассчитанного кода можете привести?

N=720 R=1/2 k=[5,6,7] код оказался QC-LDPC
подробности уже стёрты. всё примерно. Главное декодер ошибки исправляет (проверка по CRC).
Go to the top of the page
 
+Quote Post
Serg76
сообщение Jan 12 2016, 19:11
Сообщение #19


Профессионал
*****

Группа: Участник
Сообщений: 1 029
Регистрация: 4-04-07
Пользователь №: 26 775



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

Ок, спасибо. В том то и дело, что декодер ошибки исправлять будет, но как справедливо заметил andyp где гарантия, что найденный код будет соответствовать истинному?
Go to the top of the page
 
+Quote Post
roman522
сообщение Jan 12 2016, 20:03
Сообщение #20





Группа: Новичок
Сообщений: 4
Регистрация: 19-10-07
Пользователь №: 31 504



Цитата(Serg76 @ Jan 12 2016, 23:11) *
Ок, спасибо. В том то и дело, что декодер ошибки исправлять будет, но как справедливо заметил 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)
Go to the top of the page
 
+Quote Post
Serg76
сообщение Jan 12 2016, 21:00
Сообщение #21


Профессионал
*****

Группа: Участник
Сообщений: 1 029
Регистрация: 4-04-07
Пользователь №: 26 775



Цитата(roman522 @ Jan 13 2016, 00:03) *
Главная плюшка метода, он гарантированно работает для псевдо/рандомных LDPC и BER входных кодовых слов 10^-2 (тестировался предварительно на малых кодах с BER=10^-1)

Другими словами, матрицу можно рассчитать по сигналу с ошибками в кодовых словах?
Go to the top of the page
 
+Quote Post
SKov
сообщение Jan 28 2016, 15:07
Сообщение #22


Знающий
****

Группа: Свой
Сообщений: 805
Регистрация: 22-01-05
Из: SPb
Пользователь №: 2 119



Цитата(roman522 @ Jan 12 2016, 23:03) *
Не вижу смысла в такой постановке вопроса.
Задача вроде была найти H кода. и такую что бы работал декодер. Да я понимаю что эта H может быть не равна H настоящей.
...

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

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

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

Go to the top of the page
 
+Quote Post
andyp
сообщение Jan 28 2016, 16:15
Сообщение #23


Местный
***

Группа: Участник
Сообщений: 425
Регистрация: 23-07-08
Пользователь №: 39 163



Цитата(SKov @ Jan 28 2016, 18:07) *
Это правильно. Просто участники диспута, задающие вопрос об эквивалентных кодах,
путают понятия эквивалентных кодов и эквивалентых проверочных матриц для одного и того же кода.
Еще народ совершенно зря кошмарит бедного студента по поводу нахождения разреженной матрицы LDPC кода.
На самом деле бедному студенту нафиг не нужен код в разреженном виде (хоть студень, возможно, об этом и не подозревает wink.gif).


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

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

Так что, никаких понятий эквивалентности я не путал, а говорил именно об эквивалентных линейных кодах.
Go to the top of the page
 
+Quote Post
SKov
сообщение Jan 28 2016, 19:15
Сообщение #24


Знающий
****

Группа: Свой
Сообщений: 805
Регистрация: 22-01-05
Из: SPb
Пользователь №: 2 119



Цитата(andyp @ Jan 28 2016, 19:15) *
..
Очевидно, что у линейного кода кодовое слово получается как линейная комбинация строк генерирующей матрицы, а перестановка строк в матрице приведет к другому эквивалентному коду, состоящему из того же набора кодовых слов, просто информационные биты будут "включать" другие строки генерирующей матрицы.

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

Было сказано, что искомый код систематический. Обычно это означает, что порождающая матрица
кода имеет вид G=[ I | P ], где I - единичная матрица k*k.
Вы набираете (каких попало) k линейно независимых кодовых слов в матрицу,
а потом диагонализируете ее на первых k позициях, приводя к единичной матрице в левой части.
И получаете единственно возможную искомую порождающую матрицу G для систематического кода.
Только, мне кажется, что ТС нужна не порождающая, а проверочная матрица.
И он как-то строит ее в обход порождающей wink.gif
И вопрос о многовариантности представления кода с помощью проверочной (или порождающей)
матрицы его совершенно не касается, т.к. ему надо ошибки исправлять, а для этого годится
любой из многих вариантов проверочных матриц, главное, чтобы там было единиц поменьше,
т.к. он, видимо, хочет использовать алгоритм, заточенный под низкую плотность единиц в H wink.gif
А после исправления ошибок он просто возьмет первые k позиций, содержащих полезную информацию.
И истинный вид порождающей матрицы его мало волнует.
Go to the top of the page
 
+Quote Post
andyp
сообщение Jan 28 2016, 21:10
Сообщение #25


Местный
***

Группа: Участник
Сообщений: 425
Регистрация: 23-07-08
Пользователь №: 39 163



Цитата(SKov @ Jan 28 2016, 22:15) *
Было сказано, что искомый код систематический. Обычно это означает, что порождающая матрица


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

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


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



Go to the top of the page
 
+Quote Post
SKov
сообщение Jan 28 2016, 21:44
Сообщение #26


Знающий
****

Группа: Свой
Сообщений: 805
Регистрация: 22-01-05
Из: SPb
Пользователь №: 2 119



Цитата(andyp @ Jan 29 2016, 00:10) *
Не нашел у ТС, что тот LDPC, который он ищет - систематический. Он писал про систематического Хамминга, с которым возился раньше.

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

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

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

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

Честно говоря, не встречал информационные биты, рассыпанные как попало по слову. Обычно или в начале или в конце.
Ну, спорить не буду, всякое в жизни бывает wink.gif
Go to the top of the page
 
+Quote Post
andyp
сообщение Jan 28 2016, 23:29
Сообщение #27


Местный
***

Группа: Участник
Сообщений: 425
Регистрация: 23-07-08
Пользователь №: 39 163



Цитата(SKov @ Jan 29 2016, 00:44) *
Честно говоря, не встречал информационные биты, рассыпанные как попало по слову. Обычно или в начале или в конце.
Ну, спорить не буду, всякое в жизни бывает wink.gif


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

Go to the top of the page
 
+Quote Post
AspireSky
сообщение Jan 29 2016, 23:00
Сообщение #28





Группа: Участник
Сообщений: 11
Регистрация: 13-11-11
Пользователь №: 68 288



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


Вышесказанным полностью согласен. Впрочем Вы описали все верно.
В первую очередь найти G. И эта G (порождающая матрица) - будет верной, поскольку в левой части должны быть по диагонали только одна "1" - что и говорит о правильности матрицы. А вот потом ищем H. Как получить H - в литературе много описано.
Go to the top of the page
 
+Quote Post
abraziv
сообщение Sep 18 2017, 13:15
Сообщение #29


Участник
*

Группа: Участник
Сообщений: 21
Регистрация: 26-07-11
Пользователь №: 66 424



Добрый день товарищи инженера. Почему все говорят, что нельзя декодировать (исправить ошибки) систематический LDPC код с помощью матрицы полученной путём решения системы независимых линейных комбинаций кодовых слов?
Go to the top of the page
 
+Quote Post
Serg76
сообщение Sep 19 2017, 10:12
Сообщение #30


Профессионал
*****

Группа: Участник
Сообщений: 1 029
Регистрация: 4-04-07
Пользователь №: 26 775



Цитата(abraziv @ Sep 18 2017, 16:15) *
Добрый день товарищи инженера. Почему все говорят, что нельзя декодировать (исправить ошибки) систематический LDPC код с помощью матрицы полученной путём решения системы независимых линейных комбинаций кодовых слов?

По-видимому, из-за отсутствия эффективных алгоритмов декодирования при наличии высокой плотности единиц в матрице и таких размерах. В этом случае остро стоит вопрос кодирования, не то, что декодирования.
Go to the top of the page
 
+Quote Post

3 страниц V  < 1 2 3 >
Reply to this topicStart new topic
6 чел. читают эту тему (гостей: 6, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 22nd November 2017 - 11:14
Рейтинг@Mail.ru


Страница сгенерированна за 0.01353 секунд с 7
ELECTRONIX ©2004-2016