|
Вопросы по итеративному декодированию, Реализация CTC/BTC/LDPC кодов |
|
|
|
Dec 24 2014, 14:00
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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. Вот этот момент мне совсем не понятен. Пока всё  Прошу помощи тех кто в теме.
--------------------
|
|
|
|
|
Dec 24 2014, 19:54
|
Частый гость
 
Группа: Участник
Сообщений: 112
Регистрация: 27-12-08
Пользователь №: 42 786

|
2. Полиномы RCS для Wimax и DVB одинаковые, но перемежители разные. Это сделано по политическим причинам или это результат "улучшения" характеристик декодера в процессе разработки стандарта?
Совершенно разные каналы генерируют совершенно разные ошибки (одиночные/пачки, длина пачки и т.д.), отсюда и разные перемежители, подобранные каждый под свои модели каналов.
3. В сверточных бинарных кодах, свойство tail-bitting используется при декодировании: В одной доке нашел что дополняют принятую последовательность вначале и в конце, затем декодируют по витерби и выкусывают нужное. В примере матлаба вообще составляют два фрейма, декодируют один за другим, потом из двух декодированных собирают один результат. Никакого намека на похожие операции в доках на турбокоды не нашел. Почему в алгоритмах SOVA/MAP/... для турбокодов это не делается?
Вопрос в получаемом энергетическом выигрыше и цене, которую за это надо заплатить. В случае сверточных кодов tail-biting дает +0.3 дБ, а платой за это является требование увеличения вычислительной мощности устройства, на котором реализуется декодер. По всей видимости в случае турбокодов это нецелесообразно.
|
|
|
|
|
Dec 24 2014, 22:13
|
Местный
  
Группа: Участник
Сообщений: 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
|
|
|
|
|
Dec 26 2014, 03:46
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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 наверное лучше заполнять не нулями, а какой нить ПСП ?
--------------------
|
|
|
|
|
Dec 26 2014, 08:56
|
Местный
  
Группа: Участник
Сообщений: 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
|
|
|
|
|
Dec 26 2014, 09:48
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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 байт добиваем нулями. Кодируем. Пары систематических символов, порожденные этим байтом в поток не передаем. На приемной стороне определяем эти биты как априори известные и декодируем.
--------------------
|
|
|
|
|
Dec 26 2014, 12:10
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(des00 @ Dec 26 2014, 12:48)  Вы правы, так и есть, правда сумма для 00 не вычитается. Вот это место : Странно. Судя по коду, который Вы приводили выше, они считают, что гамма для переходов решетки с 00 равна 0. Я поэтому про вычитание и предположил. Может быть, это еще где учитывается. Цитата Всё так, этот момент понятнен. Но что мешает поступить следующим образом : положим работаем с фреймом 53 байта и хотим укоротить его на 1 байт. Берем 52 байта данных и 1 байт добиваем нулями. Кодируем. Пары систематических символов, порожденные этим байтом в поток не передаем. На приемной стороне определяем эти биты как априори известные и декодируем. В системном плане смысла нет. В WiMax единицей частотно-временного ресурса системы является слот. В случае OFDMA это определенным образом расставленные по времени и частоте поднесущие (там много всяких комбинаций). Планировщик передачи выделяет ресурс слотами. Разбивка на слоты в аплинке и даунлинке сообщается всем станциям через специальные сообщения, передаваемые на фиксированных местах фрейма. Все кодовые блоки содержат целое количество слотов. Так уж это работает.
|
|
|
|
|
Dec 26 2014, 16:05
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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 Занятная вещь. Похоже местоположение инверсии пар не сильно принципиально  Пример кода в приложении. При работе требует либу http://www.iterativesolutions.com/Matlab.htm
Прикрепленные файлы
CTC.zip ( 2.31 килобайт )
Кол-во скачиваний: 39
--------------------
|
|
|
|
|
Dec 26 2014, 17:15
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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. Похоже просто убрали скорость, чтобы не заморачиваться  В этом вопросе WiMax гибче, у него количество фреймов разной длинны больше
--------------------
|
|
|
|
|
Dec 27 2014, 18:25
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(des00 @ Dec 26 2014, 19:05)  Занятная вещь. Похоже местоположение инверсии пар не сильно принципиально  Только кодер перестанет быть стандартным  . Рассмотрим второе преобразование (перестановку пар) и кодовый блок с 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
|
|
|
|
|
Dec 28 2014, 14:46
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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 канале?
--------------------
|
|
|
|
|
Dec 28 2014, 19:12
|
Профессионал
    
