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

 
 
16 страниц V   1 2 3 > »   
Reply to this topicStart new topic
> Вопросы по итеративному декодированию, Реализация CTC/BTC/LDPC кодов
des00
сообщение Dec 24 2014, 14:00
Сообщение #1


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Добрый день!

Наконец то появилось время подтянуть себя в вопросах реализации кодов с вероятностным декодированием. Первая задача реализация DVB-RCS/WiMAX CTC кодера на ПЛИС, часть проекта будет выложен в опенсорс. Решил создать отдельную тему для обсуждения вопросов по реализации

После штудирования литературы и примеров сорцов в сети возникла часть вопросов, на которые не хватает ума/настойчивости найти ответы:
1. Для DVB-RCS оговорены выкалывания под скорости кодирования 1/3, 2/5, 1/2, 2/3, 3/4, 4/5, 6/7. Почему не определены скорости 5/6 (удивляет "дырка" между скоростями 4/5 и 6/7) и 7/8? При этому матрица выкалывания под эти скорости возможна.
2. Полиномы RCS для Wimax и DVB одинаковые, но перемежители разные. Это сделано по политическим причинам или это результат "улучшения" характеристик декодера в процессе разработки стандарта?
3. В сверточных бинарных кодах, свойство tail-bitting используется при декодировании: В одной доке нашел что дополняют принятую последовательность вначале и в конце, затем декодируют по витерби и выкусывают нужное. В примере матлаба вообще составляют два фрейма, декодируют один за другим, потом из двух декодированных собирают один результат. Никакого намека на похожие операции в доках на турбокоды не нашел. Почему в алгоритмах SOVA/MAP/... для турбокодов это не делается?
4. По tail-bitting нашел в доках только то, что особым образом инициализируются рекурсия прямой и обратной метрики на первой итерации, а на всех остальных значения между итерациями сохраняются. Но
в сорцах от CML цикл по итерациям выглядит так :
Код
for it = 1:max_iterations
    inx1 = X + inner_extr;
    [outx1, outz1]=DuobinaryCRSCDecode( inx1, inz1, poly, decoder_type);
    
    llrx1 = outx1 - inner_extr;
    inx2(1:3*N) = llrx1( code_interleaver_GF4);
    [outx2, outz2, out_info]=DuobinaryCRSCDecode( inx2, inz2, poly, decoder_type);
    detected_data(code_interleaver.info_intl) = (out_info>0)+0;
    errors(it)= sum( sum(abs(detected_data - data)));
    if (errors(it) == 0)
        break;
    else
        inner_extr(code_interleaver_GF4) = outx2 - inx2;
    end
end

Т.е. видно что последовательные вызовы функции DuobinaryCRSCDecode между собой не обмениваются этой информацией. А в самих функциях
Код
    // initialization  for CRSC code
    for (i =0; i< max_states; i++)
    {
        alpha[i][0] = 0;
        beta[i][len] = 0;
    }

Т.е. не используется даже свойство одинакового начального состояния. Более того, в алгоритмах с оконным расчетом обратной рекурсии тоже забивают на свойство tail-bitting. Так насколько это важно и почему во всех доках настойчиво пишут кодировать данные 2 раза для определения состояния инициализации?
5. В алгоритмах, наследованных от Log-MAP метрика ветки считается как сумма корреляций метрик приемных битов с выходными битами решетки : gamma(Sk-1, S) = Lapri + (ys0*xs0 + ys1*xs1 + yp0*xp0 + yp1*xp1). При этом предполагается что y - надежность принятого символа , x = -1/1 выходной(переданный) бит. В сорцах от CML это место выглядит так :
Код
    int m_input = 2;  // 2 input bits,
    int max_states = 8; // total state numbers
    int M_input = 1<<m_input;
    int i, j, max_trellis = M_input * max_states;
.......
        for (j = 0; j< max_trellis; j++)
        {
            temp_input = j%M_input;
            temp_output = trellis_out[j];
            gamma[j] = ( temp_input ==0)? 0: inx[ (temp_input -1)+ i*llr_height ];   //llr for systematic symbol
            gamma[j] += ( temp_output ==0)? 0: inz[ (temp_output -1)+ i*llr_height ];  //llr for parity symbol
        }

Насколько я понимаю Си gamma[j] = ( temp_input ==0)? 0: inx[ (temp_input -1)+ i*llr_height ] - берет надежности символов кроме нулевого. Диапазон изменения temp_input = 0..3 или в битах 00/01/10/11. Вот этот момент мне совсем не понятен.

Пока всё sm.gif Прошу помощи тех кто в теме.


--------------------
Go to the top of the page
 
+Quote Post
stealth-coder
сообщение Dec 24 2014, 19:54
Сообщение #2


Частый гость
**

Группа: Участник
Сообщений: 112
Регистрация: 27-12-08
Пользователь №: 42 786



2. Полиномы RCS для Wimax и DVB одинаковые, но перемежители разные. Это сделано по политическим причинам или это результат "улучшения" характеристик декодера в процессе разработки стандарта?

Совершенно разные каналы генерируют совершенно разные ошибки (одиночные/пачки, длина пачки и т.д.), отсюда и разные перемежители, подобранные каждый под свои модели каналов.

3. В сверточных бинарных кодах, свойство tail-bitting используется при декодировании: В одной доке нашел что дополняют принятую последовательность вначале и в конце, затем декодируют по витерби и выкусывают нужное. В примере матлаба вообще составляют два фрейма, декодируют один за другим, потом из двух декодированных собирают один результат. Никакого намека на похожие операции в доках на турбокоды не нашел. Почему в алгоритмах SOVA/MAP/... для турбокодов это не делается?

Вопрос в получаемом энергетическом выигрыше и цене, которую за это надо заплатить. В случае сверточных кодов tail-biting дает +0.3 дБ, а платой за это является требование увеличения вычислительной мощности устройства, на котором реализуется декодер. По всей видимости в случае турбокодов это нецелесообразно.
Go to the top of the page
 
+Quote Post
andyp
сообщение Dec 24 2014, 22:13
Сообщение #3


Местный
***

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



Пункт 1

Вероятно, кривая BER для 5/6 лежит слишком близко к кривым 4/5 и 6/7, поэтому в этой скорости нет смысла, если используется адаптивная модуляция-кодирование. Это только догадка, которую стоит проверить, если ответ интересен.

Пункты 3-4

Сравнение реализаций с прологом и с использованием состояния, полученного на предудыщей итерации приведены здесь
http://www.see.ed.ac.uk/~slig/papers/zhan.icassp06.pdf

Пункт 5

Массив inx для каждого i похоже содержит предварительно 3 рассчитанные суммы вида ys0*xs0 + ys1*xs1 для входных пар бит 01, 10, 11, из которых уже вычтена сумма для 00

Сообщение отредактировал andyp - Dec 25 2014, 07:08
Go to the top of the page
 
+Quote Post
des00
сообщение Dec 26 2014, 03:46
Сообщение #4


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(stealth-coder @ Dec 25 2014, 02:54) *
Совершенно разные каналы генерируют совершенно разные ошибки (одиночные/пачки, длина пачки и т.д.), отсюда и разные перемежители, подобранные каждый под свои модели каналов.

Понятно. Интересно, есть ли работы по обоснованию выбора трасс таких перемежителей именно для турбокодов. Судя по формулам перемежения, они идентичны. разница только в P0...P3. Причем в Wimax перемежитель проще (всего 2 параметра P0/P1), хотя по идее он работает в более сложных условиях: широкополосный доступ/полузакрытые и закрытые интервалы.

Цитата
По всей видимости в случае турбокодов это нецелесообразно.

Цитата(andyp @ Dec 25 2014, 05:13) *
Сравнение реализаций с прологом и с использованием состояния, полученного на предудыщей итерации приведены здесь

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

По этой же теме возник вопрос : насколько обоснованно укорочение CTC кодов и чем именно лучше делать укорочение? Например в BCH/RS просто зануляем укорачиваемые слова на кодере, а на декодере изменяем начальную точку декодирования. А в CTC наверное лучше заполнять не нулями, а какой нить ПСП ?


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Dec 26 2014, 08:56
Сообщение #5


Местный
***

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



Цитата(des00 @ Dec 26 2014, 06:46) *
По этой же теме возник вопрос : насколько обоснованно укорочение CTC кодов и чем именно лучше делать укорочение? Например в BCH/RS просто зануляем укорачиваемые слова на кодере, а на декодере изменяем начальную точку декодирования. А в CTC наверное лучше заполнять не нулями, а какой нить ПСП ?


WiMax работает так - входные данные добиваются 0xFF до размера выделенного кодового блока, прогоняются через рандомайзер (это XOR с определенной ПСП), затем поступают в кодер. Размеры кодовых блоков определены в стандарте. Для каждого размера кодового блока определяются параметры интерливера. Т.е. CTC WiMax работает только для фиксированного набора кодовых блоков.

Сообщение отредактировал andyp - Dec 26 2014, 09:06
Go to the top of the page
 
+Quote Post
des00
сообщение Dec 26 2014, 09:48
Сообщение #6


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Dec 25 2014, 06:13) *
Массив inx для каждого i похоже содержит предварительно 3 рассчитанные суммы вида ys0*xs0 + ys1*xs1 для входных пар бит 01, 10, 11, из которых уже вычтена сумма для 00

Вы правы, так и есть, правда сумма для 00 не вычитается. Вот это место :
Код
// llr = received LLR of the code bits.
...
Nbits = length(code_interleaver.info_intl);
N = Nbits/2;
...
depun_llr = zeros(1,3*Nbits);
....
depun_llr(1:3*Nbits) = llr;
.....
    temp_llr([1,2],:) = reshape( depun_llr(1:2*N), 2, N );
    temp_llr([3,4],:) = reshape( depun_llr(2*N+1:4*N), 2, N);
    temp_llr([5,6],:) = reshape( depun_llr(4*N+1:6*N), 2, N);
....
X = [ temp_llr([2,1],:); temp_llr(1,:)+temp_llr(2,:)]; %% llr: 01, 10, 11
inz1  = [ temp_llr([5,3],:); temp_llr(3,:)+temp_llr(5,:)]; %% llr: 01, 10, 11
inz2  = [ temp_llr([6,4],:); temp_llr(4,:)+temp_llr(6,:)]; %% llr: 01, 10, 11

Судя по всему они определяют символы 0/1 а не -1/1. Занятно что в других местах не так.

Цитата(andyp @ Dec 26 2014, 16:56) *
Т.е. CTC WiMax работает только для фиксированного набора кодовых блоков.

Всё так, этот момент понятнен. Но что мешает поступить следующим образом : положим работаем с фреймом 53 байта и хотим укоротить его на 1 байт. Берем 52 байта данных и 1 байт добиваем нулями. Кодируем. Пары систематических символов, порожденные этим байтом в поток не передаем. На приемной стороне определяем эти биты как априори известные и декодируем.


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Dec 26 2014, 12:10
Сообщение #7


Местный
***

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



Цитата(des00 @ Dec 26 2014, 12:48) *
Вы правы, так и есть, правда сумма для 00 не вычитается. Вот это место :

Странно. Судя по коду, который Вы приводили выше, они считают, что гамма для переходов решетки с 00 равна 0. Я поэтому про вычитание и предположил. Может быть, это еще где учитывается.

Цитата
Всё так, этот момент понятнен. Но что мешает поступить следующим образом : положим работаем с фреймом 53 байта и хотим укоротить его на 1 байт. Берем 52 байта данных и 1 байт добиваем нулями. Кодируем. Пары систематических символов, порожденные этим байтом в поток не передаем. На приемной стороне определяем эти биты как априори известные и декодируем.


В системном плане смысла нет. В WiMax единицей частотно-временного ресурса системы является слот. В случае OFDMA это определенным образом расставленные по времени и частоте поднесущие (там много всяких комбинаций). Планировщик передачи выделяет ресурс слотами. Разбивка на слоты в аплинке и даунлинке сообщается всем станциям через специальные сообщения, передаваемые на фиксированных местах фрейма. Все кодовые блоки содержат целое количество слотов. Так уж это работает.
Go to the top of the page
 
+Quote Post
des00
сообщение Dec 26 2014, 16:05
Сообщение #8


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Занятное дело. Скидал в матлабе кодер, похожий на железный, и вот что обнаружилось: интерливер в сорцах CML и в стандарте разный. А именно отличается условие инверсии пар.
В стандарте интерливер работает так :
Код
    for j=0:N-1
        i = get_paddr(j, N, P);        
        if mod(j,2) == 0 % equal standart            
            odat([1, 2],j+1) = idat([2, 1], i+1);
        else
            odat([1, 2],j+1) = idat([1, 2], i+1);
        end
    end

