[Tpeck 0]

On 3/7/2019 at 10:05 AM, des00 said:

А есть кто нибудь, кто делал декодеры со списочным/стековым декодированием? 

Может и мимо конечно. Несколько лет назад реализовывал декодер сверточного систематического кода с большим кодовым ограничением. Использовал стек-алгоритм.

Но там сортировать надо было только 2 метрики, а не 2L %)

[des00 25]

19 hours ago, Tpeck said:

Может и мимо конечно. Несколько лет назад реализовывал декодер сверточного систематического кода с большим кодовым ограничением. Использовал стек-алгоритм.

Но там сортировать надо было только 2 метрики, а не 2L %)

Ну хоть кто-то отклинулся, а то тихо сам с собою веду беседу)

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

inactivePathIndices     = new stack with capacity L
activePath              = new boolean array of size L
arrayPointer_P          = new 2-D array of size (m + 1)  L, the elements of which are array pointers
arrayPointer_C          = new 2-D array of size (m + 1)  L, the elements of which are array pointers
pathIndexToArrayIndex   = new 2-D array of size (m + 1)  L
inactiveArrayIndices    = new array of size m + 1, the elements of which are stacks with capacity L
arrayReferenceCount     = new 2-D array of size (m + 1)  L

И мне не до конца понятно, почему нельзя сделать память пути как в том же декодере витерби, с обратным трейсбеком. расставить ссылки на предыдущий путь, считать метрику и CRC пути (если есть) и после декодирования собрать данные. Или там есть какой то тайный смысл ?

[Tpeck 0]

1 hour ago, des00 said:

И мне не до конфа понятно, почему нельзя сделать память пути как в том же декодере витерби, с обратным трейсбеком. расставить ссылки на предыдущий путь, считать метрику и CRC пути (если есть) и после декодирования собрать данные. Или там есть какой то тайный смысл ?

А это исходники для какого алгоритма?

Ведь про ML пишут, что вроде так и можно, но для маленьких кодов. Вот в этой статье Polar Coding: Finite-Length Aspects п. 3.5.1.

Я не знаю значения L и m. Но на первый взгляд объем памяти ~ L^m, а для больших кодов это много, если L - это кол-во входных метрик, а m - число связей. Но это вы и без меня знаете :)

А (SCL) Decoding, если я правильно понял это нужно бегать по решетке для каждого бита, а для этого надо хранить все (сначала ерунду написал) прошлые метрики с временными метками, да еще и сортировать их на каждый новый бит. 

В SSC такая же проблема, кодовое ограничение больше 35 и декодер Витерби не получается. Вот и приходилось бегать по решетке взад и вперед, пока FIFО не переполнялось :)

[des00 25]

16 hours ago, Tpeck said:

А это исходники для какого алгоритма?

Это код функции иницализации алгоритма SCL из документа List Decoding of Polar Codes авторов Ido Tal Alexander Vardy. Код рабочий, есть матлабовский пример этого кода, ссылку на код выше Grizzly давал.

Quote

Ведь про ML пишут, что вроде так и можно, но для маленьких кодов. Вот в этой статье Polar Coding: Finite-Length Aspects п. 3.5.1.

Много где встречал что ML для полярных кодов дает плохой результат из-за малого просвета. Пишут что только SC для длинных и SCL/SCL+CRC для коротких позволяют перебить LDPC и Turbo коды. Очередное непонимание, просто на интересных кодах, (4...32к) его делать сложно)

Quote

Я не знаю значения L и m. Но на первый взгляд объем памяти ~ L^m, а для больших кодов это много, если L - это кол-во входных метрик, а m - число связей. Но это вы и без меня знаете :)

А (SCL) Decoding, если я правильно понял это нужно бегать по решетке для каждого бита, а для этого надо хранить все (сначала ерунду написал) прошлые метрики с временными метками, да еще и сортировать их на каждый новый бит. 

Мой косяк, m - количество слоев кодера, 2^m длинна блока. Декодирование осуществляется по слоям, с сохранением промежуточного контекста (или рассчетом его заново), поэтому расход памяти даже на классическое SC декодирование большой.  L - количество используемых списков.

Для SC алгоритма нужно хранить входные и промежуточные метрики в количестве 2*block_length, промежуточные результаты кодирования 2*block_length бит и, если нужно, исходную последовательность бит block_length (не нужны, если используется систематическое кодирование). Ну и такая портянка у каждого списка. Как я понял алгоритм, сортировка там только на основе текущих метрик пути, для определения какие записи из списка убрать и какие клонировать и пополнить.

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

 

ЗЫ. Сверточник на кодовое ограничение 35 ? Реально?? это для каких целей нужен такой код? Не проще ли каскадный или турбо/лдпц использовать?

 

[Serg76 0]

В 13.03.2019 в 06:17, des00 сказал:

ЗЫ. Сверточник на кодовое ограничение 35 ? Реально?? это для каких целей нужен такой код? Не проще ли каскадный или турбо/лдпц использовать?

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

[Tpeck 0]

On 3/13/2019 at 7:17 AM, des00 said:

Как я понял алгоритм, сортировка там только на основе текущих метрик пути, для определения какие записи из списка убрать и какие клонировать и пополнить.

Когда я реализовывал SSC, нужно было для каждой метрики весь стек метрик пересортировывать. Если путь был выбран не верно, то его метрика не росла и в конце-концов уступала, метрики другого пути, хоть дцать тактов назад. В зависимости от глубины стека.

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

On 3/13/2019 at 7:17 AM, des00 said:

ЗЫ. Сверточник на кодовое ограничение 35 ? Реально?? это для каких целей нужен такой код? Не проще ли каскадный или турбо/лдпц использовать?

 

Первый релиз iess309, где используются SSC был 1985 году :)

[des00 25]

4 hours ago, Tpeck said:

Когда я реализовывал SSC, нужно было для каждой метрики весь стек метрик пересортировывать. Если путь был выбран не верно, то его метрика не росла и в конце-концов уступала, метрики другого пути, хоть дцать тактов назад. В зависимости от глубины стека.

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

Похоже я понял почему сделано так, там все равно нужны указатели на массивы результатов промежуточных вычислений, поэтому какая разница как кодировать путь, все равно указатели синхронизированны) Поэтому отбой)

5 hours ago, Serg76 said:

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

4 hours ago, Tpeck said:

Первый релиз iess309, где используются SSC был 1985 году :)

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

А сейчас, меня ткнули носом (спасибо Павлу Трифонову) в то, что декодировать полярный код, методом последовательного декодирования, проще, чем методом списочного последовательного исключения, при большом размере списка (больше 8 списков). Более того, используя часть статически замороженных битов в качестве динамически замороженных битов, можно улучшить характеристики полярного кода и более того, мягко декодировать коды рида соломона)

Чем дальше в лес, тем больше узнаю) надо было идти в математики, а не радиотехники))))))

[des00 25]

Первая проба пера

 

[Grizzly 0]

@des00 Офигеть) Респект!