Группа: Участник
Сообщений: 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 канале? Это уже епархия демодулятора (АРУ, ограничители), чтобы все выходные значения лежали в заданном диапазоне
|
|
|
|
|
Dec 28 2014, 19:30
|
Местный
  
Группа: Участник
Сообщений: 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.
|
|
|
|
|
Dec 28 2014, 20:26
|

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

|
Прошу прощения, что влажу в чужую тему, но вопрос по теме вроде ... Из того, что я находил, то декодирование блочных кодов по МАР-алгоритму (мягкое решение) лучше всего расписано в приложенном документе (стр. 9-11) и у Moon'а (стр. 663). Но там все также предполагается построение решетки на основе входного символа. В приложении есть подраздел, в котором указывается, насчет построения решетки и насчет 2 конечных состояний - этот момент я пока не понимаю (даже несмотря на то, что есть рисунок - вопросы именно по этим 2 состояниям в основном). + Там интересный вывод окончательной формулы для вычислений (выражение 63). Может мне кто-то пояснить и как быть если блок например 128х128 - количество решеток ооочень большое получается... Чейз (2 вариант/алгоритм) в этом плане как-то по проще(понятней что-ли), но исправляющая способность у него ниже. Может кто-то поделиться понятным алгоритмом для декодирования блочных кодов (мягкое решение по входу)...
--------------------
If it doesn't work in simulation, it won't work on the board.
"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
|
|
|
|
|
Dec 28 2014, 23:36
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(Maverick @ Dec 28 2014, 23:26)  В приложении есть подраздел, в котором указывается, насчет построения решетки и насчет 2 конечных состояний - этот момент я пока не понимаю (даже несмотря на то, что есть рисунок - вопросы именно по этим 2 состояниям в основном). Глубоко копаешь  . Сам метод построения решетки блочного кода по проверочной матрице описан в книжке 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
|
|
|
|
|
Dec 29 2014, 09:48
|

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

|
Цитата(andyp @ Dec 29 2014, 01:36)  Глубоко копаешь  . Сам метод построения решетки блочного кода по проверочной матрице описан в книжке 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. Там приведены кое-какие алгоритмы. Может, часть из них окажется интересной. спасибо за объяснение... тогда и махlog-map тоже не подходит. А какой же алгоритм брать для использования - чейза или есть другие по лучше алгоритмы?
--------------------
If it doesn't work in simulation, it won't work on the board.
"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
|
|
|
|
|
Dec 29 2014, 10:13
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(Maverick @ Dec 29 2014, 12:48)  А какой же алгоритм брать для использования - чейза или есть другие по лучше алгоритмы? Для длинных кодовых блоков и скорости, близкой к 1/2? Общего рецепта нет. Чейз для длинных кодов как-то тоже не очень - у него сложность тоже экспоненциальная, просто растет медленнее. Народ идет по пути синтеза хорошо декодируемых известными алгоритмами кодов. LDPC хорошо декодируются по графу итеративно. BTC - опять итеративное декодирование простых составных кодов. Как-то так. "Итеративно" - видимо ключевое слово на сегодяншний день. Есть еще алгоритмы мягкого декодирования Рида-Соломона, но я с ними не разбирался.
|
|
|
|
|
Dec 29 2014, 10:58
|

я только учусь...
     
Группа: Модераторы
Сообщений: 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) Длинные эти коды или нет я не знаю  Интересуют именно алгоритмы мягкого декодирования Момент итеративности(количества итераций) сейчас можно пока опустить...
--------------------
If it doesn't work in simulation, it won't work on the board.
"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
|
|
|
|
|
Dec 29 2014, 12:13
|
Профессионал
    
Группа: Участник
Сообщений: 1 050
Регистрация: 4-04-07
Пользователь №: 26 775