а в CML
Код
    for j=0:N-1
        i = get_paddr(j, N, P);        
        if mod(i,2) == 0 % equal CML            
            odat([1, 2],j+1) = idat([2, 1], i+1);
        else
            odat([1, 2],j+1) = idat([1, 2], i+1);
        end
    end

Занятная вещь. Похоже местоположение инверсии пар не сильно принципиально sm.gif

Пример кода в приложении. При работе требует либу http://www.iterativesolutions.com/Matlab.htm
Прикрепленные файлы
Прикрепленный файл  CTC.zip ( 2.31 килобайт ) Кол-во скачиваний: 39
 


--------------------
Go to the top of the page
 
+Quote Post
des00
сообщение Dec 26 2014, 17:15
Сообщение #9


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(des00 @ Dec 24 2014, 22:00) *
1. Для DVB-RCS оговорены выкалывания под скорости кодирования 1/3, 2/5, 1/2, 2/3, 3/4, 4/5, 6/7. Почему не определены скорости 5/6 (удивляет "дырка" между скоростями 4/5 и 6/7) и 7/8? При этому матрица выкалывания под эти скорости возможна.

Цитата(andyp @ Dec 25 2014, 06:13) *
Вероятно, кривая BER для 5/6 лежит слишком близко к кривым 4/5 и 6/7, поэтому в этой скорости нет смысла, если используется адаптивная модуляция-кодирование. Это только догадка, которую стоит проверить, если ответ интересен.

ларчик просто открывался. В DVB размеры фреймов сильно не кратны скоростям 5/6 и 7/8. Выкалывание скоростей 1/2, 2/3 и 4/5 хорошо ложится на размеры фреймов, выкалывания 3/4 и 6/7 требуют 3-х фреймов для выравнивания, а 5/6 требует уже 15. Похоже просто убрали скорость, чтобы не заморачиваться sm.gif В этом вопросе WiMax гибче, у него количество фреймов разной длинны больше sm.gif


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Dec 27 2014, 18:25
Сообщение #10


Местный
***

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



Цитата(des00 @ Dec 26 2014, 19:05) *
Занятная вещь. Похоже местоположение инверсии пар не сильно принципиально sm.gif


Только кодер перестанет быть стандартным sm.gif. Рассмотрим второе преобразование (перестановку пар) и кодовый блок с N=24 (P0=5, P1=P2=P3=0). Если рассмотреть j mod 4 = 0 (четное), то i = (5*j + 1) mod N - нечетное. Соответственно, А и В будут переставлены не у тех пар.

Я бы перестал ориентироваться на либу CML, тем более, что последний вариант, доступный в исходниках, очень старый.

Сообщение отредактировал andyp - Dec 27 2014, 18:28
Go to the top of the page
 
+Quote Post
Dr.Alex
сообщение Dec 28 2014, 10:23
Сообщение #11


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

Группа: Свой
Сообщений: 1 386
Регистрация: 5-04-05
Из: моська, RF
Пользователь №: 3 863



.
Go to the top of the page
 
+Quote Post
des00
сообщение Dec 28 2014, 14:46
Сообщение #12


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Возник вопрос по поводу расчета LLR канальных символов. Изучил другие темы на форуме и доку от AHA, все понятно и обосновано. Вопрос возник вот в каком моменте: посмотрел реализации других декодеров софтовых/хардварных. Одни предлагают подавать на вход квантованные LLR, другие квантованные канальные символы (например для QAM16 - 2 бита целая часть, 4 бита дробная).

Насколько я понимаю при декодировании речь может идти только о квантовании LLR, а по каким канальным символам она была вычислена, личное дело того кто использует декодер. Канальные символы квантуют что бы уменьшить требования к аппаратуре/памяти. Правильно ли это, или есть какой-то другой тайный смысл ?

Есть еще такой вопрос: рассмотрим нормированное созвездие QAM16. Возьмем угловую точку '00' 0.75 + 0.75i. В этом случае, канальный символ 0.99+0.99i будет трактован как очень надежный символ '00'. А как правильно, трактовать канальный символ 1.5 + 1.5i, т.е. выход точки за пределы нормировки созвездия (например на АРУ), который может возникнуть, ну положим, из-за импульсной помехи? Ведь для стационарного AWGN канала это нештатная ситуация и точка не может быть очень надежной и ее желательно "стереть". Или это уже из области, отличной от декодеров в AWGN канале?


--------------------
Go to the top of the page
 
+Quote Post
Serg76
сообщение Dec 28 2014, 19:12
Сообщение #13


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

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



Цитата(des00 @ Dec 28 2014, 17:46) *
Одни предлагают подавать на вход квантованные LLR, другие квантованные канальные символы (например для QAM16 - 2 бита целая часть, 4 бита дробная).

Насколько я понимаю при декодировании речь может идти только о квантовании LLR, а по каким канальным символам она была вычислена, личное дело того кто использует декодер. Канальные символы квантуют что бы уменьшить требования к аппаратуре/памяти. Правильно ли это, или есть какой-то другой тайный смысл ?

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

Цитата(des00 @ Dec 28 2014, 17:46) *
Есть еще такой вопрос: рассмотрим нормированное созвездие QAM16. Возьмем угловую точку '00' 0.75 + 0.75i. В этом случае, канальный символ 0.99+0.99i будет трактован как очень надежный символ '00'. А как правильно, трактовать канальный символ 1.5 + 1.5i, т.е. выход точки за пределы нормировки созвездия (например на АРУ), который может возникнуть, ну положим, из-за импульсной помехи? Ведь для стационарного AWGN канала это нештатная ситуация и точка не может быть очень надежной и ее желательно "стереть". Или это уже из области, отличной от декодеров в AWGN канале?

Это уже епархия демодулятора (АРУ, ограничители), чтобы все выходные значения лежали в заданном диапазоне
Go to the top of the page
 
+Quote Post
andyp
сообщение Dec 28 2014, 19:30
Сообщение #14


Местный
***

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



Цитата(des00 @ Dec 28 2014, 17:46) *
Насколько я понимаю при декодировании речь может идти только о квантовании LLR, а по каким канальным символам она была вычислена, личное дело того кто использует декодер. Канальные символы квантуют что бы уменьшить требования к аппаратуре/памяти. Правильно ли это, или есть какой-то другой тайный смысл ?

Алгоритм BCJR, используемый при декодировании, работает в терминах вероятностей перехода из состояния в состояние по решетке, описывающей код. Его логарифмическая версия, требующая меньше вычислений, работает в терминах логарифмов этих вероятностей. Если говорить о дальнейшем упрощении (MAXLOGMAP), то добавление (вычитание) любой величины к логарифму вероятностей перехода по решетке ничего не меняет. Умножение всех логарифмов на константу изменяет в то же число раз рассчитанные LLR кодированных бит на выходе. Это (возможность вычитания) позволяет использовать LLR вместо логарифмов вероятностей переходов, поэтому декодер кушает LLR кодированных бит, из которых легко получить LLR переходов в решетке. Фиксированная разрядность имеет смысл только для практики, но не для теории. Также можно отметить еще одну штуку: из LLR легко получить логарифмы вероятностей отдельных бит. Легко показать, что если p(0) + p(1) = 1; LLR = log(p(1)/p(0)), то:
log(p(1)) = log(exp(LLR)/(exp(LLR)+1)); log(p(0)) = log(1/(exp(LLR)+1))

Цитата
Есть еще такой вопрос: рассмотрим нормированное созвездие QAM16. Возьмем угловую точку '00' 0.75 + 0.75i. В этом случае, канальный символ 0.99+0.99i будет трактован как очень надежный символ '00'. А как правильно, трактовать канальный символ 1.5 + 1.5i, т.е. выход точки за пределы нормировки созвездия (например на АРУ), который может возникнуть, ну положим, из-за импульсной помехи? Ведь для стационарного AWGN канала это нештатная ситуация и точка не может быть очень надежной и ее желательно "стереть". Или это уже из области, отличной от декодеров в AWGN канале?


Про рассчет LLR отдельных бит на выходе демодулятора писал здесь:
http://electronix.ru/forum/index.php?showt...t&p=1270246

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

Я обычно ограничиваю макс. значение в квадратурах уровнем max+d - max - макс. значение квадратуры созвездия, d - расстояние до ближайшей соседней от d точки. Т.е. Пусть имеем QAM16 - макс. по квадратуре 3, расстояние до ближайшей точки 2. Ограничиваю квадратуры на входе демаппера по уровню +/- 5.
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 28 2014, 20:26
Сообщение #15


я только учусь...
******

Группа: Модераторы
Сообщений: 3 447
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Прошу прощения, что влажу в чужую тему, но вопрос по теме вроде ...

Из того, что я находил, то декодирование блочных кодов по МАР-алгоритму (мягкое решение) лучше всего расписано в приложенном документе (стр. 9-11) и у Moon'а (стр. 663). Но там все также предполагается построение решетки на основе входного символа. В приложении есть подраздел, в котором указывается, насчет построения решетки и насчет 2 конечных состояний - этот момент я пока не понимаю (даже несмотря на то, что есть рисунок - вопросы именно по этим 2 состояниям в основном). + Там интересный вывод окончательной формулы для вычислений (выражение 63).
Может мне кто-то пояснить и как быть если блок например 128х128 - количество решеток ооочень большое получается...

Чейз (2 вариант/алгоритм) в этом плане как-то по проще(понятней что-ли), но исправляющая способность у него ниже.

Может кто-то поделиться понятным алгоритмом для декодирования блочных кодов (мягкое решение по входу)...
Прикрепленные файлы
Прикрепленный файл  hagenauer.pdf ( 2.25 мегабайт ) Кол-во скачиваний: 92
 


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
andyp
сообщение Dec 28 2014, 23:36
Сообщение #16


Местный
***

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



Цитата(Maverick @ Dec 28 2014, 23:26) *
В приложении есть подраздел, в котором указывается, насчет построения решетки и насчет 2 конечных состояний - этот момент я пока не понимаю (даже несмотря на то, что есть рисунок - вопросы именно по этим 2 состояниям в основном).

Глубоко копаешь wink.gif .
Сам метод построения решетки блочного кода по проверочной матрице описан в книжке Lin Costello Error Control Coding Fundamentals and Applications (только 2е издание). Скачать ее можно здесь
http://bookzz.org/md5/8032998F071B09E087B9E8D81E7FFC1F
Тебе потребуется глава 9, а именно секция 9.5. Но хочу предупредить сразу - чтение не из легких.
Если кратко, получается, что код представляется (n+1)-секционной решеткой, метки ветвей соответствуют закодированным битам, метки состояний - линейная комбинация столбцов проверочной матрицы и кодовых бит, по которым пришли в это состояние. Очевидно, что n-ое состояние решетки будет единственным и будет состоять из (n-k) нулей по свойству проверочной матрицы. 0-е состояние - тоже 0. Из него начинаем.

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

Цитата
Может мне кто-то пояснить и как быть если блок например 128х128 - количество решеток ооочень большое получается...

Чейз (2 вариант/алгоритм) в этом плане как-то по проще(понятней что-ли), но исправляющая способность у него ниже.


Именно поэтому чистый MAP для длинных блочных кодов не используется. Структура решетки не позволяет.

Цитата
Может кто-то поделиться понятным алгоритмом для декодирования блочных кодов (мягкое решение по входу)...


В книжке есть секция 10, написанная проф. Fossorier. Там приведены кое-какие алгоритмы. Может, часть из них окажется интересной.

Сообщение отредактировал andyp - Dec 28 2014, 23:39
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 29 2014, 09:48
Сообщение #17


я только учусь...
******

Группа: Модераторы
Сообщений: 3 447
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(andyp @ Dec 29 2014, 01:36) *
Глубоко копаешь wink.gif .
Сам метод построения решетки блочного кода по проверочной матрице описан в книжке Lin Costello Error Control Coding Fundamentals and Applications (только 2е издание). Скачать ее можно здесь
http://bookzz.org/md5/8032998F071B09E087B9E8D81E7FFC1F
Тебе потребуется глава 9, а именно секция 9.5. Но хочу предупредить сразу - чтение не из легких.
Если кратко, получается, что код представляется (n+1)-секционной решеткой, метки ветвей соответствуют закодированным битам, метки состояний - линейная комбинация столбцов проверочной матрицы и кодовых бит, по которым пришли в это состояние. Очевидно, что n-ое состояние решетки будет единственным и будет состоять из (n-k) нулей по свойству проверочной матрицы. 0-е состояние - тоже 0. Из него начинаем.

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



Именно поэтому чистый MAP для длинных блочных кодов не используется. Структура решетки не позволяет.



В книжке есть секция 10, написанная проф. Fossorier. Там приведены кое-какие алгоритмы. Может, часть из них окажется интересной.

спасибо за объяснение... a14.gif
тогда и махlog-map тоже не подходит.

А какой же алгоритм брать для использования - чейза или есть другие по лучше алгоритмы?


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
andyp
сообщение Dec 29 2014, 10:13
Сообщение #18


