|
 Обновления |
Главная -> Вычислительные алгоритмы Приложение А НАБОР АЛГОРИТМОВ ЦИКЛИЧЕСКИХ СВЕРТОК В данном приложении приводится набор алгоритмов циклических сверток над полем вещественных чисел для длин п = = 2, 3, 4, 5, 7, 8 и 9. Алгоритмы имеют вид равенств S - CGAd. Матрица О является диагональной и ее .пагогальиые элементы выписываются в виде компонент вектора G = Bg. хМатрнцы А я С выписываются полностью. Кроме того, используя обозначения D - Ad, S - GD. S = CS, мы приводим последовательности сложений, которыми можно заменить умножения на матрицы А и С. 2-точечная циклическая свертка; 2 вещественных умножения,. 4 вегдесгвекных сложения [т п fg,: , - Se - s, 3-точечная циклическая свертка; 4 вещественных умножения. 11 вещественных сложений 1 -2] Do - Го + rfj Dl . Л - d, Dv = rfi + r: 7, = S, - S, r, = s= - s, s. So + To s, = So - To - Ti 5, = So + T, 12.2. Повторить приведенный на рис. 12.7 пример для входной последоват! ности V = 1000100000100000... . 13.3. Алгоритм Витерби может быть запрограммирован в виде, в котором pal ходимости путей на (-Й итерации запоминаются в том же массиве, что и pal ходимости путей на (i-1)-й итерации. Выписать последовательно) адресов и вычислений, позволяющих сделать такую программу. 2.4. 2 выживающих в алгоритме Витерби (при q= 2) путей можно записа- в виде 2 й-битовых двоичных слов. В типичных случаях fc = 40 бит. 1 строить (используя такие средства, как указатели и битовые срезы) cxei управления памятью для алгоритма Витерби, которая исключает необи димость считывания на каждой итерации 2%битовых слов. Замечания Алгоритмы поиска по решетке появились сначала в связи с кодами, контр! лирующнми ошибки, для которых задачу декодирования сверточных кодов можш интерпретировать как задачу поиска по решетке (или по дереву). Большинста публикаций по данному вопросу выполнено на языке кодов, контролируют ошибки. Однако, в настоящее время к этим алгоритмам проявляется более ши кий интерес, и в данной главе сделана попытка их изложения вне зависимое от какого бы то нн было приложения. Хотя ретроспективно наиболее подходящим в качестве начала изложен данного круга вопросов представляется алгоритм Витерби, на самом деле п€ выми были разработаны последовательные алгоритмы. Последовательные алп ритмы были введены Возенкрафтон (1957) н подробно описаны Возенкрафто и Рейффеном (1961). Дальнейшее развитие они получили у Фано (1963), Зиганг] рова (1966) и Джелинека (1969). Разработки Джелинека (1968) и Форни (197J а также работы ШевнлЛа и Костелло (1978) и Хаккоуна и Фергюсона (19Г также продвинули исследование данного вопроса. Наше изложение алгорйп Фано тесно связано с данным Галлагером (1968) изложением этого алгоритм Первоначально Витерби (1967) опубликовал свой алгоритм скорее в учебнЫ целях, чем в качестве серьезного алгоритма. Программные реализации алг ритма Витерби с эффективным использованием памяти описаны Рейдером (19813 Нижние границы для распределения числа операций получили Джекоба н Берлекэмп (1967), а верхние - Севедж (1966). ний!-г5 вГс.в1:нТГлГни7 -- -венных ум;;;;;: Приложевне А. Набор алгоритмов циклических сверток
fi I 1 I -1 I I 1-1 ! -1 -1 0 -n 1 01 -I 1 -1 0 -2 0 2 2 -2 2 -2 -2I
n = S , J, = s. - .s, T, = S, - s, T, = .S, + .V, 5.1 - n + Г, i = r, + T, J = f - r, - T, - r. 7-точечная циклическая свертка; 16 вещественных умножений 70 вещественных сложений 31 вГщ7 вТныГс~иГ - - -венных умножений,! П о о 1) I о 110 0-2 0 0 1 0-1 0 0 о 1-1 0 0 1 I 2 10-10 0 10 1 0-1 1-1 о 10 10 0 0 -1 0 -1 -1-2-1-1-2 0 0 0 1 0 0 0 0 1 1 I о о о 1 о 1 11110 11 о о 0-1-1 , I I 1 1
1 1 1 1 0 0 0 0 0 0 l-i -3 -1 - -1 -I -3 1 -7 -1 0 0 0 0 0 0 1 1 4 1 0000001 -1 20 0 0 0 0 0 1 1 1 1 0 0 1 1 4 1 0 0 0 0 0 01 -1 200000 11110 0 0 0 0 0 о -1 -0-1 -1 -1 -о 1 о 1 - -4-1 1 -2 о 1 -1 о 1 4 1 I 2 р 1 D, . D, . Ds = Oi = D, --D, --Oi. = D = Du = 2C, 14C, 6Ci 60, G, O, 14G, 60, 6C, 2Gi. MGii 60 6C Ci. 7Ci, = rfi - Л Л - rf. - rf. - rf. = rf! - rfs = o + d = - o + /i ! + (j -d. + rfj - d, - dt D, + I. De + Ii D, + + и + h I, d, - d, D, + (. Di + fj £>6 + /6 + /б + /, О, - О, - О, D, - Oi D, - Д, О. - О. Dii + 2(rf, + (/, + do) -
8-точечная циклическая свертка; 14 вещественных умножений, 46 вещественных сложений Г, = S. + s Т, - S, + s T, = Si + s,j n = s, + s T, = S, + S:, TiS,- s r. = s. - s r,S,- s Г, = S, - S,j Г, = 5, - S r,. = Г, + T, r r + Ti Гц = 7i + 7, r = Г,. # T, r,. = T - n T,i = (Г, + 7-j + г, + г.) + 7i т ,! = - г - г,1 - (г + г, + г, т.)! т = п + т, т = т + т, т = т, + г т = Г -ь т, Тп = (7- + F, + г, + г,) 7-, i Г = -Т - 7 - (Г г, + г. + Г,) Sl = Г, + Га -I- Sij Sj = Tji + 5is S) = r Sij s. - r + S,s Si = T,> + 5,1 s. = Г,. + S,
20i 2C, 20i 2G 2G 2C 1 0 0 0 0 1 0 I 0 -1 -1 0 0 1 - 0 -1 - 1 0 -1 0 0 -1 - 0 I - -1 1 1 1 0 0 0 0
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||