|
Цитата(Maverick @ Dec 29 2014, 13:48)  спасибо за объяснение... тогда и махlog-map тоже не подходит. А какой же алгоритм брать для использования - чейза или есть другие по лучше алгоритмы? при правильном подходе Чейз дает весьма неплохие результаты даже для кодов типа [128x128], результат получается даже на уровне AHA, можно и другие алгоритмы попробовать, как-то уже с Вами обсуждали здесь, даже кое-что высылал. посмотрите в сторону мажоритарного декодера, для расширенных кодов Хемминга, о которых, как я понимаю, идет речь, сложность реализации будет невелика (для этих кодов каждый бит может быть представлен 4-мя уравнениями), а эффективность будет находиться где-то на уровне Чейза. к уже упомянутым алгоритмам можно еще добавить семейство вероятностных алгоритмов BPA (Belief Propagation Algorithm) или SPA (SumProduct Algorithm) алгоритмов и их аппроксимации на основе все той же алгебры логарифмов правдоподобия, но опять же, сложность реализации будет на уровне MAPa. а MAP, как правильно сказали, будет тяжеловат для кодов типа [128x128], хотя для [64x64] еще приемлемо.
|
|
|
|
|
Dec 29 2014, 13:02
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(Maverick @ Dec 29 2014, 13:58)  Да, для блоковых кодов до (128*128)*(128*128) и до 3D: (128*128)*(128*128)*(64*64) Длинные эти коды или нет я не знаю  Интересуют именно алгоритмы мягкого декодирования Момент итеративности(количества итераций) сейчас можно пока опустить... Что ты понимаешь под (128*128)? Перемножение двух скобочек - это продакт код? Сложность алгоритма Чейза 2 растет (ну и всех основанных на нем алгоритмов SISO) экспоненциально от d/2. Если у тебя например 128-битный код Хамминга, то у него d=3 и декодировать его - плевое дело. Если будешь его декодировать по решетке, то в каждой секции будет не больше 2^7 состояний (количество состояний в решетке будет пропорционально 2^(n-k) или 2^k, смотря что меньше), так что MAP декодирование для составных кодов, остнованных на кодах Хемминга, опять же возможно для широкого диапазона битовых скоростей. Есть еще всякие алгоритмы типа recursive MLD и итеративное декодирование по minimum weight subtrellis, но все они зависят от структуры кода. Наверное, я не про то пишу и все-таки и не понимаю вопроса.
|
|
|
|
|
Dec 29 2014, 13:55
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(Serg76 @ Dec 29 2014, 16:23)  По всей видимости 2D TPC, где в качестве компонентных используются расширенные коды Хемминга или же, по-другому, (128, 120)x(128,120) Тогда мой ответ про Хемминга релевантен. Для MAP декодирования наибольшую проблему составляет скорость ~1/2 - наиболее сложная решетка. Да и для Чейза сложность с ростом кодового расстояния увеличится.
|
|
|
|
|
Dec 29 2014, 15:39
|

я только учусь...
     
Группа: Модераторы
Сообщений: 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.
"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
|
|
|
|
|
Dec 29 2014, 21:40
|

я только учусь...
     
Группа: Модераторы
Сообщений: 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] еще приемлемо. погорячился... попробую посмотреть в сторону мажоритарного декодера... ЗЫ Просьба если не затруднит вышлите мне еще раз - не могу найти у себя на винте Вот это читаю...На 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.
"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
|
|
|
|
|
Dec 29 2014, 21:48
|
Профессионал
    
Группа: Участник
Сообщений: 1 050
Регистрация: 4-04-07
Пользователь №: 26 775

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

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

|
Цитата(Serg76 @ Dec 29 2014, 23:48)  ссылка мертвая  , уже не помню, что я там выкладывал, надо собирать заново, пока можно спросить у 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.
"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
|
|
|
|
|
Dec 30 2014, 03:42
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453