Местный
***

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



Цитата(Maverick @ Dec 29 2014, 12:48) *
А какой же алгоритм брать для использования - чейза или есть другие по лучше алгоритмы?


Для длинных кодовых блоков и скорости, близкой к 1/2?

Общего рецепта нет. Чейз для длинных кодов как-то тоже не очень - у него сложность тоже экспоненциальная, просто растет медленнее. Народ идет по пути синтеза хорошо декодируемых известными алгоритмами кодов. LDPC хорошо декодируются по графу итеративно. BTC - опять итеративное декодирование простых составных кодов. Как-то так. "Итеративно" - видимо ключевое слово на сегодяншний день. Есть еще алгоритмы мягкого декодирования Рида-Соломона, но я с ними не разбирался.
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 29 2014, 10:58
Сообщение #19


я только учусь...
******

Группа: Модераторы
Сообщений: 3 447
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(andyp @ Dec 29 2014, 12:13) *
Для длинных кодовых блоков и скорости, близкой к 1/2?

Общего рецепта нет. Чейз для длинных кодов как-то тоже не очень - у него сложность тоже экспоненциальная, просто растет медленнее. Народ идет по пути синтеза хорошо декодируемых известными алгоритмами кодов. LDPC хорошо декодируются по графу итеративно. BTC - опять итеративное декодирование простых составных кодов. Как-то так. "Итеративно" - видимо ключевое слово на сегодяншний день. Есть еще алгоритмы мягкого декодирования Рида-Соломона, но я с ними не разбирался.

Да, для блоковых кодов до (128*128)*(128*128) и до 3D: (128*128)*(128*128)*(64*64)
Длинные эти коды или нет я не знаю sm.gif
Интересуют именно алгоритмы мягкого декодирования
Момент итеративности(количества итераций) сейчас можно пока опустить...


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
Serg76
сообщение Dec 29 2014, 12:13
Сообщение #20


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

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



Цитата(Maverick @ Dec 29 2014, 13:48) *
спасибо за объяснение... a14.gif
тогда и махlog-map тоже не подходит.

А какой же алгоритм брать для использования - чейза или есть другие по лучше алгоритмы?

при правильном подходе Чейз дает весьма неплохие результаты даже для кодов типа [128x128], результат получается даже на уровне AHA, можно и другие алгоритмы попробовать, как-то уже с Вами обсуждали здесь, даже кое-что высылал. посмотрите в сторону мажоритарного декодера, для расширенных кодов Хемминга, о которых, как я понимаю, идет речь, сложность реализации будет невелика (для этих кодов каждый бит может быть представлен 4-мя уравнениями), а эффективность будет находиться где-то на уровне Чейза. к уже упомянутым алгоритмам можно еще добавить семейство вероятностных алгоритмов BPA (Belief Propagation Algorithm) или SPA (SumProduct Algorithm) алгоритмов и их аппроксимации на основе все той же алгебры логарифмов правдоподобия, но опять же, сложность реализации будет на уровне MAPa. а MAP, как правильно сказали, будет тяжеловат для кодов типа [128x128], хотя для [64x64] еще приемлемо.
Go to the top of the page
 
+Quote Post
andyp
сообщение Dec 29 2014, 13:02
Сообщение #21


Местный
***

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



Цитата(Maverick @ Dec 29 2014, 13:58) *
Да, для блоковых кодов до (128*128)*(128*128) и до 3D: (128*128)*(128*128)*(64*64)
Длинные эти коды или нет я не знаю sm.gif
Интересуют именно алгоритмы мягкого декодирования
Момент итеративности(количества итераций) сейчас можно пока опустить...


Что ты понимаешь под (128*128)? Перемножение двух скобочек - это продакт код?

Сложность алгоритма Чейза 2 растет (ну и всех основанных на нем алгоритмов SISO) экспоненциально от d/2. Если у тебя например 128-битный код Хамминга, то у него d=3 и декодировать его - плевое дело. Если будешь его декодировать по решетке, то в каждой секции будет не больше 2^7 состояний (количество состояний в решетке будет пропорционально 2^(n-k) или 2^k, смотря что меньше), так что MAP декодирование для составных кодов, остнованных на кодах Хемминга, опять же возможно для широкого диапазона битовых скоростей.

Есть еще всякие алгоритмы типа recursive MLD и итеративное декодирование по minimum weight subtrellis, но все они зависят от структуры кода.

Наверное, я не про то пишу и все-таки и не понимаю вопроса.
Go to the top of the page
 
+Quote Post
Serg76
сообщение Dec 29 2014, 13:23
Сообщение #22


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

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



Цитата(andyp @ Dec 29 2014, 17:02) *
Что ты понимаешь под (128*128)? Перемножение двух скобочек - это продакт код?

По всей видимости 2D TPC, где в качестве компонентных используются расширенные коды Хемминга или же, по-другому, (128, 120)x(128,120)
Go to the top of the page
 
+Quote Post
andyp
сообщение Dec 29 2014, 13:55
Сообщение #23


Местный
***

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



Цитата(Serg76 @ Dec 29 2014, 16:23) *
По всей видимости 2D TPC, где в качестве компонентных используются расширенные коды Хемминга или же, по-другому, (128, 120)x(128,120)


Тогда мой ответ про Хемминга релевантен. Для MAP декодирования наибольшую проблему составляет скорость ~1/2 - наиболее сложная решетка. Да и для Чейза сложность с ростом кодового расстояния увеличится.
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 29 2014, 15:39
Сообщение #24


я только учусь...
******

Группа: Модераторы
Сообщений: 3 447
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(Serg76 @ Dec 29 2014, 15:23) *
По всей видимости 2D TPC, где в качестве компонентных используются расширенные коды Хемминга или же, по-другому, (128, 120)x(128,120)

совершенно верно
спасибо...
Просто я думал вначале сделать декодирование блока например (128*120), а потом уже перенести на 2D/3D TPC код.
Алгоритм же остается тот же...

andyp спасибо за помощь


Все равно я не понимаю как достигаются такие высокие скорости у AHA декодирования
- 311 Mbits/sec TPC Encoder/Decoder IC
КАК???


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
Serg76
сообщение Dec 29 2014, 16:28
Сообщение #25


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

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



Цитата(Maverick @ Dec 29 2014, 19:39) *
совершенно верно
спасибо...
Просто я думал вначале сделать декодирование блока например (128*120), а потом уже перенести на 2D/3D TPC код.
Алгоритм же остается тот же...

естественно, за исключением того, что кроме мягкого входа еще нужен будет и мягкий выход )
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 29 2014, 19:29
Сообщение #26


я только учусь...
******

Группа: Модераторы
Сообщений: 3 447
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(Serg76 @ Dec 29 2014, 18:28) *
естественно, за исключением того, что кроме мягкого входа еще нужен будет и мягкий выход )

да, тогда алгоритм Чейза не подходит...
из-за этого начал смотреть на max log-map алгоритм, но и с ним возникли проблемы... sad.gif
а другого алгоритма я не знаю....


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
Serg76
сообщение Dec 29 2014, 20:53
Сообщение #27


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

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



Цитата(Maverick @ Dec 29 2014, 23:29) *
да, тогда алгоритм Чейза не подходит...
из-за этого начал смотреть на max log-map алгоритм, но и с ним возникли проблемы... sad.gif
а другого алгоритма я не знаю....

с чего Вы это взяли? все алгоритмы, о которых я упоминал способны генерировать мягкий выход
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 29 2014, 21:40
Сообщение #28


я только учусь...
******

Группа: Модераторы
Сообщений: 3 447
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(Serg76 @ Dec 29 2014, 14:13) *
при правильном подходе Чейз дает весьма неплохие результаты даже для кодов типа [128x128], результат получается даже на уровне AHA, можно и другие алгоритмы попробовать, как-то уже с Вами обсуждали здесь, даже кое-что высылал. посмотрите в сторону мажоритарного декодера, для расширенных кодов Хемминга, о которых, как я понимаю, идет речь, сложность реализации будет невелика (для этих кодов каждый бит может быть представлен 4-мя уравнениями), а эффективность будет находиться где-то на уровне Чейза. к уже упомянутым алгоритмам можно еще добавить семейство вероятностных алгоритмов BPA (Belief Propagation Algorithm) или SPA (SumProduct Algorithm) алгоритмов и их аппроксимации на основе все той же алгебры логарифмов правдоподобия, но опять же, сложность реализации будет на уровне MAPa. а MAP, как правильно сказали, будет тяжеловат для кодов типа [128x128], хотя для [64x64] еще приемлемо.

погорячился...
попробую посмотреть в сторону мажоритарного декодера...
ЗЫ Просьба если не затруднит вышлите мне еще раз - не могу найти у себя на винте sad.gif
Вот это читаю...

На 3 странице

Цитата(Serg76 @ Jul 22 2010, 18:38) *
MAP (maximum-a-posteriori) и его аппроксимации LOG-MAP и MAX-LOG-MAP. AHA так и делает (например, чип AHA4540)


вопрос как?

количество метрик для (128*120) очень большое получается - как обойти этот момент?


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
Serg76
сообщение Dec 29 2014, 21:48
Сообщение #29


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

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



Цитата(Maverick @ Dec 30 2014, 01:40) *
погорячился...
попробую посмотреть в сторону мажоритарного декодера...
ЗЫ Просьба если не затруднит вышлите мне еще раз - не могу найти у себя на винте sad.gif

ссылка мертвая sad.gif, уже не помню, что я там выкладывал, надо собирать заново, пока можно спросить у des00, ему тоже высылал
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 29 2014, 22:25
Сообщение #30


я только учусь...
******

Группа: Модераторы
Сообщений: 3 447
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(Serg76 @ Dec 29 2014, 23:48) *
ссылка мертвая sad.gif, уже не помню, что я там выкладывал, надо собирать заново, пока можно спросить у des00, ему тоже высылал

знаю, прежде чем попросить проверил ...
И все равно я не понимаю как сделано тут , чтобы достичь таких высоких скоростей обработки и повторить такое...
Цитата
Four-SISO option achieves a data rate of 155 Mbps with five iterations using (64,57)^2 code




--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
Serg76
сообщение Dec 30 2014, 00:33
Сообщение #31


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

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



Цитата(Maverick @ Dec 30 2014, 01:40) *
вопрос как?

количество метрик для (128*120) очень большое получается - как обойти этот момент?

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

Порядка 10 Мбит/с у меня получалось на персоналке для TPC 3/4 при 5-ти итерациях, применял Чейза.
Go to the top of the page
 
+Quote Post
des00
сообщение Dec 30 2014, 03:42
Сообщение #32


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(Maverick @ Dec 30 2014, 06:25) *
знаю, прежде чем попросить проверил ...

То что вы спрашивали помню, а вот то что отсылал нет sm.gif
Цитата
чтобы достичь таких высоких скоростей обработки и повторить такое...

Не совсем понимаю в чем проблема, там же 4 декодера работают параллельно. Обрабатывается сразу по 4 строки и 4 столбца, при этом как я понимаю работают не побитно, а пословно. Пока совершенно не ориентируюсь в 2D TPC кодах, но если скорость кодирования высокая, то думаю что это может очень быстро работать.

судя по доке на 150МГц они дают 45 мегабит на декодер, итого 3 такта на бит. 4 декодера с запасом.


--------------------
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 30 2014, 09:50
Сообщение #33


я только учусь...
******

Группа: Модераторы
Сообщений: 3 447
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(des00 @ Dec 30 2014, 05:42) *
То что вы спрашивали помню, а вот то что отсылал нет sm.gif

Не совсем понимаю в чем проблема, там же 4 декодера работают параллельно. Обрабатывается сразу по 4 строки и 4 столбца, при этом как я понимаю работают не побитно, а пословно. Пока совершенно не ориентируюсь в 2D TPC кодах, но если скорость кодирования высокая, то думаю что это может очень быстро работать.

судя по доке на 150МГц они дают 45 мегабит на декодер, итого 3 такта на бит. 4 декодера с запасом.

спасибо...
не отсылали, я Вам тогда не ответил, решил сам покопать... sm.gif


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
des00
сообщение Jan 19 2015, 10:09
Сообщение #34


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Глупый вопрос. Почему в RSС кодах не учитывается extrinsic информация о проверочных битах. Понятно что между декодерами передавать LLR проверочных битов не имеет смысла, но в пределах одного декодера между итерациями почему не воспользоваться выходными LLR метриками проверочных бит. В качестве примера вот код из CML
Код
for it = 1:max_iterations
    inx1 = X + inner_extr;
    [outx1, outz1]=DuobinaryCRSCDecode( inx1, inz1, poly, decoder_type);
    
    llrx1 = outx1 - inner_extr;
    inx2(1:3*N) = llrx1( code_interleaver_GF4);
    [outx2, outz2, out_info]=DuobinaryCRSCDecode( inx2, inz2, poly, decoder_type);
    detected_data(code_interleaver.info_intl) = (out_info>0)+0;
    errors(it)= sum( sum(abs(detected_data - data)));
    if (errors(it) == 0)
        break;
    else
        inner_extr(code_interleaver_GF4) = outx2 - inx2;
    end