|
Цитата(Maverick @ Dec 30 2014, 06:25)  знаю, прежде чем попросить проверил ... То что вы спрашивали помню, а вот то что отсылал нет Цитата чтобы достичь таких высоких скоростей обработки и повторить такое... Не совсем понимаю в чем проблема, там же 4 декодера работают параллельно. Обрабатывается сразу по 4 строки и 4 столбца, при этом как я понимаю работают не побитно, а пословно. Пока совершенно не ориентируюсь в 2D TPC кодах, но если скорость кодирования высокая, то думаю что это может очень быстро работать. судя по доке на 150МГц они дают 45 мегабит на декодер, итого 3 такта на бит. 4 декодера с запасом.
--------------------
|
|
|
|
|
Dec 30 2014, 09:50
|

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

|
Цитата(des00 @ Dec 30 2014, 05:42)  То что вы спрашивали помню, а вот то что отсылал нет Не совсем понимаю в чем проблема, там же 4 декодера работают параллельно. Обрабатывается сразу по 4 строки и 4 столбца, при этом как я понимаю работают не побитно, а пословно. Пока совершенно не ориентируюсь в 2D TPC кодах, но если скорость кодирования высокая, то думаю что это может очень быстро работать. судя по доке на 150МГц они дают 45 мегабит на декодер, итого 3 такта на бит. 4 декодера с запасом. спасибо... не отсылали, я Вам тогда не ответил, решил сам покопать...
--------------------
If it doesn't work in simulation, it won't work on the board.
"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
|
|
|
|
|
Jan 19 2015, 10:09
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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 используются всегда как есть
--------------------
|
|
|
|
|
Jan 19 2015, 12:14
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(des00 @ Jan 19 2015, 13:09)  Глупый вопрос. Почему в RSС кодах не учитывается extrinsic информация о проверочных битах. Понятно что между декодерами передавать LLR проверочных битов не имеет смысла, но в пределах одного декодера между итерациями почему не воспользоваться выходными LLR метриками проверочных бит. Апостериорные вероятности проверочных бит не добавляют полезной информации. Вся инфа, выцепленная из структуры кода, уже учтена в экстринсиках систематических бит. Они определяют вероятности состояний решетки и, соответственно переходов по ней, из которых рассчитываются апостериорные вероятности того или иного проверочного бита.
|
|
|
|
|
Jan 19 2015, 13:25
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453

|
Цитата(andyp @ Jan 19 2015, 20:14)  Апостериорные вероятности проверочных бит не добавляют полезной информации. Вся инфа, выцепленная из структуры кода, уже учтена в экстринсиках систематических бит. Они определяют вероятности состояний решетки и, соответственно переходов по ней, из которых рассчитываются апостериорные вероятности того или иного проверочного бита. Понял, как самому в голову не пришло  Тогда вопросы - следствие: 1. Тогда зачем в некоторых примерах рассчитывают LLR проверочных бит и принимают решение о проверочных битах? Только ради того что бы посчитать BER методом обратного кодирования? 2. В таком случае можно же сократить количество вычислений при итерациях, вычислив gammaE[0][input][k][s]=exp(0.5*Lc*parity1[k]*xk); один раз при первом проходе?
--------------------
|
|
|
|
|
Jan 19 2015, 15:23
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(des00 @ Jan 19 2015, 16:25)  Понял, как самому в голову не пришло  Тогда вопросы - следствие: 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) - меняется.
|
|
|
|
|
Jan 21 2015, 09:42
|
Участник

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

|
или для демодуляции и декодировании в многоуровневых сигнально-кодовых конструкциях.
|
|
|
|
|
Jan 22 2015, 09:06
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453

|
Цитата(andyp @ Jan 19 2015, 22:23)  P_appriory(in) * P_appriory(coded) можно посчитать заранее, это не меняется между итерациями. P_extrinsic(in) - меняется. Это и имел в виду, похоже что в сети полно декодеров, назову их "каноническими", которые показывают работу алгоритма и не заботятся о производительности. Все остальное "пилите шура, пилите" (с)  Цитата(andyp @ Jan 21 2015, 15:37)  Подумал на счет пункта 1 - LLR проверочных бит могут потребоваться для итеративной демодуляции-выравнивания. Вполне возможно, видел много статей про турбоэквалайзирование, но для моих скоростей оно пока не применимо. Цитата(smoke_111 @ Jan 21 2015, 16:42)  или для демодуляции и декодировании в многоуровневых сигнально-кодовых конструкциях. Вы имеете в виду что-то вроде иерархической модуляции, для классических созвездий этого делать не нужно, там просто демаппер корректный надо сделать.
--------------------
|
|
|
|
|
Jan 23 2015, 08:08
|
Участник

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

|
я имею в виду схемы наподобии trellis-coded modulation на основе разбиения Ангербёка(Ungerboek), где для демодуляции бит следующего уровня нужны все данные с предыдущего.
|
|
|
|
|
Jan 23 2015, 08:49
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

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

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

|
точно, спасибо, забыл как это называется.
|
|
|
|
|
Jan 26 2015, 06:45
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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, они ставят созвездие почти в насыщение квантователя. В чем тайный смысл сего действа ?
--------------------
|
|
|
|
|
Jan 26 2015, 16:54
|
Местный
  
Группа: Участник
Сообщений: 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. Видимо, провели моделирование какое-то, чтобы подтвердить результаты.
|
|
|
|
|
Jan 27 2015, 05:52
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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 бит в метрику накинуть или нелийнейное квантование сделать.
Эскизы прикрепленных изображений
--------------------
|
|
|
|
|
Jan 27 2015, 09:19
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(des00 @ Jan 27 2015, 08:52)  Т.е. большую часть статистической информации тупо выкинули. Тут стоит оценить дисперсию ошибки квантования vs дисперсия ошибки ограничения на рабочих SNR декодера для разных скоростей. Хотя даже это не будет критерием "лучшести" квантователя из-за нелинейности декодера. Нужно на BER смотреть. Цитата Похоже что вы правы, сам не додумался. ИМХО это сильно на шаманство похоже. Вырезать актуальную информацию из канала, вместо того что бы 1 бит в метрику накинуть или нелийнейное квантование сделать. Я тоже за дополнительный бит  , но я ж софтверщик - он мне фактически ничего не стоит. В железе, думаю, сложность будет линейно расти с количеством входных бит. Авторы электричество и вентили экономят вовсю.
|
|
|
|
|
Jan 28 2015, 12:07
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(des00 @ Jan 28 2015, 12:44)  да, где то в доке находил коэффициент 0.75, но это только для max-log-MAP алгоритма, для компенсации неидеальности аппроксимации логарифма суммы экспонент. Я встречал другое объяснение - от итерации к итерации информация о бите уменьшается, поэтому вводят нечто типа OOC, чтобы учесть это уменьшение.
|
|
|
|
|
Jan 28 2015, 15:42
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453

|
Цитата(andyp @ Jan 28 2015, 19:07)  Я встречал другое объяснение - от итерации к итерации информация о бите уменьшается, поэтому вводят нечто типа OOC, чтобы учесть это уменьшение. хмм, надо еще будет эту тему прошерстить. В приложении матлабовский примитивный, без какой либо оптимизации, декодер dvb-rsc, часть функций сделана близко к железу, позволяет покрутить/посмотреть что и как считается, что куда идет, как себя ведут метрики и прочее  Содержит комментарии как что и куда. Перехожу к работе над HDL идеалкой.
Прикрепленные файлы
ctc.zip ( 12.61 килобайт )
Кол-во скачиваний: 39
--------------------
|
|
|
|
|
Jan 28 2015, 20:09
|

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

|
Цитата(des00 @ Jan 28 2015, 17:42)  хмм, надо еще будет эту тему прошерстить. В приложении матлабовский примитивный, без какой либо оптимизации, декодер dvb-rsc, часть функций сделана близко к железу, позволяет покрутить/посмотреть что и как считается, что куда идет, как себя ведут метрики и прочее  Содержит комментарии как что и куда. Перехожу к работе над HDL идеалкой. спасибо...
--------------------
If it doesn't work in simulation, it won't work on the board.
"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
|
|
|
|
|
Feb 3 2015, 15:34
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453

|
Цитата(andyp @ Jan 29 2015, 16:56)  Поздравляю с завершением этапа  Похоже где то я ошибся  Сделал идеалку на 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.
--------------------
|
|
|
|
|
Feb 4 2015, 13:47
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453

|
Цитата(des00 @ Feb 3 2015, 22:34)  Похоже где то я ошибся  Ошибся в добавлении шума к сигналу в тесте на 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?
Эскизы прикрепленных изображений
--------------------
|
|
|
|
|
Feb 4 2015, 16:08
|
Частый гость
 