end

видно что в качестве inz1/inz2 всегда используются канальные LLR, хотя outz1/outz2 - метрики с учетом влияния решетки.
или код с http://the-art-of-ecc.com/8_Iterative/index.html
Код
   for (int c=0;c<ITERATIONS;c++)
   {
    // k from 0 to N-1 instead of 1 to N
    for (int k=0;k<size;k++)
       {
       // calculate the gamma(s',s);
       for (int input=0;input<2;input++)
        {
        double uk = (input == 0) ? -1.0 : 1.0;

              for (int s=0;s<numstates;s++)
             {
             double xk = (output[input][s] == 0) ? -1.0 : 1.0;

         gammaE[0][input][k][s]=exp(0.5*Lc*parity1[k]*xk);
         gamma[0][input][k][s]
                      = exp(0.5*uk*(L[1][k]+Lc*mesg[k]))*gammaE[0][input][k][s];
             }
          }
       }
.....
       // calculate the gamma(s',s);
       for (int input=0;input<2;input++)
        {
        double uk = (input == 0) ? -1.0 : 1.0;

              for (int s=0;s<numstates;s++)
                {
                double xk = (output[input][s] == 0) ? -1.0 : 1.0;

            gammaE[1][input][k][s] = exp(0.5*Lc*parity2[k]*xk);
            gamma[1][input][k][s] = exp(0.5*uk*(L[0][k]+Lc*mesg[k]))
                                                     * gammaE[1][input][k][s];
                }
             }
       }

также parity1/parity2 используются всегда как есть


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Jan 19 2015, 12:14
Сообщение #35


Местный
***

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



Цитата(des00 @ Jan 19 2015, 13:09) *
Глупый вопрос. Почему в RSС кодах не учитывается extrinsic информация о проверочных битах. Понятно что между декодерами передавать LLR проверочных битов не имеет смысла, но в пределах одного декодера между итерациями почему не воспользоваться выходными LLR метриками проверочных бит.


Апостериорные вероятности проверочных бит не добавляют полезной информации. Вся инфа, выцепленная из структуры кода, уже учтена в экстринсиках систематических бит. Они определяют вероятности состояний решетки и, соответственно переходов по ней, из которых рассчитываются апостериорные вероятности того или иного проверочного бита.
Go to the top of the page
 
+Quote Post
des00
сообщение Jan 19 2015, 13:25
Сообщение #36


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Jan 19 2015, 20:14) *
Апостериорные вероятности проверочных бит не добавляют полезной информации. Вся инфа, выцепленная из структуры кода, уже учтена в экстринсиках систематических бит. Они определяют вероятности состояний решетки и, соответственно переходов по ней, из которых рассчитываются апостериорные вероятности того или иного проверочного бита.

Понял, как самому в голову не пришло sm.gif Тогда вопросы - следствие:
1. Тогда зачем в некоторых примерах рассчитывают LLR проверочных бит и принимают решение о проверочных битах? Только ради того что бы посчитать BER методом обратного кодирования?
2. В таком случае можно же сократить количество вычислений при итерациях, вычислив gammaE[0][input][k][s]=exp(0.5*Lc*parity1[k]*xk); один раз при первом проходе?


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Jan 19 2015, 15:23
Сообщение #37


Местный
***

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



Цитата(des00 @ Jan 19 2015, 16:25) *
Понял, как самому в голову не пришло sm.gif Тогда вопросы - следствие:
1. Тогда зачем в некоторых примерах рассчитывают LLR проверочных бит и принимают решение о проверочных битах? Только ради того что бы посчитать BER методом обратного кодирования?


Не знаю.

Цитата
2. В таком случае можно же сократить количество вычислений при итерациях, вычислив gammaE[0][input][k][s]=exp(0.5*Lc*parity1[k]*xk); один раз при первом проходе?


Давай рассмотрим BCJR без логарифмов. В этом случае gamma - вероятность перехода из состояния s_in в состояние s_out решетки. Пусть переходу соответствует информационный бит in (их может быть не один) и проверочный бит , coded (их тоже может быть не один)

gamma(s_in, s_out) = P_appriory(in) * P_extrinsic(in) * P_appriory(coded).

P_appriory(in) * P_appriory(coded) можно посчитать заранее, это не меняется между итерациями. P_extrinsic(in) - меняется.
Go to the top of the page
 
+Quote Post
andyp
сообщение Jan 21 2015, 08:37
Сообщение #38


Местный
***

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



Подумал на счет пункта 1 - LLR проверочных бит могут потребоваться для итеративной демодуляции-выравнивания.
Go to the top of the page
 
+Quote Post
smoke_111
сообщение Jan 21 2015, 09:42
Сообщение #39


Участник
*

Группа: Участник
Сообщений: 40
Регистрация: 9-09-10
Из: москва
Пользователь №: 59 392



или для демодуляции и декодировании в многоуровневых сигнально-кодовых конструкциях.
Go to the top of the page
 
+Quote Post
des00
сообщение Jan 22 2015, 09:06
Сообщение #40


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Jan 19 2015, 22:23) *
P_appriory(in) * P_appriory(coded) можно посчитать заранее, это не меняется между итерациями. P_extrinsic(in) - меняется.

Это и имел в виду, похоже что в сети полно декодеров, назову их "каноническими", которые показывают работу алгоритма и не заботятся о производительности. Все остальное "пилите шура, пилите" (с) sm.gif

Цитата(andyp @ Jan 21 2015, 15:37) *
Подумал на счет пункта 1 - LLR проверочных бит могут потребоваться для итеративной демодуляции-выравнивания.

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

Цитата(smoke_111 @ Jan 21 2015, 16:42) *
или для демодуляции и декодировании в многоуровневых сигнально-кодовых конструкциях.

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


--------------------
Go to the top of the page
 
+Quote Post
smoke_111
сообщение Jan 23 2015, 08:08
Сообщение #41


Участник
*

Группа: Участник
Сообщений: 40
Регистрация: 9-09-10
Из: москва
Пользователь №: 59 392



я имею в виду схемы наподобии trellis-coded modulation на основе разбиения Ангербёка(Ungerboek), где для демодуляции бит следующего уровня нужны все данные с предыдущего.
Go to the top of the page
 
+Quote Post
andyp
сообщение Jan 23 2015, 08:49
Сообщение #42


Местный
***

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



Цитата(smoke_111 @ Jan 23 2015, 11:08) *
я имею в виду схемы наподобии trellis-coded modulation на основе разбиения Ангербёка(Ungerboek), где для демодуляции бит следующего уровня нужны все данные с предыдущего.


Ну да, для BCM (BICM) мягкий выход проверочных бит нужен.
Go to the top of the page
 
+Quote Post
smoke_111
сообщение Jan 23 2015, 13:09
Сообщение #43


Участник
*

Группа: Участник
Сообщений: 40
Регистрация: 9-09-10
Из: москва
Пользователь №: 59 392



точно, спасибо, забыл как это называется.
Go to the top of the page
 
+Quote Post
des00
сообщение Jan 26 2015, 06:45
Сообщение #44


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Перевожу модель в фиксед поинт. Есть глупый вопрос: в документе ETSI TR 101 790 V1.4.1 указаны рекомендации
Цитата
It has been found in one implementation, using Sub-MAP and at Packet Error Ratio (PER) in the region of 10е-5, that a 3-bit quantization entails a penalty of 0,2 dB compared to a 4-bit quantization. It can be further shown, by simulation, that increasing from 4 bits to 5 bits results in no more than 0,1 dB additional coding gain.

Насколько я понимаю речь идет о квантовании LLR метрик битов. Изучение других материалов показало, что 1 бит под дробную часть не эффективно, минимально рекомендуемое 2 бита. Делаю вывод, что в случае 4-х бит речь идет о формате представления чисел s2.2. Т.е. знаковое число, 2 бита под целую часть и 2 бита под дробную. В таком случае диапазон LLR метрик битов -4.00 ... +3.75 (вероятность нуля 0.98... вероятность единицы 0.97). Эти значения как раз совпадают со значением LLR битов нормированного QPSK созвездия -+1 -+1i, при попадании точно в точку. Тут все понятно. Нормируем созвездие на эквалайзере/ару, считаем евклидовы метрики, делаем ограничение на уровень -4...3.75.

Чуть ниже в этом же документе написано
Цитата
Measurements, using samples from a real demodulator with Automatic Gain Control, have put into evidence that the position of the "sample clouds" within the quantizer range could be optimized for Turbo decoding. One implementation uses the following rule-of-thumb: "multiply the analogue samples of the demodulator by a constant so that after 4-bit quantization, the average of the unsigned values is equal to Rate × 8, Rate being the Turbo code rate (6/7, 4/5, 3/4, etc.)

И тут у меня взрывается мозг. Судя по доке, рекомендуемые уровни для кодирования [1/3 1/2 2/3 3/4 4/5 6/7] = [2.6 4.0 5.3 6.0 6.4 6.8]. Первый вопрос почему не нормируют созвездие, ведь ару это умножение на константу, сигнал умножается вместе с шумом? Второй вопрос, судя по всему предполагается квантование сигнала в формате s3.0, но в таком случае диапазон чисел -8...+7, т.е. при кодировании 6/7, они ставят созвездие почти в насыщение квантователя. В чем тайный смысл сего действа ?


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Jan 26 2015, 16:54
Сообщение #45


Местный
***

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



Цитата(des00 @ Jan 26 2015, 09:45) *
Первый вопрос почему не нормируют созвездие, ведь ару это умножение на константу, сигнал умножается вместе с шумом?


Давай сначала - что такое канальные LLR (случай BPSK,AWGN)

LLR = log(p(x=1|r)/p(x = 0|r)) = log(exp(-(r-a)^2/sigma^2)/exp(-(r+a)^2/sigma^2)) =
=4*a/sigma^2*r;

r - сигнал на входе демаппера;
sigma^2 - дисперсия шума
a - точка, соответствующая чистому сигналу на входе приемника (фактически, это мат. ожидание абс. величины сигнала на выходе приемника).

АРУ на входе демаппера увеличит в К_agc раз sigma^2 и a, поэтому формула для LLR не изменится. Т.е. это математически это все равно - скалить сигнал на входе или созвездие в демаппере.

Цитата
Второй вопрос, судя по всему предполагается квантование сигнала в формате s3.0, но в таком случае диапазон чисел -8...+7, т.е. при кодировании 6/7, они ставят созвездие почти в насыщение квантователя. В чем тайный смысл сего действа ?


На счет 3.0 vs 2.1 - если рассмотреть алгоритм MAXLOG-MAP, то он не чувствителен к постоянному множителю в канальных LLR, т.е. суть вопроса от меня ускользает - можно отскалить вход как это будет удобно. Именно поэтому при реализации смело плюют на a/sigma^2 в знаменателе канальных LLR, если диспресия шума постоянна на кодовом блоке.

Давай теперь перейдем к квантованию. Сначала проще ограничение на входе рассмотреть. Мой опыт говорит, что ограничение на входе декодера полезно даже без квантования. Фактически оно приводит к тому, что в декодер попадает меньше шума, экстремальные всплески которого просто срезаются ограничителем. Я обычно выбираю уровень ограничения, равный a+(1.5...2)*sigma. a/sigma - худший рабочий SNR декодера. Авторы рекомендаций используют мало уровней квантования, так что им нужно сбалансировать шум квантования и шум от ограничения динамического диапазона входа ограничителем. Для больших скоростей они посчитали, что дисперсия шума на входе будет меньше (рабочая точка декодера смещается вправо по шкале SNR) и потому решили сузить динамический диапазон относительно +/- a и уменьшить шум квантования малых LLR. Видимо, провели моделирование какое-то, чтобы подтвердить результаты.
Go to the top of the page
 
+Quote Post
des00
сообщение Jan 27 2015, 05:52
Сообщение #46


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Jan 27 2015, 00:54) *
Т.е. это математически это все равно - скалить сигнал на входе или созвездие в демаппере.
...
суть вопроса от меня ускользает - можно отскалить вход как это будет удобно.

Согласен с вами во всем, похоже вопрос задал не совсем понятно. Задам с графическим материалом.
На рисунке qpsk - классический QPSK, с точками {4,4} и SNR 5дб, по стандарту так должно быть отмасштабировано созвездие для кодирования 1/2. На рисунке qpsk_sat тоже созведие, но после ограничения диапазона [-8,7]. Видно что такое ограничение не особо критично. На рисунке qpsk_6by7 созвездие перед ограничением отмасштабировано с коэффициентом (6/7)/(1/2). Видно что большая часть точек, ушла в зону ограничения. Это я и назвал термином "насыщение квантователя". Т.е. большую часть статистической информации тупо выкинули.
Цитата
что ограничение на входе декодера полезно даже без квантования.