Группа: Участник
Сообщений: 90
Регистрация: 11-09-11
Пользователь №: 67 121

|
Цитата(des00 @ Feb 4 2015, 17:47)  Ошибся в добавлении шума к сигналу в тесте на SV. Забыл про одну из типовых System Verilog gotcha, в результате при добавлении к сигналу шум становился не AWGN, со всеми вытекающими. Поправил это место и характеристики легли близко с "референсным" декодером в статье. Почему матлаб работает не так еще не понял, может быть сказывается количество бит. RTL гоняю на 8М бит(15 минут на тест), матлаб на 200К (это он ночь стоит, очень уж медленно он работает). Код запускаете напрямую или компилируете в mex или exe? У меня для декодера компиляция дала прирост почти на порядок.
|
|
|
|
|
Feb 4 2015, 17:07
|
Знающий
   
Группа: Свой
Сообщений: 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
|
|
|
|
|
Feb 4 2015, 18:32
|
Участник

Группа: Участник
Сообщений: 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 хорош для больших длин ( позволяет не пересчитывать метрики каждую полуитерацию), для маленьких будет давать существенный проигрыш.
|
|
|
|
|
Feb 4 2015, 19:03
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453

|
Цитата(Grizzzly @ Feb 5 2015, 01:07)  Посмотрите примеры Спасибо, попробую запустить. Не ставил задачу оптимизации матлабовского кода, наоборот писалось все в лоб, что бы понять детали. Но тем не менее тормоза удручают. При этом даже, на казалось бы, быстрых машинах. Цитата(smoke_111 @ Feb 5 2015, 02:32)  Нормально, это не принципиально Понял спасибо. Цитата по поводу цикличности, метод предложенный andyp хорош для больших длин ( позволяет не пересчитывать метрики каждую полуитерацию), для маленьких будет давать существенный проигрыш. Как раз успел прогнать разные варианты (альфа - бета, бета - альфа) на маленьких кодах, проигрыш виден не вооруженным взглядом. На больших еще не проверял.
--------------------
|
|
|
|
|
Feb 4 2015, 19:18
|
Участник

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

|
На больших все хорошо должно быть, если мне правильно вспоминается, то вариант от andyp, работает лучше чем вариант с предекодерами.
|
|
|
|
|
Feb 4 2015, 20:01
|
Частый гость
 
Группа: Участник
Сообщений: 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.
|
|
|
|
|
Feb 5 2015, 07:47
|
Профессионал
    
Группа: Участник
Сообщений: 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). Какая максимальная скорость достигнута в Вашей реализации?
|
|
|
|
|
Feb 5 2015, 08:43
|
Знающий
   
Группа: Свой
Сообщений: 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
|
|
|
|
|
Feb 5 2015, 09:30
|
Частый гость
 
Группа: Участник
Сообщений: 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)
|
|
|
|
|
Feb 5 2015, 10:04
|
Профессионал
    
Группа: Участник
Сообщений: 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?
|
|
|
|
|
Feb 5 2015, 10:36
|
Знающий
   
Группа: Свой
Сообщений: 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. Понял, спасибо.
|
|
|
|
|
Feb 5 2015, 10:59
|
Частый гость
 
Группа: Участник
Сообщений: 90
Регистрация: 11-09-11
Пользователь №: 67 121

|
Цитата(Serg76 @ Feb 5 2015, 14:04)  Спасибо, 4-х битный - это на 16 состояний как в RCS2? Да, на 16 из стандарта ECSS-E-ST-50-01C, длиной 1784.
|
|
|
|
|
Feb 6 2015, 16:42
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453

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

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

|
метод обращения функции генерации адреса есть, смотреть в сторону решения уравнений в модулярной форме, там в принципе ничего сложного. Да вроде никто не мешает сначала посчитать бету, а потом альфу и получается, что результирующие данные идут в прямом порядке (в общем спорный вопрос про логичность).
Сообщение отредактировал smoke_111 - Feb 6 2015, 17:36
|
|
|
|
|
Feb 6 2015, 17:43
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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, потом при забеге по бета, расчет не потребуется, т.к. адрес уже посчитан и результат второй полуитерации можно записать в уже деперемеженном формате в результат.
--------------------
|
|
|
|
|
Feb 6 2015, 18:07
|
Участник

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