Да, вы про это уже писали. Возражений тут никаких, единственное что уровень ограничения в ПЛИС я делаю меньше, т.е. для QAM16 с уровнями 1 и 3, беру 2 бита запаса в сигнале в ару и перед декодированием ограничиваю по уровню 4, мне так проще в ПЛИС.

Цитата
Видимо, провели моделирование какое-то, чтобы подтвердить результаты.

Похоже что вы правы, сам не додумался. ИМХО это сильно на шаманство похоже. Вырезать актуальную информацию из канала, вместо того что бы 1 бит в метрику накинуть или нелийнейное квантование сделать.
Эскизы прикрепленных изображений
Прикрепленное изображение
Прикрепленное изображение
Прикрепленное изображение
 


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Jan 27 2015, 09:19
Сообщение #47


Местный
***

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



Цитата(des00 @ Jan 27 2015, 08:52) *
Т.е. большую часть статистической информации тупо выкинули.


Тут стоит оценить дисперсию ошибки квантования vs дисперсия ошибки ограничения на рабочих SNR декодера для разных скоростей. Хотя даже это не будет критерием "лучшести" квантователя из-за нелинейности декодера. Нужно на BER смотреть.

Цитата
Похоже что вы правы, сам не додумался. ИМХО это сильно на шаманство похоже. Вырезать актуальную информацию из канала, вместо того что бы 1 бит в метрику накинуть или нелийнейное квантование сделать.


Я тоже за дополнительный бит sm.gif, но я ж софтверщик - он мне фактически ничего не стоит. В железе, думаю, сложность будет линейно расти с количеством входных бит. Авторы электричество и вентили экономят вовсю.
Go to the top of the page
 
+Quote Post
des00
сообщение Jan 28 2015, 08:13
Сообщение #48


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Созрел следующий вопрос: метрики состояний проходят через процедуру нормализации. А как поступают с Lextrinsic и выходными LLR битов ? Судя по результатам моделирования, при сходимости декодера, Lextrinsic, а за ним и LLR выходных символов/битов имеют тенденцию к росту от итерации к итерации. Но, как я понимаю, нормализовать их нельзя, а логичнее использовать ограничение на определенном уровне. Правда упоминание об этом в статьях я не нашел, так ли это ?


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Jan 28 2015, 09:26
Сообщение #49


Местный
***

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



Видел, что экстринсики скалили между итерациями (но не между полуитерациями) на что-то типа 0.8 - 0.9. Там же после первой итерации все равно их статистическая независимость нарушается и начинается сплошная магия.
Go to the top of the page
 
+Quote Post
des00
сообщение Jan 28 2015, 09:44
Сообщение #50


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Jan 28 2015, 16:26) *
Видел, что экстринсики скалили между итерациями (но не между полуитерациями) на что-то типа 0.8 - 0.9. Там же после первой итерации все равно их статистическая независимость нарушается и начинается сплошная магия.

да, где то в доке находил коэффициент 0.75, но это только для max-log-MAP алгоритма, для компенсации неидеальности аппроксимации логарифма суммы экспонент.


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Jan 28 2015, 12:07
Сообщение #51


Местный
***

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



Цитата(des00 @ Jan 28 2015, 12:44) *
да, где то в доке находил коэффициент 0.75, но это только для max-log-MAP алгоритма, для компенсации неидеальности аппроксимации логарифма суммы экспонент.


Я встречал другое объяснение - от итерации к итерации информация о бите уменьшается, поэтому вводят нечто типа OOC, чтобы учесть это уменьшение.
Go to the top of the page
 
+Quote Post
des00
сообщение Jan 28 2015, 15:42
Сообщение #52


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Jan 28 2015, 19:07) *
Я встречал другое объяснение - от итерации к итерации информация о бите уменьшается, поэтому вводят нечто типа OOC, чтобы учесть это уменьшение.

хмм, надо еще будет эту тему прошерстить.

В приложении матлабовский примитивный, без какой либо оптимизации, декодер dvb-rsc, часть функций сделана близко к железу, позволяет покрутить/посмотреть что и как считается, что куда идет, как себя ведут метрики и прочее sm.gif Содержит комментарии как что и куда. Перехожу к работе над HDL идеалкой.
Прикрепленные файлы
Прикрепленный файл  ctc.zip ( 12.61 килобайт ) Кол-во скачиваний: 39
 


--------------------
Go to the top of the page
 
+Quote Post
Maverick
сообщение Jan 28 2015, 20:09
Сообщение #53


я только учусь...
******

Группа: Модераторы
Сообщений: 3 447
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(des00 @ Jan 28 2015, 17:42) *
хмм, надо еще будет эту тему прошерстить.

В приложении матлабовский примитивный, без какой либо оптимизации, декодер dvb-rsc, часть функций сделана близко к железу, позволяет покрутить/посмотреть что и как считается, что куда идет, как себя ведут метрики и прочее sm.gif Содержит комментарии как что и куда. Перехожу к работе над HDL идеалкой.

спасибо...


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
des00
сообщение Jan 29 2015, 04:53
Сообщение #54


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(Maverick @ Jan 29 2015, 03:09) *
спасибо...

там я только немного "накосяпорил" когда считал оценочный FER (FEC Error Rate), затер некодированный BER. Только сейчас увидел, будете пробовать поправьте sm.gif


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Jan 29 2015, 08:56
Сообщение #55


Местный
***

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



Цитата(des00 @ Jan 28 2015, 18:42) *
Перехожу к работе над HDL идеалкой.


Поздравляю с завершением этапа beer.gif
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 3 2015, 15:34
Сообщение #56


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Jan 29 2015, 16:56) *
Поздравляю с завершением этапа beer.gif

Похоже где то я ошибся sad.gif Сделал идеалку на RTL, осознал откуда растут ноги у количества эффективных бит у метрик пар/ветвей/состояний/extinsic. Но? начал гонять и заметил расхождение в характеристиках декодера, по сравнению с используемым мной "референсным" документом. Документ в приложении, характеристики на странице 3 (466 страница документа). Набрел на него когда искал точки привязки BER для декодера(в других найденных документах приводился FER в качестве характеристик).

Первая мысль что используемый для моделирования в RTL генератор шума не верен. Отложил в сторону RTL. Взял матлабовский вариант без квантования, ограничений, честный Log Map и т.д. Тоже не бьются кривые с документом. Особенно если учесть тот факт, что в документе якобы рассмотрен Max Log Map без каких либо улучшений. Проверяю на QPSK, пакет длинной 64 пары, кодирование 1/3, 10 итераций. Пример расхождения характеристик : EbN0 = 2.5дб, в статье BER 5е-5, RTL код BER 4е-4, матлаб 2е-4.

Может кто нибудь поделиться ссылками на эталонные результаты или характеристиками своих декодеров? Интересует кривая для пакета 64 пары, кодирование 1/3, 8 итераций. Диапазон EbNo 0.5:0.5:4.

Прикрепленные файлы
Прикрепленный файл  Design_and_Implementation_of_Low_Power_Turbo_Encoder_for_DVB_RCS_Software_Radio.pdf ( 436.62 килобайт ) Кол-во скачиваний: 84
 


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Feb 4 2015, 11:53
Сообщение #57


Местный
***

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



Поделиться результатами не могу - давно было, так что нет под рукой ни результатов ни кода.

Посмотрел повнимательнее твой матлаб - есть один момент:

У тебя решетка циклическая, следовательно состояния решетки в начале и конце должны быть одинаковыми. Начинать нужно с альф. Доходишь до конца, используешь последние полученные альфы для инициализации (N+1)ых бет и идешь назад по решетке. Затем сохраняешь полученные 0ые беты для использования как 0ые альфы на следующей итерации.

Go to the top of the page
 
+Quote Post
des00
сообщение Feb 4 2015, 13:47
Сообщение #58


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(des00 @ Feb 3 2015, 22:34) *
Похоже где то я ошибся sad.gif

Ошибся в добавлении шума к сигналу в тесте на SV. Забыл про одну из типовых System Verilog gotcha, в результате при добавлении к сигналу шум становился не AWGN, со всеми вытекающими. Поправил это место и характеристики легли близко с "референсным" декодером в статье. Почему матлаб работает не так еще не понял, может быть сказывается количество бит. RTL гоняю на 8М бит(15 минут на тест), матлаб на 200К (это он ночь стоит, очень уж медленно он работает).

Цитата(andyp @ Feb 4 2015, 18:53) *
У тебя решетка циклическая, следовательно состояния решетки в начале и конце должны быть одинаковыми. Начинать нужно с альф. Доходишь до конца, используешь последние полученные альфы для инициализации (N+1)ых бет и идешь назад по решетке. Затем сохраняешь полученные 0ые беты для использования как 0ые альфы на следующей итерации.

Понял, проверю. Цикличность отдельно альф от бет я сделал основываясь на разделе в стандарте (в приложении). С бет начинал потому что планирую в железе делать sliding window с двумя движками для бет и одним для альф. Уж больно не хочется два раза массив данных перебирать.

Когда искал в чем косяк созрел такой вопрос. Насколько правомочно формирование метрик отсчета L1,L2 для дебитов по правилу:
L00 = 0, L01 = L2, L10 = L1, L11 = L1+L2. По идее это результат вычитания из метрик L01/L10/L11 метрики L00. Но тогда должно быть так :
исходные метрики L00 = -L1-L2, L01 = -L1 + L2, L10 = L1 - L2, L11 = L1+L2 и после вычитания получается L00 = 0, L01 = 2*L2, L10 = 2*L1, L11 = 2*(L1+L2).

Казалось бы постоянный множитель LLR алгоритму не принципиален, но ведь этот множитель задает распределение надежностей. Например пусть L1/L2 = 4, тогда честные метрики будут : L00 = -8, L01 = 0, L10 = 0, L11 = 8. "Расстояния" между метриками L01/L10/L11 и метрикой L00 будет 0/8/8/16. Тогда как по упрощенному правилу метрики будут L00 = 0, L01 = 4, L10 = 4, L11 = 8 и расстояния 0/4/4/8. Как более правильно? Или этом пренебрегают в виду того, что exp(-4) = 0.0183 и exp(-8) = 3.3546e-04?
Эскизы прикрепленных изображений
Прикрепленное изображение
 


--------------------
Go to the top of the page
 
+Quote Post
Mogwaika
сообщение Feb 4 2015, 16:08
Сообщение #59


Частый гость
**

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



Цитата(des00 @ Feb 4 2015, 17:47) *
Ошибся в добавлении шума к сигналу в тесте на SV. Забыл про одну из типовых System Verilog gotcha, в результате при добавлении к сигналу шум становился не AWGN, со всеми вытекающими. Поправил это место и характеристики легли близко с "референсным" декодером в статье. Почему матлаб работает не так еще не понял, может быть сказывается количество бит. RTL гоняю на 8М бит(15 минут на тест), матлаб на 200К (это он ночь стоит, очень уж медленно он работает).


Код запускаете напрямую или компилируете в mex или exe?
У меня для декодера компиляция дала прирост почти на порядок.
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 4 2015, 16:11
Сообщение #60


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(Mogwaika @ Feb 4 2015, 23:08) *
Код запускаете напрямую или компилируете в mex или exe?
У меня для декодера компиляция дала прирост почти на порядок.

Судя по всему напрямую, рылся в хелпе как скомпилировать в mex (в симулинке такое делать умею), а тут так и не разобрался.


--------------------
Go to the top of the page
 
+Quote Post
Grizzzly
сообщение Feb 4 2015, 17:07
Сообщение #61


Знающий
****

Группа: Свой
Сообщений: 565
Регистрация: 22-02-13
Пользователь №: 75 748



Цитата(des00 @ Feb 4 2015, 19:11) *
Судя по всему напрямую, рылся в хелпе как скомпилировать в mex (в симулинке такое делать умею), а тут так и не разобрался.

Посмотрите примеры по codegen.

По своему опыту скажу следующее: если в матлабовском коде используются в основном встроенные функции, которые хорошо векторизованы, то от генерации сишного кода будет даже проигрыш прмерно в 1.5-2 раза, если же присутствует множество вложенных циклов, условия, то будет выигрыш (у меня получалось от 1.5 до 20 раз для различных программ, Win7, 64 bit).

Сообщение отредактировал Grizzzly - Feb 4 2015, 17:08
Go to the top of the page
 
+Quote Post
smoke_111
сообщение Feb 4 2015, 18:32
Сообщение #62


Участник
*

Группа: Участник
Сообщений: 40
Регистрация: 9-09-10
Из: москва
Пользователь №: 59 392



Цитата(des00 @ Feb 4 2015, 16:47) *
Ошибся в добавлении шума к сигналу в тесте на SV. Забыл про одну из типовых System Verilog gotcha, в результате при добавлении к сигналу шум становился не AWGN, со всеми вытекающими. Поправил это место и характеристики легли близко с "референсным" декодером в статье. Почему матлаб работает не так еще не понял, может быть сказывается количество бит. RTL гоняю на 8М бит(15 минут на тест), матлаб на 200К (это он ночь стоит, очень уж медленно он работает).


Понял, проверю. Цикличность отдельно альф от бет я сделал основываясь на разделе в стандарте (в приложении). С бет начинал потому что планирую в железе делать sliding window с двумя движками для бет и одним для альф. Уж больно не хочется два раза массив данных перебирать.

Когда искал в чем косяк созрел такой вопрос. Насколько правомочно формирование метрик отсчета L1,L2 для дебитов по правилу:
L00 = 0, L01 = L2, L10 = L1, L11 = L1+L2. По идее это результат вычитания из метрик L01/L10/L11 метрики L00. Но тогда должно быть так :
исходные метрики L00 = -L1-L2, L01 = -L1 + L2, L10 = L1 - L2, L11 = L1+L2 и после вычитания получается L00 = 0, L01 = 2*L2, L10 = 2*L1, L11 = 2*(L1+L2).

Казалось бы постоянный множитель LLR алгоритму не принципиален, но ведь этот множитель задает распределение надежностей. Например пусть L1/L2 = 4, тогда честные метрики будут : L00 = -8, L01 = 0, L10 = 0, L11 = 8. "Расстояния" между метриками L01/L10/L11 и метрикой L00 будет 0/8/8/16. Тогда как по упрощенному правилу метрики будут L00 = 0, L01 = 4, L10 = 4, L11 = 8 и расстояния 0/4/4/8. Как более правильно? Или этом пренебрегают в виду того, что exp(-4) = 0.0183 и exp(-8) = 3.3546e-04?


Нормально, это не принципиально, по поводу цикличности, метод предложенный andyp хорош для больших длин ( позволяет не пересчитывать метрики каждую полуитерацию), для маленьких будет давать существенный проигрыш.
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 4 2015, 19:03
Сообщение #63


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(Grizzzly @ Feb 5 2015, 01:07) *
Посмотрите примеры

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

Цитата(smoke_111 @ Feb 5 2015, 02:32) *
Нормально, это не принципиально

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

Как раз успел прогнать разные варианты (альфа - бета, бета - альфа) на маленьких кодах, проигрыш виден не вооруженным взглядом. На больших еще не проверял.


--------------------
Go to the top of the page
 
+Quote Post
smoke_111
сообщение Feb 4 2015, 19:18
Сообщение #64


Участник
*

Группа: Участник
Сообщений: 40
Регистрация: 9-09-10
Из: москва
Пользователь №: 59 392



На больших все хорошо должно быть, если мне правильно вспоминается, то вариант от andyp, работает лучше чем вариант с предекодерами.
Go to the top of the page
 
+Quote Post
Mogwaika
сообщение Feb 4 2015, 20:01
Сообщение #65


Частый гость
**

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



Цитата(Grizzzly @ Feb 4 2015, 21:07) *
Посмотрите примеры по codegen.

По своему опыту скажу следующее: если в матлабовском коде используются в основном встроенные функции, которые хорошо векторизованы, то от генерации сишного кода будет даже проигрыш прмерно в 1.5-2 раза, если же присутствует множество вложенных циклов, условия, то будет выигрыш (у меня получалось от 1.5 до 20 раз для различных программ, Win7, 64 bit).


У меня даже декодер, оптимизированный под матричные операции для ускорения простого кода ускорился значительно.
Плюсом желательно использовать parfor, чтобы полностью загрузить процессор.
Далее можно скомпилировать exe с помощью mcc для запуска сразу на нескольких машинах с установленным mcr.
Go to the top of the page
 
+Quote Post
Serg76
сообщение Feb 5 2015, 07:47
Сообщение #66


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

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



Цитата(Mogwaika @ Feb 4 2015, 23:01) *
У меня даже декодер, оптимизированный под матричные операции для ускорения простого кода ускорился значительно.
Плюсом желательно использовать parfor, чтобы полностью загрузить процессор.
Далее можно скомпилировать exe с помощью mcc для запуска сразу на нескольких машинах с установленным mcr.

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

Цитата(Grizzzly @ Feb 4 2015, 20:07) *
Посмотрите примеры по codegen.

По своему опыту скажу следующее: если в матлабовском коде используются в основном встроенные функции, которые хорошо векторизованы, то от генерации сишного кода будет даже проигрыш прмерно в 1.5-2 раза, если же присутствует множество вложенных циклов, условия, то будет выигрыш (у меня получалось от 1.5 до 20 раз для различных программ, Win7, 64 bit).

Какая максимальная скорость достигнута в Вашей реализации?
Go to the top of the page
 
+Quote Post
Grizzzly
сообщение Feb 5 2015, 08:43
Сообщение #67


Знающий
****

Группа: Свой
Сообщений: 565
Регистрация: 22-02-13
Пользователь №: 75 748



Цитата(Serg76 @ Feb 5 2015, 10:47) *
Какая максимальная скорость (в битах данных или символах в сек.) получилась в итоге после всех оптимизаций и при каких режимах (тип кода, количество итераций, частота и тип процессора, использование SIMD, мультитрейдинга и др.)?

Турбо-декодер делал давно, для него не генерировал код. Описал полученные результаты на различных алгоритмах только в качестве примера по генерации mex-файлов. Из последнего: сейчас мне понадобилась собственная реализация алгоритма Витерби. В первом случае мне нужно только значение наилучшей метрики (оптимальные пути не ищутся, только вычисляются метрики), выигрыш получился минимум в 10 раз, на некоторых длинах блоков и при определенном числе состояний решетки в 15-20 раз. Для случая, когда декодер выдает оптимальный путь, выигрыш составил 1.5 раза (подозреваю, что как-то можно оптимизировать процесс копирования выживших путей). Процессор Intel Core 2 Duo, 3 GHz. Компилятор использовался VS 2010, наверное, от будь от Intel, результаты получились бы лучшими. Matlab 2014a 64 bit. Мне real-time не нужен, генерировал только для сокращения времени моделирвания.
Не подскажете, где можно прочитать по настройкам оптимизации?

Сообщение отредактировал Grizzzly - Feb 5 2015, 08:45
Go to the top of the page
 
+Quote Post
Mogwaika
сообщение Feb 5 2015, 09:30
Сообщение #68


Частый гость
**

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



Цитата(Serg76 @ Feb 5 2015, 11:47) *
Какая максимальная скорость (в битах данных или символах в сек.) получилась в итоге после всех оптимизаций и при каких режимах (тип кода, количество итераций, частота и тип процессора, использование SIMD, мультитрейдинга и др.)?

~300кб/с (свёрточный турбо на 4х битном регистре, rate 1/2, 10 итераций max-log-map, qpsk + awgn, Xeon E5-2620v2 2.10GHz, mcr 2014a 64bit)
Go to the top of the page
 
+Quote Post
Serg76
сообщение Feb 5 2015, 10:04
Сообщение #69


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

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



Цитата(Grizzzly @ Feb 5 2015, 11:43) *
Турбо-декодер делал давно, для него не генерировал код. Описал полученные результаты на различных алгоритмах только в качестве примера по генерации mex-файлов. Из последнего: сейчас мне понадобилась собственная реализация алгоритма Витерби. В первом случае мне нужно только значение наилучшей метрики (оптимальные пути не ищутся, только вычисляются метрики), выигрыш получился минимум в 10 раз, на некоторых длинах блоков и при определенном числе состояний решетки в 15-20 раз. Для случая, когда декодер выдает оптимальный путь, выигрыш составил 1.5 раза (подозреваю, что как-то можно оптимизировать процесс копирования выживших путей). Процессор Intel Core 2 Duo, 3 GHz. Компилятор использовался VS 2010, наверное, от будь от Intel, результаты получились бы лучшими. Matlab 2014a 64 bit. Мне real-time не нужен, генерировал только для сокращения времени моделирвания.
Не подскажете, где можно прочитать по настройкам оптимизации?

Ок, спасибо. Если немного отойти от темы, то выигрыш 1.5 раза - это сколько в битах и для какой относительной скорости кодирования и длины кодового ограничения? Кстати, алгоритм Витерби, точнее его вариант с генерацией мягкого выхода - SOVA, можно смело применять и для RCS кода, правда неизвестно еще будет ли выигрыш по скорости в сравнении с MAX-LOG-MAP, но по эффективности, конечно, хуже. По поводу Intel: прирост должен быть как на уровне компилятора, так и при использовании их примитивов - IPP, а по поводу настроек оптимизации имеется ввиду компилятор?

Цитата(Mogwaika @ Feb 5 2015, 12:30) *
~300кб/с (свёрточный турбо на 4х битном регистре, rate 1/2, 10 итераций max-log-map, qpsk + awgn, Xeon E5-2620v2 2.10GHz, mcr 2014a 64bit)

Спасибо, 4-х битный - это на 16 состояний как в RCS2?
Go to the top of the page
 
+Quote Post
Grizzzly
сообщение Feb 5 2015, 10:36
Сообщение #70


Знающий
****

Группа: Свой
Сообщений: 565
Регистрация: 22-02-13
Пользователь №: 75 748



Цитата(Serg76 @ Feb 5 2015, 13:04) *
Ок, спасибо. Если немного отойти от темы, то выигрыш 1.5 раза - это сколько в битах и для какой относительной скорости кодирования и длины кодового ограничения?

Это специфическая задача, аналогичная TCM. Пока что модуляция PAM-8, сверточные коды скорости 1/2. Различные полиномы (кодовые ограничения от 3 и до 7).
Цитата(Serg76 @ Feb 5 2015, 13:04) *
По поводу Intel: прирост должен быть как на уровне компилятора, так и при использовании их примитивов - IPP.

Понял, спасибо.
Go to the top of the page
 
+Quote Post
Mogwaika
сообщение Feb 5 2015, 10:59
Сообщение #71


Частый гость
**

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



Цитата(Serg76 @ Feb 5 2015, 14:04) *
Спасибо, 4-х битный - это на 16 состояний как в RCS2?


Да, на 16 из стандарта ECSS-E-ST-50-01C, длиной 1784.
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 6 2015, 11:34
Сообщение #72


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Первые результаты по RTL кодированию


--------------------
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 6 2015, 16:42
Сообщение #73


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Сел за синтезируемую RTL реализацию и сразу возник глупый вопрос:
функция генерации адресов перемежителя судя по всему не обратима (табличные реализации не рассматриваются), это делает не возможным предварительную подготовку результата декодирования полу-итерации на этапе записи ее результата в буфер. Следовательно нужно делать перемежение при чтении. Делать это отдельной операцией, перекладывая из буфера в буфер тривиально. Интересна реализация на лету.
В этом случае, насколько понимаю, есть проблема в генерации обратного порядка адресов чтения, которые необходимы для обратного прохода. И даже если бы такой проблемы не было, то была бы проблема расчета начальных адресов буфера для реализации sliding window когда бета считается первой (рассматриваем вариант отсутствия операции деления в целевой архитектуре). Логично в случае sliding window сначала вычислять альфу, складывая данные в LIFO, а потом считать бету одновременно с результатом. Теперь собственно вопрос: во всех материалах что я видел по sliding window, рассматривают вариант расчета беты, потом альфы. И нигде наоборот. Все делают перемежение отдельной операцией или все таки есть метод обращения функции генерации адреса ?


--------------------
Go to the top of the page
 
+Quote Post
smoke_111
сообщение Feb 6 2015, 17:28
Сообщение #74


Участник
*

Группа: Участник
Сообщений: 40
Регистрация: 9-09-10
Из: москва
Пользователь №: 59 392



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

Сообщение отредактировал smoke_111 - Feb 6 2015, 17:36
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 6 2015, 17:43
Сообщение #75


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(smoke_111 @ Feb 7 2015, 01:28) *
метод обращения функции генерации адреса есть, смотреть в сторону решения уравнений в модулярной форме, там в принципе ничего сложного. Да вроде никто не мешает сначала посчитать бету, а потом альфу и получается, что результирующие данные идут в прямом порядке (в общем спорный вопрос про логичность).