|
Прошу прощения я кажется запутался, я правильно понимаю ваш вопрос, вы хотите получить адреса данных после перемежения для бет в обратном порядке?
|
|
|
|
|
Feb 6 2015, 19:14
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(smoke_111 @ Feb 6 2015, 21:07)  Прошу прощения я кажется запутался, я правильно понимаю ваш вопрос, вы хотите получить адреса данных после перемежения для бет в обратном порядке? В приложенной статье утверждается, что аналогичная схема может быть использована для генерации индексов интерливера как в прямом так и в инверсном порядке. Правда, там интерливер WiMax, но он должен быть очень похож на интерливер для DVB
Сообщение отредактировал andyp - Feb 6 2015, 19:23
|
|
|
|
|
Feb 8 2015, 08:59
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(des00 @ Feb 7 2015, 19:34)  самое занятное что они правы, внимательно позырил на формулу и все встало на круги своя. Замена сложения на вычитание P0 в аккумуляторе и изменение адреса инициализации с 0 на P0*(N-1) % N дает искомый результат. Жаль только то, что под каждую длину нужен свой уникальный адрес инициализации  Это не самая большая проблема. Проблема - обеспечить, чтобы параллельно работающие SISO модули не сталкивались при доступе к памяти экстринсиков. Вот статья про это на примере wimax. Может, будет интересно.
|
|
|
|
|
Feb 9 2015, 09:48
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(des00 @ Feb 9 2015, 08:27)  Попутно возник вопрос, почему все бьются за повышение параллелизма одной полуитерации. Положим есть 10 параллельно работающих движков, это требует наличия 10 ти портовых регистровых файлов. Ведь можно же уйти в глубину : те же 10 движков поставить последовательно в конвейер и развязать их двухпортовыми блочками памяти(при этом память под Lext можно заменить на память Lext + Ls). Да, задержка обработки вырастет, но пиковая производительность останется на том же уровне. Правда количество итераций произвольно менять будет сложнее. Потому что ты себе несколько не тот вопрос задаешь. Ты рассматриваешь задачу получения максимальной пропускной способности без ограничений, а надо с ограничениями  Вопрос должен быть таким - у меня есть максимум М движков, я жутко экономлю электричество (фактически, экономлю тактовую и память ). Какими выбрать М и тактовую, чтобы все же получить нужную пропускную способность для всех возможных размеров блоков? Что касается статьи, она не про тоже самое, что и статья, которую ты привел. У Martinа размер окон меняется динамически в зависимости от размера блока и авторы ставят задачу прокормить до 4 движков, делающих одну полуитерацию, экстринсиками из однопортовой памяти. Т.е. они вообще не ставят перед собой задачу получить макс. пропускную способность с выхода декодера. Они говорят о достаточной. Больше информации о том, как устроен декодер у Martinа, можно почерпнуть из прицепленной статьи. Предыдущая была только про интерливер. Что касается граничных альф и бет для окна, они используют значения, полученные на предыдущей итерации.
|
|
|
|
|
Feb 9 2015, 16:48
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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 состояний уйдут "в молоко". Получается первая итерация "на выброс". Но ведь это может дать неправильные экстринсики и усложнить сходимость декодера. На это забивают и тупо увеличивают количество итераций ? Типа "на что не пойдешь ради производительности" ?
--------------------
|
|
|
|
|
Feb 24 2015, 10:00
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(des00 @ Feb 24 2015, 12:06)  Базовый синтезируемый декодер в ПЛИСовой теме. К сожалению все уперлось в расчет рекурсии за 1 такт : 4 сложения и 3 MAX* Код не смотрел, но вброшу - Конвейер не спасет отца русской демократии?
|
|
|
|
|
Feb 24 2015, 15:16
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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дб(но на меньшей скорости). Наглядно и понятно что к чему, без сложных перерасчетов.
--------------------
|
|
|
|
|
Feb 24 2015, 16:02
|
Местный
  