Хмм, может я не так задал вопрос. Рассмотрим пример : код длинной 64 пары, делаем перемежение на лету.
Первая полуитерация делается над данными как есть. альфа проходит по адресам 1:1:64, бета по адресам 64:-1:1. Просто реализуется на счетчике. Пишем результат тоже по адресам 1:1:64
Вторая полуитерация делается над данными после перемежения. альфа проходит по адресам 1, 10, 47, 56, 29, 38, 11, 20, 57 ...... 55, 0, 37, 46, 19, 28. Это тоже просто реализуется на счетчике + компаратор, вычитатель и сумматор. А вот бета должна пройти по адресам 28, 19, 46, 37, 0, 55, 18, 9..... 56, 47, 10, 1. Вот эти адреса уже требуют обращения функции генерации адреса. Вот тут бы заранее заполнить память в правильном порядке, что бы вторая полуитерация работала как первая. Это можно сделать либо отдельной процедурой перемежения(переписать данные из памяти результата первой полуитерации в память исходных данных второй), либо обращением адреса при записи результата первой полуитерации

Если делать забег в режиме sliding window сначала по альфе, то можно просто сохранить адреса вместе с данными в LIFO, потом при забеге по бета, расчет не потребуется, т.к. адрес уже посчитан и результат второй полуитерации можно записать в уже деперемеженном формате в результат.


--------------------
Go to the top of the page
 
+Quote Post
smoke_111
сообщение Feb 6 2015, 18:07
Сообщение #76


Участник
*

Группа: Участник
Сообщений: 40
Регистрация: 9-09-10
Из: москва
Пользователь №: 59 392



Прошу прощения я кажется запутался, я правильно понимаю ваш вопрос, вы хотите получить адреса данных после перемежения для бет в обратном порядке?
Go to the top of the page
 
+Quote Post
andyp
сообщение Feb 6 2015, 19:14
Сообщение #77


Местный
***

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



Цитата(smoke_111 @ Feb 6 2015, 21:07) *
Прошу прощения я кажется запутался, я правильно понимаю ваш вопрос, вы хотите получить адреса данных после перемежения для бет в обратном порядке?


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

Сообщение отредактировал andyp - Feb 6 2015, 19:23
Прикрепленные файлы
Прикрепленный файл  cheng_hung2008.pdf ( 269.7 килобайт ) Кол-во скачиваний: 50
 
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 7 2015, 07:42
Сообщение #78


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(smoke_111 @ Feb 7 2015, 01:07) *
я правильно понимаю ваш вопрос, вы хотите получить адреса данных после перемежения для бет в обратном порядке?

да, именно так.

Цитата(andyp @ Feb 7 2015, 02:14) *
В приложенной статье утверждается, что аналогичная схема может быть использована для генерации индексов интерливера как в прямом так и в инверсном порядке.

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


--------------------
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 7 2015, 16:34
Сообщение #79


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Feb 7 2015, 03:14) *
В приложенной статье утверждается, что аналогичная схема может быть использована для генерации индексов интерливера как в прямом так и в инверсном порядке.

Цитата(des00 @ Feb 7 2015, 15:42) *
покурю внимательно

самое занятное что они правы, внимательно позырил на формулу и все встало на круги своя. Замена сложения на вычитание P0 в аккумуляторе и изменение адреса инициализации с 0 на P0*(N-1) % N дает искомый результат. Жаль только то, что под каждую длину нужен свой уникальный адрес инициализации wink.gif


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Feb 8 2015, 08:59
Сообщение #80


Местный
***

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



Цитата(des00 @ Feb 7 2015, 19:34) *
самое занятное что они правы, внимательно позырил на формулу и все встало на круги своя. Замена сложения на вычитание P0 в аккумуляторе и изменение адреса инициализации с 0 на P0*(N-1) % N дает искомый результат. Жаль только то, что под каждую длину нужен свой уникальный адрес инициализации wink.gif


Это не самая большая проблема. Проблема - обеспечить, чтобы параллельно работающие SISO модули не сталкивались при доступе к памяти экстринсиков. Вот статья про это на примере wimax. Может, будет интересно.


Прикрепленные файлы
Прикрепленный файл  martina2008.pdf ( 177.06 килобайт ) Кол-во скачиваний: 33
 
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 9 2015, 05:27
Сообщение #81


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Feb 8 2015, 16:59) *
Проблема - обеспечить, чтобы параллельно работающие SISO модули не сталкивались при доступе к памяти экстринсиков. Вот статья про это на примере wimax. Может, будет интересно.

статья немного путаная но занятная, но по кросс линкам ведет к статье A HIGH-SPEED MAP ARCHITECTURE WITH OPTIMIZED MEMORY SIZE AND POWER CONSUMPTION вот там яснее написано sm.gif

Попутно возник вопрос, почему все бьются за повышение параллелизма одной полуитерации. Положим есть 10 параллельно работающих движков, это требует наличия 10 ти портовых регистровых файлов. Ведь можно же уйти в глубину : те же 10 движков поставить последовательно в конвейер и развязать их двухпортовыми блочками памяти(при этом память под Lext можно заменить на память Lext + Ls). Да, задержка обработки вырастет, но пиковая производительность останется на том же уровне. Правда количество итераций произвольно менять будет сложнее.
Прикрепленные файлы
Прикрепленный файл  A_HIGH_SPEED_MAP_ARCHITECTURE_WITH_OPTIMIZED_MEMORY_SIZE_AND_POWER_CONSUMPTION.pdf ( 80.62 килобайт ) Кол-во скачиваний: 21
 


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Feb 9 2015, 09:48
Сообщение #82


Местный
***

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



Цитата(des00 @ Feb 9 2015, 08:27) *
Попутно возник вопрос, почему все бьются за повышение параллелизма одной полуитерации. Положим есть 10 параллельно работающих движков, это требует наличия 10 ти портовых регистровых файлов. Ведь можно же уйти в глубину : те же 10 движков поставить последовательно в конвейер и развязать их двухпортовыми блочками памяти(при этом память под Lext можно заменить на память Lext + Ls). Да, задержка обработки вырастет, но пиковая производительность останется на том же уровне. Правда количество итераций произвольно менять будет сложнее.


Потому что ты себе несколько не тот вопрос задаешь. Ты рассматриваешь задачу получения максимальной пропускной способности без ограничений, а надо с ограничениями wink.gif Вопрос должен быть таким - у меня есть максимум М движков, я жутко экономлю электричество (фактически, экономлю тактовую и память ). Какими выбрать М и тактовую, чтобы все же получить нужную пропускную способность для всех возможных размеров блоков?

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

Больше информации о том, как устроен декодер у Martinа, можно почерпнуть из прицепленной статьи. Предыдущая была только про интерливер.

Что касается граничных альф и бет для окна, они используют значения, полученные на предыдущей итерации.
Прикрепленные файлы
Прикрепленный файл  martina2008_1.pdf ( 427.08 килобайт ) Кол-во скачиваний: 33
 
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 9 2015, 16:48
Сообщение #83


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Feb 9 2015, 17:48) *
Что касается граничных альф и бет для окна, они используют значения, полученные на предыдущей итерации.

Вот как раз по этому вопросу мне не до конца понятно.
Реализовал модель декодера который работает по окну == размеру пакета. За один проход считает альфа и бета: читает метрики и экстинсики для двух пар, до середины пакета набирает состояния в память, после середины начинает вычислять выходные экстринсики для двух пар одновременно и пишет в память экстринсиков. Адреса записи не пересекаются, чтение с записью разведено латентностью обработки. Все должно более менее красиво лечь в ПЛИС, правда в качестве блочков памяти нужно будет из двухпортовок сделать память 2 порта на запись и 2 на чтение (как прикрутить однопортовку еще не задумывался). Сама решетка инициализируется на концах и вычисления идут по эталонной модели с первой итерации.

В многооконных декодерах, судя по одной из статей
Цитата
The algorithm is as following. First of all, the received data for each constituent codes are divided into several contiguous non-overlapping sub-blocks; so called windows. Then, each window is decoded separately in parallel using the BCJR algorithm. In other words, each window is a vector decoder. However, the initial values for alpha and beta variables come from previous iteration of adjacent windows. Since all the windows are being processed at the same time, in the next iteration the initial values are ready to load. Therefore, there is no extra processing needed for the initialization of state probabilities at each iteration. The size of windows is a very important parameter that will be discussed later. Fig. 3 shows the structure of the decoder.

делают так : если я понял правильно, окна не перекрываются и решетки окон инициализируются в 0. Но ведь свойство решеток в том, что они сходятся спустя несколько длин кодовых ограничений? Т.е. если размер окна у нас 32, то первые 16 состояний уйдут "в молоко". Получается первая итерация "на выброс". Но ведь это может дать неправильные экстринсики и усложнить сходимость декодера. На это забивают и тупо увеличивают количество итераций ? Типа "на что не пойдешь ради производительности" ? sm.gif


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Feb 9 2015, 17:16
Сообщение #84


Местный
***

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



Ну да, на оверлап забивают, чтобы поднять производительность. В той статье, которую ты цитировал sm.gif есть анализ - можно докрутить немного итераций и получить тот же перформанс. При этом это все равно оказывается выгоднее по пропускной способности, так как итерации крутятся большим количеством ядер.

Сообщение отредактировал andyp - Feb 9 2015, 22:35
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 10 2015, 07:32
Сообщение #85


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Feb 10 2015, 01:16) *
Ну да, на оверлап забивают, чтобы поднять производительность.

Злодеи sm.gif
Цитата(des00 @ Feb 10 2015, 00:48) *
как прикрутить однопортовку еще не задумывался

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


--------------------
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 24 2015, 09:06
Сообщение #86


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Базовый синтезируемый декодер в ПЛИСовой теме. К сожалению все уперлось в расчет рекурсии за 1 такт : 4 сложения и 3 MAX* sad.gif На моем среднем чипе для 8ми итераций, битовая кодированная скорость ~=2*100/(8*2) = 12.5 мегабит.


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Feb 24 2015, 10:00
Сообщение #87


Местный
***

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



Цитата(des00 @ Feb 24 2015, 12:06) *
Базовый синтезируемый декодер в ПЛИСовой теме. К сожалению все уперлось в расчет рекурсии за 1 такт : 4 сложения и 3 MAX*


Код не смотрел, но вброшу - Конвейер не спасет отца русской демократии?
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 24 2015, 15:16
Сообщение #88


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Feb 24 2015, 17:00) *
Код не смотрел, но вброшу - Конвейер не спасет отца русской демократии?

Нет. Сейчас скорость декодирования в полуитерации 1 пара/такт и частота ~100 МГц, если расконвейризировать (поставить регистры на критическом пути), то получиться частота ~200МГц, но и скорость декодирования 0.5пары/такт. В итоге размен шило, на мыло, при более сложном управлении. Как вариант, можно сделать на частоте ~200МГц, с мультиплексированием вычислительных модулей, при скорости декодирования 0.5 пары за такт, даст экономию ресурса процентов 40.

Есть такой вопрос по теории кодирования. На форуме уже была тема с обсуждением этого вопроса, но ЕМНИП закончилась ничем. Предисловие вопроса:
рассмотрим кривую декодирования с такими точками:
Код
# EbNo = 0.5: ber = 3.553110e-002. fer = 1.911794e-001
# EbNo = 1.0: ber = 2.800132e-003. fer = 1.811356e-001
# EbNo = 1.5: ber = 3.224499e-005. fer = 1.677701e-001
# EbNo = 2.0: ber = 0.000000e+000. fer = 1.540700e-001
# EbNo = 2.5: ber = 0.000000e+000. fer = 1.401851e-001
# EbNo = 3.0: ber = 0.000000e+000. fer = 1.269456e-001
# EbNo = 3.5: ber = 0.000000e+000. fer = 1.135156e-001
# EbNo = 4.0: ber = 0.000000e+000. fer = 1.005704e-001
# EbNo = 5.0: ber = 0.000000e+000. fer = 7.646611e-002
# EbNo = 6.0: ber = 0.000000e+000. fer = 5.522185e-002
# EbNo = 7.0: ber = 0.000000e+000. fer = 3.731609e-002
# EbNo = 8.0: ber = 0.000000e+000. fer = 2.336034e-002
# EbNo = 9.0: ber = 0.000000e+000. fer = 1.335576e-002

это QPSK размер пакета 212 пар, скорость 1/3. ber - бер после декодирования, fer - бер до декодирования. Если "не вооруженным взглядом" сравнить измеренный fer с эталонным графиком не кодированного QPSK с характерной точкой 1e-6 при EbNo = 10.5дб, то кажется что что-то не так. Но если вооружиться и пересчитать через EsNo = EbNo + 10log10(bps) + 10log10(coderate) то все встанет на свои места.

Теперь собственно сам вопрос : использование EbNo для сравнения систем кодирования/декодирования более менее понятно, нужна общая точка для сравнения характеристик декодеров, но для реальных систем связи более актуален EsNo. Почему он в теории кодирования, в применении к реальным системам связи, совсем не встречается? Более актуален ИМХО потому что этот параметр нагляден. Например: система с не кодированным QPSK может работать с 1е-6 при SNR ~= IEVM == 13.5дб, добавляем кодирование и можем работать при том же бер ну положим с SNR = 6дб(но на меньшей скорости). Наглядно и понятно что к чему, без сложных перерасчетов.


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Feb 24 2015, 16:02
Сообщение #89