Группа: Участник
Сообщений: 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 неизменен и интересует именно выигрыш от применения той или иной схемы в данной конкретной системе связи.
|
|
|
|
|
Feb 24 2015, 16:29
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453

|
Цитата(andyp @ Feb 25 2015, 00:02)  На практике это оказывается не всегда удобным и народ часто перескакивает на Es/N0, когда именно Es/N0 неизменен и интересует именно выигрыш от применения той или иной схемы в данной конкретной системе связи. Вот как раз к такому же логическому выводу и прихожу Цитата(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 нужно будет заниматься перерасчетами
--------------------
|
|
|
|
|
Feb 24 2015, 17:28
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(Mogwaika @ Feb 24 2015, 20:14)  Лучше подскажите, пакетирование ошибок это хорошо или плохо? Т.е. на выходе кодека сатистика ошибок отличается от статистики ошибок в канале с абгш с тем же ber, и есть ошибки, которые кучкуются внутри одного кадра. Не хорошо и не плохо. Это бывает не багом, а фичей  Часто бывает при декодировании сверточных кодов, где ошибка в пути по решетке приводит к сразу нескольким рядом стоящим поломанным битам на выходе. Для иллюстрации - северточный код (133,171) У него 11 словам с весом d_free соответствует общий вес в 36 информационных бит. Т.е. в среднем ошибка в пути по решетке приводит к появлению 36/11 ошибочных информационных бит, стоящих близко друг от друга. Именно из-за барстов ошибок на выходе сверточного кода вслед за ним ставят декодер Рида-Соломона, исправляющий ошибки в символах по 8 бит. Ему такие барсты не очень страшны. Если на выходе стоит кодер, чувствительный к барстам ошибок (например, исправляющей способности не хватает, чтобы исправлять барсты, но хватает, чтобы исправлять в среднем), то хорошо бы между кодерами поставить нтерливер.
|
|
|
|
|
Feb 25 2015, 10:02
|
Местный
  
Группа: Участник
Сообщений: 453
Регистрация: 23-07-08
Пользователь №: 39 163

|
Цитата(des00 @ Feb 25 2015, 10:47)  В стандарте для OFDM и OFDMA указаны что оба работают на закрытых интервалах в диапазонах до 11 гиг. Как бы одинаковые режимы работы и используемые модуляции, тогда в связи с чем может быть связана такая свобода и простота перемежителя в OFDM ? На сколько помню, в OFDM барсты с пользовательскими данными, которые собственно и кодируются, выровнены на OFDM символы. В OFDMA единица выделения частотно-временного ресурса для барста - слот. Т.е. по факту в OFDM возможно гораздо меньше размеров кодовых блоков.
|
|
|
|
|
Mar 7 2015, 15:33
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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)?
--------------------
|
|
|
|
|
Mar 8 2015, 07:27
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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 - каждую восьмую. Т.е. все условия для турбирования выполнены  Пробовал двигать начальную точку выкусывания бита при скорости 7/8, ничего не изменяется. Ощущение что 1 бит четности на период решетки дает "резонанс". При этом 8/9 работает Цитата На счет 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. Какая разница, последовательно переданы два бита или параллельно. И в одном и в другом случае шум в квадратурах или последовательных отсчетах на битовой скорости независим. Вот и мне так кажется, поэтому вопрос и возник, что результаты не совпадают с теорией
--------------------
|
|
|
|
|
Mar 8 2015, 09:37
|
Местный
  
Группа: Участник
Сообщений: 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)  Вот и мне так кажется, поэтому вопрос и возник, что результаты не совпадают с теорией  Попробуй погонять floating-point модель без ограничения при квантовании на входе. Должно работать одинаково для QPSK и BPSK. Больше ничего на ум не приходит.
|
|
|
|
|
Mar 8 2015, 14:29
|
Вечный ламер
     
Группа: Модераторы
Сообщений: 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. И все заработало И судя по всему повезло что решетка с периодом простого числа (7), в противном случае, судя по статье, пришлось бы встретиться с этим эффектом раньше Цитата Попробуй погонять floating-point модель без ограничения при квантовании на входе. Должно работать одинаково для QPSK и BPSK. Больше ничего на ум не приходит. Порою в эту сторону.
--------------------
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|