Местный
***

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



Цитата(des00 @ Feb 24 2015, 18:16) *
Теперь собственно сам вопрос : использование EbNo для сравнения систем кодирования/декодирования более менее понятно, нужна общая точка для сравнения характеристик декодеров, но для реальных систем связи более актуален EsNo. Почему он в теории кодирования, в применении к реальным системам связи, совсем не встречается? Более актуален ИМХО потому что этот параметр нагляден. Например: система с не кодированным QPSK может работать с 1е-6 при SNR ~= IEVM == 13.5дб, добавляем кодирование и можем работать при том же бер ну положим с SNR = 6дб(но на меньшей скорости). Наглядно и понятно что к чему, без сложных перерасчетов.


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

На практике это оказывается не всегда удобным и народ часто перескакивает на Es/N0, когда именно Es/N0 неизменен и интересует именно выигрыш от применения той или иной схемы в данной конкретной системе связи.

Go to the top of the page
 
+Quote Post
petrov
сообщение Feb 24 2015, 16:02
Сообщение #90


Гуру
******

Группа: Свой
Сообщений: 2 220
Регистрация: 21-10-04
Из: Balakhna
Пользователь №: 937



Цитата(des00 @ Feb 24 2015, 18:16) *
Например: система с не кодированным QPSK может работать с 1е-6 при SNR ~= IEVM == 13.5дб, добавляем кодирование и можем работать при том же бер ну положим с SNR = 6дб(но на меньшей скорости). Наглядно и понятно что к чему, без сложных перерасчетов.


Например два графика BER от Es/N0 для BPSK и QPSK, вроде кажется, что BPSK лучше, на самом деле одинаково, да ещё и на полосе экономим в два раза в случае QPSK. SNR - самозапутывание, Eb/N0 - сразу всё ясно. ИМХО
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 24 2015, 16:29
Сообщение #91


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Feb 25 2015, 00:02) *
На практике это оказывается не всегда удобным и народ часто перескакивает на Es/N0, когда именно Es/N0 неизменен и интересует именно выигрыш от применения той или иной схемы в данной конкретной системе связи.

Вот как раз к такому же логическому выводу и прихожу sm.gif
Цитата(petrov @ Feb 25 2015, 00:02) *
Например два графика BER от Es/N0 для BPSK и QPSK, вроде кажется, что BPSK лучше, на самом деле одинаково, да ещё и на полосе экономим в два раза в случае QPSK. SNR - самозапутывание, Eb/N0 - сразу всё ясно. ИМХО

На практике обычно речь идет об энергетике в фиксированной полосе. ИМХО пример BPSK vs QPSK мне всегда казался исключением чем правилом, если уйти на более сложные созвездия, то при фиксированном EsNo будет не все так однозначно: например QPSK с кодированием 7/8 или 8PSK с 2/3 или QAM16 с 1/2 (при прочих равных). При использовании EsNo будет однозначно понятно что будет в каждом случае, при использовании EbNo нужно будет заниматься перерасчетами


--------------------
Go to the top of the page
 
+Quote Post
Mogwaika
сообщение Feb 24 2015, 17:14
Сообщение #92


Частый гость
**

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



Есть подозрение, что кодовую конструкцию в отрыве от сигнальной конструкции сравнивать с чем-то не стоит.

Лучше подскажите, пакетирование ошибок это хорошо или плохо? Т.е. на выходе кодека сатистика ошибок отличается от статистики ошибок в канале с абгш с тем же ber, и есть ошибки, которые кучкуются внутри одного кадра.
Go to the top of the page
 
+Quote Post
andyp
сообщение Feb 24 2015, 17:28
Сообщение #93


Местный
***

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



Цитата(Mogwaika @ Feb 24 2015, 20:14) *
Лучше подскажите, пакетирование ошибок это хорошо или плохо? Т.е. на выходе кодека сатистика ошибок отличается от статистики ошибок в канале с абгш с тем же ber, и есть ошибки, которые кучкуются внутри одного кадра.


Не хорошо и не плохо. Это бывает не багом, а фичей sm.gif Часто бывает при декодировании сверточных кодов, где ошибка в пути по решетке приводит к сразу нескольким рядом стоящим поломанным битам на выходе. Для иллюстрации - северточный код (133,171) У него 11 словам с весом d_free соответствует общий вес в 36 информационных бит. Т.е. в среднем ошибка в пути по решетке приводит к появлению 36/11 ошибочных информационных бит, стоящих близко друг от друга.

Именно из-за барстов ошибок на выходе сверточного кода вслед за ним ставят декодер Рида-Соломона, исправляющий ошибки в символах по 8 бит. Ему такие барсты не очень страшны. Если на выходе стоит кодер, чувствительный к барстам ошибок (например, исправляющей способности не хватает, чтобы исправлять барсты, но хватает, чтобы исправлять в среднем), то хорошо бы между кодерами поставить нтерливер.
Go to the top of the page
 
+Quote Post
des00
сообщение Feb 25 2015, 07:47
Сообщение #94


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Может кто сталкивался, что бы заново велосипед не изобретать (время на тестирование не тратить). В стандарте 802.16-2012 оговорено два вида перемежителя в одном и том же RSC : 8.3 WirelessMAN-OFDM PHY и 8.4 WirelessMAN-OFDMA PHY. Не понятно следующее в OFDM параметры перемежителя заданы формулой 8.3.3.2.3.2 CTC interleave в которой по сути P[1] = 0, P[2] = P[3] = N/2, т.е. соседние пары дебитов не перемежаются (только инверсия пары) длинна пакета может быть в диапазоне 8 <= N/4 <= 1024. В OFDMA перемежитель задан таблицей и задает всего 12 режимов работы, близких к DVB.

В стандарте для OFDM и OFDMA указаны что оба работают на закрытых интервалах в диапазонах до 11 гиг. Как бы одинаковые режимы работы и используемые модуляции, тогда в связи с чем может быть связана такая свобода и простота перемежителя в OFDM ?


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Feb 25 2015, 10:02
Сообщение #95


Местный
***

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



Цитата(des00 @ Feb 25 2015, 10:47) *
В стандарте для OFDM и OFDMA указаны что оба работают на закрытых интервалах в диапазонах до 11 гиг. Как бы одинаковые режимы работы и используемые модуляции, тогда в связи с чем может быть связана такая свобода и простота перемежителя в OFDM ?


На сколько помню, в OFDM барсты с пользовательскими данными, которые собственно и кодируются, выровнены на OFDM символы. В OFDMA единица выделения частотно-временного ресурса для барста - слот. Т.е. по факту в OFDM возможно гораздо меньше размеров кодовых блоков.
Go to the top of the page
 
+Quote Post
des00
сообщение Mar 7 2015, 15:33
Сообщение #96


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



В процессе вариации параметров декодера, обнаружил странности, вызвавшие вопросы :

1. Среди многообразия скоростей кодирования 1/3, 2/5, 1/2, 3/5, [2:9]/[3:10] работают все, кроме 7/8 (выкалываются 6 пар Y битов из семи). И это не ошибка в реализации декодера. Например беру блок 512 байт, EbNo = 5.0. Скорости 6/7, 8/9 дают нулевой выходной бер, а 7/8 всего в 2 раза меньше чем на входе. Сразу как-то вспомнилась связь цифры 7 с таблицой цикличности решетки и требования на размеры блоков. Может быть кто-то еще сталкивался с этим эффектом "пораженной скорости" и может подтвердить мои подозрения?

2. Проверяю другие модуляции, обнаружил странный эффект. Смотрю bertool, BPSK и QPSK, некодированые и витерби 1/2 с мягким решением. Кривые EbNo, в обоях случаях, ложатся один в один. Делаю BPSK с точками 1+1i,-1-1i, мягкую метрику считаю как сумму квадратур/2. Кодирование 1/3 или 1/2 и вижу результат: BPSK где-то на 0.1дб хуже. Причем это наблюдается даже на длинных прогонах (~10^6) бит, т.е. не похоже на влияние разного ансамбля шумовых отсчетов. Но ведь так не бывает. Или это фича декодера заточенного под обработку символов состоящих из двух бит одного символа радиоканала(QPSK,QAM16,QAM64), а не символа составленного двух разных символов радиоканала(BPSK, 8PSK, QAM32)?


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Mar 7 2015, 18:26
Сообщение #97


Местный
***

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



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

На счет 2 - учел, что твоя BPSK на 3 dB мощнее по энергетике, чем bpsk в одной квадратуре? Декодеру без разницы - что BPSK, что QPSK. Какая разница, последовательно переданы два бита или параллельно. И в одном и в другом случае шум в квадратурах или последовательных отсчетах на битовой скорости независим.

Сообщение отредактировал andyp - Mar 7 2015, 20:59
Go to the top of the page
 
+Quote Post
des00
сообщение Mar 8 2015, 07:27
Сообщение #98


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Mar 8 2015, 02:26) *
На счет 1 - расскажи подробнее про паттерн выкалывания - стоит проверить, остаются ли вообще проверочные биты каждого из кодеров после выкалывания. Сам понимаешь, если остаются только проверочные биты одного из кодеров, турбо-балалайка работать не будет.

Там все четко. Беру пары Y1Y0 и W1W0 (исходный код 1/3), для кодов >= 1/2 убираем W биты. Затем
1/2 - используем все Y пары,
2/3 - каждую вторую пару
3/4 - каждую третью
....
6/7 - каждую шестую
7/8 - каждую седьмую
8/9 - каждую восьмую.
Т.е. все условия для турбирования выполнены sm.gif Пробовал двигать начальную точку выкусывания бита при скорости 7/8, ничего не изменяется. Ощущение что 1 бит четности на период решетки дает "резонанс". При этом 8/9 работает sm.gif

Цитата
На счет 2 - учел, что твоя BPSK на 3 dB мощнее по энергетике, чем bpsk в одной квадратуре?

Я же строю нормированные к EbNo кривые. Сравниваю QPSK с символами 1+1i/-1+1i/1-1i/-1-1i и BPSK с символами 1+1i/-1-1i. Мощность созвездий одинакова и равна 2. EsNo для генератора шума пересчитываю по формуле EsNo = EbNo +10*log10(k*coderate). Для EbNo = 1db и coderate 1/3 для QPSK EsNo = -0.76db, BPSK EsNo = -3.77db.
Цитата
Декодеру без разницы - что BPSK, что QPSK. Какая разница, последовательно переданы два бита или параллельно. И в одном и в другом случае шум в квадратурах или последовательных отсчетах на битовой скорости независим.

Вот и мне так кажется, поэтому вопрос и возник, что результаты не совпадают с теорией sm.gif


--------------------
Go to the top of the page
 
+Quote Post
andyp
сообщение Mar 8 2015, 09:37
Сообщение #99


Местный
***

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



Почитал немного про выкалывание. Действительно, лучше не использовать скорости, числитель которых равен периоду феедбэк LFSR. В спектре появляется много слов с маленьким весом.
При 7/8 длина паттерна как раз равна периоду LFSR.
Объяснение на пальцах можно почитать здесь:
http://www.argreenhouse.com/society/TaCom/papers99/18_6.pdf

Цитата(des00 @ Mar 8 2015, 10:27) *
Вот и мне так кажется, поэтому вопрос и возник, что результаты не совпадают с теорией sm.gif


Попробуй погонять floating-point модель без ограничения при квантовании на входе. Должно работать одинаково для QPSK и BPSK. Больше ничего на ум не приходит.
Go to the top of the page
 
+Quote Post
des00
сообщение Mar 8 2015, 14:29
Сообщение #100


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



Цитата(andyp @ Mar 8 2015, 17:37) *
Объяснение на пальцах можно почитать здесь:

Спасибо за нужную литературу, вкурил и в итоге
Цитата
Действительно, лучше не использовать скорости, числитель которых равен периоду феедбэк LFSR.

можно использовать, но нужно уйти от простого равномерного выкалывания. Т.е. для 7/8 на группу из 49 символов нужно вместо патерна 0, 7, 14, 21, 28, 35, 42 использовать следующий паттерн 0, 8, 16, 24, 32, 40, 48. И все заработало sm.gif

И судя по всему повезло что решетка с периодом простого числа (7), в противном случае, судя по статье, пришлось бы встретиться с этим эффектом раньше sm.gif

Цитата
Попробуй погонять floating-point модель без ограничения при квантовании на входе. Должно работать одинаково для QPSK и BPSK. Больше ничего на ум не приходит.

Порою в эту сторону.


--------------------
Go to the top of the page
 
+Quote Post

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

 


RSS Текстовая версия Сейчас: 4th August 2025 - 08:51
Рейтинг@Mail.ru


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