Декодер хвостових бітів решітки (варіанти) та спосіб декодування кодів хвостових бітів решітки (варіанти)

1. Декодер хвостових бітів решітки, закодованих шифратором, які декодер декодує шляхом визначення сумісної імовірності того, що стан шифратора в час t, St, дорівнює m, і що приймається послідовність L канальних виходів, які мають значення YLl={y1...yL}, визначеної за формулою λt(m)=P{St=m; YLl}, причому вказаний решітковий код відповідає М станам шифратора, який відрізняється тим, що декодер виконаний з можливістю визначення L матриць Гt імовірностей, причому одна матриця відповідає кожному з L решіткових рівнів, а елементи вказаних матриць імовірностей визначаються за формулою: Гt(і,j)=Р{стан j в час t; уt/стан і в час t-1}; шляхом визначення рядкових векторів αt, які мають М елементів сумісних імовірностей, за формулою: αt(j)=P{cтaн j в час t; у1,...,уt}; шляхом визначення векторів колонок βt, які мають М елементів умовних імовірностей за формулою: βt(j)=P{yt+1,..., yL/ стан j в час t}, де j=0,1,..., (M-1), цей декодер містить: Гt калькулятор для прийому вказаних канальних виходів, визначення R(Yt,X) імовірності канального переходу, імовірності pt(m/m') того, що шифратор робить перехід із стану m' в стан m в час t, і імовірності qt(X/m', m) того, що вихідний символ шифратора позначений X, обумовлений тим, що попередній стан шифратора має значення m', а теперішній стан шифратора - m, а також призначений для визначення скалярних елементів вказаних матриць Гt імовірностей; калькулятор матричного добутку для прийому вказаних скалярних елементів Гt, визначених вказа C2 (54) ДЕКОДЕР ХВОСТОВИХ БІТІВ РЕШІТКИ (ВАРІАНТИ) ТА СПОСІБ ДЕКОДУВАННЯ КОДІВ ХВОСТОВИХ БІТІВ РЕШІТКИ (ВАРІАНТИ) 42841 довність L канальних виходів, які мають значення YLI={y1...yL}, визначеної за формулою: lt(m)=P{St=m; YLI}, причому вказаний решітковий код відповідає М станам шифратора, який відрізняється тим, що декодер виконаний з можливістю визначення L матриць Гt імовірностей, причому одна матриця відповідає кожному з L решіткових рівнів, а елементи вказаних матриць імовірностей визначаються за формулою: Гt(i, j)=P{cтaн j в час t; уt/стан і в час t-1}; шляхом визначення рядкових векторів αt, які мають М елементів сумісних імовірностей, за формулою: at(j)=Р{стан j в час t; у1,...,уt}; шляхом визначення векторів колонок bt, які мають М елементів умовних імовірностей за формулою: b t(j)=Р{yt+1, ...,yL/стан j в час t}, де j=0,1,..., (М-1), цей декодер містить Гt калькулятор для прийому вказаних канальних виходів, обчислення імовірності R(Yt,X) канального переходу, імовірності рt(m/m') того, що шифратор робить перехід із стану m' в стан m в час t, і імовірності qt(X/m', m) того, що вихідний символ шифратора позначений X, обумовлений тим, що попередній стан має значення m', а теперішній стан m, а також призначений для визначення скалярних елементів, вказаних матриць Гt імовірностей; калькулятор матричного добутку αt для отримання вказаних скалярних елементів Гt із вказаного калькулятора Гt і для визначення вказаних рядкових векторів αt; калькулятор матричного добутку βt для визначення вказаних колонкових векторів βt; калькулятор поелементного добутку для формування векторів lt сумісної імовірності, елементами яких є вказані сумісні імовірності lt(i,j); вказані калькулятор матричного добутку αt, калькулятор матричного добутку βt і калькулятор поелементного добутку виконані з можливістю формування вказаних векторів αt, βt, lt, відповідно, шляхом: (і.а) обчислення прямої рекурсії L разів, починаючи з вихідного α0=(1/М, ...,1/М), αt=αt-1Гt, t=1, …,L, і нормалізації результатів таким чином, щоб елементи кожного αt підсумовувались до одиниці, зберігаючи всі L векторів αt; (і.b) припускаючи, що α0=αL із кроку (і.а) і починаючи з t=1, обчислення αt=αt-1Гt, t=1, …, L w де L w min min ниці, зберігаючи тільки L останніх обчислених значень αt, причому ці αt попередньо знайдені на кроці (і.а); (і.е) порівняння з найближчим попередньо обчисленим αt із кроків (ii.а), (і.b) і (i.d) і переходу до кроку (іі), якщо вони в діапазоні допуска; продовження кроку (i.d), якщо два найближчі вектори не потрапляють в указаний діапазон допуску, і якщо кількість рекурсій не перевищує попередньо визначений максимум, інакше перехід до кроку (іі); (іі) визначення початкового значення βL= =(1,1,1, ...,1)T і формування попередніх зворотною рекурсією за формулою: βt=Гt+1βt+1, t=L-1, …,1; і нормалізації результатів рекурсії таким чином, щоб елементи кожного βt підсумовувались до одиниці, зберігаючи всі L векторів βt; (ііі) формування векторів lt сумісної імовірності, елементами яких є згадані сумісні імовірності lt, перемноженням елементів вказаних рядкових векторів на елементи колонкових векторів за формулою: lt(i)=αt(i)βt(i), всі і, t=1, ...,L; пам'ять для зберігання вказаних матриць імовірностей і вказаних рядкових векторів, і калькулятор імовірностей значень декодованих бітів для визначення із lt імовірності того, що отриманий біт даних, введений в шифратор в час t, дорівнює нулю, причому біт даних це m-тий з k-бітів даних, який виконує програмований вихід як функцію вказаної імовірності. 6. Декодер по п. 5, який відрізняється тим, що містить пристрій порогових рішень для отримання імовірностей того, що біт даних, введений в шифратор в час t, дорівнює нулю і для виконання правила рішення для виходу декодованих бітів. 7. Декодер по п. 5, який відрізняється тим, що код решітки хвостових бітів містить код згортки. 8. Декодер по п. 5, який відрізняється тим, що містить декодер граничних відстаней. 9. Декодер по п. 5, який відрізняється тим, що шифратор виконаний з можливістю кодування блока бітів даних, і групування вказаних бітів даних в k-бітові символи для шифрування, а попередньо визначена максимальна кількість рекурсій включає подвійну кількість k-бітових вхідних символів у блоці бітів даних. 10. Декодер хвостових бітів решітки, закодованих шифратором, які декодер декодує шляхом визначення сумісної імовірності того, що стан шифратора в час t, St, дорівнює m, і що приймається послідовність L канальних виходів, які мають значення YLI={у1...yL}, визначеної за формулою: λt(m)= =P{St=m; YLI}, причому вказаний решітковий код відповідає М станам шифратора, який відрізняється тим, що декодер виконаний з можливістю визначення L матриць Гt умовних імовірностей, причому одна матриця відповідає кожному з L решіткових рівнів, а елементи вказаних матриць імовірностей визначаються за формулою: Гt(і,j)=P{стан j в час t; уt/стан і в час t-1}; шляхом визначення рядкових векторів αt, які мають М елементів сумісних імовірностей, за формулою: αt(j)=Р{стан j в час t; у1,...,yt}; шляхом визначення векторів βt колонок, які мають М елементів умовних імовірностей за формулою: , - попередньо визначена мінімальна кіль кість стадій решітки; нормалізації результатів таким чином, щоб елементи кожного αt підсумовувались до одиниці, зберігаючи тільки останні L векторів αt, які знайдені рекурсією на кроках (і.а) і (і.b) i αLw min , знайденою на кроці (і.а); (і.с) порівняння αLw min із кроку (і.b), αLw min із кроку (і.а) і переходу до кроку (іі), якщо вони в діапазоні допуску, інакше продовження кроку (i.d); (i.d) припускаючи, що t=t+1 і обчислюючи αt= αtГt, нормалізації результатів рекурсії таким чином, щоб елементи кожного αt підсумовувались до оди 2 42841 даних і забезпечує програмований вихід як функцію вказаної імовірності. 11. Декодер по п. 10, який відрізняється тим, що містить пристрій порогових рішень для визначення імовірності того, що біт даних, введений в шифратор в час t, дорівнює нулю і для використання правила рішення для виконання декодування вихідних бітів. 12. Декодер по п. 10, який відрізняється тим, що пропонований код решітки хвостових бітів містить код згортки. 13. Декодер по п. 10, який відрізняється тим, що містить декодер граничної відстані. 14. Декодер по п. 10, який відрізняється тим, що шифратор виконаний з можливістю кодування блока бітів даних, і групування блока бітів даних в k-бітові символи для шифрування, а попередньо визначена максимальна кількість рекурсій вдвічі більша кількості вхідних k-бітових символів в блоці бітів даних. 15. Спосіб декодування кодів хвостових бітів решітки, закодованих шифратором, шляхом визначення сумісної імовірності того, що стан шифратора в час t, St, дорівнює m, і що приймається послідовність L канальних виходів, які мають значення YLI={у1 ...уL}, визначеної за формулою lt(m)= =P{St=m; YLI}, причому вказаний решітковий код відповідає М станам шифратора, який відрізняється тим, що виконують кроки для визначення L матриць Гt імовірностей, причому одна матриця, відповідає кожному з L решіткових рівнів і елементи вказаних матриць імовірностей визначають за формулою: Гt(і,j)=Р{стан j в час t; уt/стан і в час t-1}; і для визначення рядкових векторів αt, які мають М елементів сумісних імовірностей, за формулою: αt(j)=Р{стан j в час t; у1,...,уt}; і для визначення векторів колонок βt, які мають М елементів умовних імовірностей за формулою: βt(j)=Р{уt+1,...,yL/стан j в час t}; для j=0,1,..., (М-1), кроки вказаного способу включають: визначення скалярних елементів вказаних матриць Гt імовірностей із вказаних канальних виходів, імовірності R(Yt, X) канальних переходів, імовірності pt(m/m') того, що шифратор робить перехід із стану m' в стан m в час t і імовірності qt(X/m', m) того, що символ виходу шифратора є X, обумовлений тим, що попередній стан шифратора - m', а теперішній - m; обчислення матричного добутку Г1, Г2,...,ГL із вказаних скалярних елементів Гt; обчислення нормалізованого власного вектора α0 відповідно до максимального власного значення Р{YLI} вказаного матричного добутку матриць Г1, Г2,...,ГL; формування наступного αt прямою рекурсією за формулою: αt= αt-1, Гt, t=1, …,L; отримання колонкових векторів визначенням початкового значення βL=(1,1,1,...,1)T і формування попередніх βt зворотною рекурсією за формулою: βt=Гt+1βt+1, t=L-1,...,1; формування векторів lt сумісної імовірності, елементами якої є вказані сумісні імовірності lt(i,j), перемноженням елементів вказаних рядкових век βt(j)=P{yt+1,...,yL/стан j в час t}, де j=0,1,..., (М-1), цей декодер містить: Гt калькулятор для прийому вказаних канальних виходів, обчислення імовірності R(Yt, X) канального переходу, імовірності pt(m/m') того, що шифратор робить перехід із стану m' в стан m в час t, і імовірності qt(X/m', m) того, що вихідний символ шифратора позначений X, обумовлений тим, що попередній стан має значення m', а теперішній стан - m, а також призначений для визначення скалярних елементів, вказаних матриць Гt імовірностей; калькулятор матричного добутку αt для отримання вказаних скалярних елементів Гt, визначених вказаним калькулятором Гt, і отримання вказаних рядкових векторів αt; калькулятор матричного добутку βt для визначення вказаних колонкових векторів βt; калькулятор поелементного добутку для формування сумісної імовірності lt; вказані калькулятор матричного добутку αt, калькулятор матричного добутку βt і калькулятор поелементного добутку для формування вказаних векторів αt, βt і lt, відповідно, шляхом: (і.а) обчислення прямої рекурсії L разів, починаючи з вихідного α0=(1/М, ...,1/М), αt=αt-1Гt, t=1, …,L; і нормалізації результатів таким чином, щоб елементи кожного αt підсумовувались до одиниці, зберігаючи всі L векторів αt; (і.b) припускаючи, що α0=αL із кроку (і.а) і починаючи з t=1, обчислення αt=αt-1Гt, t=1,2,…, L w; де глибина циклу Lw - попередньо визначена кількість стадій решітки, нормалізація результатів таким чином, щоб елементи кожного αt підсумовувались до одиниці, замінюючи αt, обчислену на кроці (і.а), на αt, обчислену на кроці (і.b) для t=1,2,..., L w; (іі.а) визначення початкового значення βL= =(1,1,1, ...,1)T і формування попереднього βt зворотною рекурсією за формулою: βt=Гt+1βt+1, t=L-1, …,1; і нормалізації результатів рекурсії таким чином, щоб елементи кожного βt підсумовувались до одиниці, зберігаючи всі L векторів βt; (іі.b) припускаючи, що βt+1=1 із кроку (іі.а) і ГL+1=Г1, починаючи з t=L, і обчислюючи βt=Гt+1βt+1, t=L,(L-1), …,L-(Lw+1), де глибина циклу Lw - попередньо визначена кількість стадій решітки, шляхом нормалізації рекурсій так, щоб елементи кожного βt підсумовувались до одиниці, замінюючи βt, обчислене на кроці (іі.а), на βt, обчислене на кроці (іі.b) для t= =L,(L-1), ...,L-(Lw+1); (ііі) формування векторів lt сумісної імовірності, елементами яких є вказані сумісні імовірності lt(i,j), перемножуючи елементи вказаних рядкових векторів на елементи вказаних колонкових векторів за формулою: lt(i)=αt(i)βt(i), всі і, t=1,...,L; пам'ять для зберігання вказаних матриць імовірностей та рядкових векторів, і калькулятор імовірності значень декодованих бітів для визначення із l1 імовірності того, що отриманий біт даних, введений в шифратор в час t, дорівнює нулю, при цьому біт даних є m-тий із k-бітів 3 42841 торів на елементи вказаних колонкових векторів наступним чином: lt(i)=αt(i)βt(i), всі і, t=1,...,L; i визначення із lt імовірності того, що отриманий біт даних, введений в шифратор в час t, дорівнює нулю, причому біт даних є m-тий із k-бітів даних, який забезпечує програмований вихід вказаної імовірності. 16. Спосіб по п. 15, який відрізняється тим, що він включає крок дії правила рішень для декодування вихідних бітів, виходячи із імовірності того, що біт даних, введений в шифратор в час t, дорівнює нулю. 17. Спосіб по п. 15, який відрізняється тим, що в код решітки хвостових бітів уміщують код згортки. 18. Спосіб декодування кодів хвостових бітів решітки, закодованих шифратором, шляхом визначення сумісної імовірності того, що стан шифратора в час t, St, дорівнює m, і що приймається послідовність L канальних виходів, які мають значення YLI={у1 ...уL}, визначеної за формулою lt(m)= =P{St=m; YLI}, причому вказаний решітковий код відповідає М станам шифратора, який відрізняється тим, що виконують кроки для визначення L матриць Гt імовірностей, причому одна матриця відповідає кожному з L решіткових рівнів, а елементи вказаних матриць імовірностей визначають за формулою: Гt(i,j)=P{cтaн j в час t, yt/стан і в час t-1}; і для визначення рядкових векторів αt, які мають М елементів сумісних імовірностей, за формулою: αt(j)=P{cтaн j в час t; у1,...,yt}; і для визначення векторів колонок βt, які мають М елементів умовних імовірностей за формулою: βt(j)=Р{yt+1,...,yL/стан j в час t}, де j=0,1,...,(М-1), який включає кроки: визначення скалярних елементів вказаних матриць Гt імовірностей із вказаних канальних виходів, імовірності R(Yt, X) канального переходу, імовірності pt(m/m') того, що шифратор робить перехід із стану m' в стан m в час t, і імовірності qt(X/m', m) того, що вихідний символ шифратора позначений X, обумовлений тим, що попередній стан має значення m', а теперішній стан - m; формування вказаних векторів αt, βt, lt, відповідно, шляхом: (і.а) обчислення прямої рекурсії L разів, починаючи з визначення початкового значення α 0= =(1/М, ...,1/М), αt=αt-1Гt, t=1, …,L; і нормалізації результатів таким чином, щоб елементи кожного αt підсумовувались до одиниці, зберігаючи всі L векторів αt; (і.b) припускаючи, що α0=αL із кроку (і.а) і починаючи з t=1, обчислення αt=αt-1Гt, t=1, …, L w де L w min min (і.с) порівняння αLw min min із кроку (і.b), αLw min із кроку (і.а) і переходу до кроку (іі), якщо вони в діапазоні допуску, інакше продовження кроку (i.d); (i.d) припускаючи t=t+1 і обчислюючи αt=αt-1Гt, нормалізуючи результати ітерацій таким чином, щоб елементи кожного αt підсумовувались до одиниці, зберігаючи тільки останні L обчислених значень α, причому ці αt попередньо знайдені на кроці (і.а); (і.е) порівняння αt з найближчим попередньо обчисленим αt із кроків (іі.а), (і.b) і (i.d) і переходу до кроку (іі) в діапазоні; продовження кроку (i.d), якщо два найближчі вектори не потрапляють в указаний діапазон допуску і якщо кількість рекурсій не перевищує попередньо визначений максимум, інакше перехід до кроку (іі); (іі) визначення початкового значення βL= =(1,1,1, ...,1)T і формування попередніх βt зворотною рекурсією за формулою: βt=Гt+1βt+1, t=L-1,...,1; і нормалізації результатів рекурсії таким чином, щоб елементи кожного βt підсумовувались до одиниці, зберігаючи всі L векторів βt; (ііі) формування векторів λt сумісної імовірності, елементами яких є згадані сумісні імовірності λt(i,j), перемноженням елементів вказаних рядкових векторів на елементи колонкових векторів за формулою: λt(i)=αt(i)βt(i), всі і, t=1, ...,L; i визначення із λt імовірності того, що отриманий біт даних, введений в шифратор в час t, дорівнює нулю, причому біт даних є m-тим з k-бітів даних, і забезпечення програмованого виходу як функції вказаної імовірності. 19. Спосіб по п. 18, який відрізняється тим, що включає крок виконання правила рішень для декодування вихідних бітів, виходячи із імовірності того, що біт даних, введений в шифратор в час t, дорівнює нулю. 20. Спосіб по п. 18, який відрізняється тим, що в пропонований код решітки хвостових бітів уміщують код згортки. 21. Спосіб по п. 18, який відрізняється тим, що шифратор кодує блок бітів даних, а вказані біти даних групуються в k-бітові символи для шифрування, а попередньо визначена максимальна кількість рекурсій включає вдвічі більшу кількість k-бітових вхідних символів в блоці бітів даних. 22. Спосіб декодування кодів хвостових бітів решітки, закодованих шифратором, які декодер декодує шляхом визначення сумісної імовірності того, що стан шифратора в час t, St, дорівнює m, і що спостерігається послідовність L канальних виходів, які мають значення YLI={y1 ... yL}, визначеної за формулою λt(m)=P{St=m; YLI}, причому вказаний решітковий код відповідає М станам шифратора, який відрізняється тим що виконують кроки для визначення L матриць Гt умовних імовірностей, причому одна матриця відповідає кожному з L решіткових рівнів, а елементи вказаних матриць імовірностей визначають за формулою: Гt(i,j)=P{cтaн j в час t; уt/стан і в час t-1}; і для визначення рядкових векторів αt, які мають М елементів сумісних імовірностей, за формулою: αt(j)=P{cтaн j в час t; у1,...,yt}; і для визначення векторів колонок βt, які мають М елементів умовних імовірностей за формулою: , - попередньо визначена мінімальна кіль кість стадій решітки; нормалізації результатів таким чином, щоб елементи кожного αt підсумовувались до одиниці, зберігаючи тільки останні L векторів αt, які знайдені рекурсією на кроках (і.а) і (і.b), і αLw , знайдену раніш на кроці (і.а); 4 42841 (ii.b) припускаючи, що βL+1 дорівнює β1 із кроку (іі.а) і ГL+1=Г1, починаючи з t=L, і обчислення βt=Гt+1βt+1, t=L,(L-1),...,L-(Lw+1), βt(j)=P{yt+1,...,yL/cтaн j в час t}; де j=0,1,..., (М-1), який включає кроки: визначення скалярних елементів вказаних матриць Гt імовірностей із вказаних канальних виходів, імовірності R(Yt, X) канального переходу, імовірності рt(m/m') того, що шифратор робить перехід із стану m' в стан m в час t, і імовірності qt(X/m', m) того, що вихідний символ шифратора позначений X, обумовлений тим, що попередній стан має значення m', а теперішній стан - m; формування вказаних векторів αt, βt, λt, відповідно, шляхом: (і.а) обчислення прямої рекурсії L разів, виходячи з початкового α0=(1/М, ...,1/М), за формулою: αt=αt-1Гt, t=1,...,L; і нормалізації результатів таким чином, щоб елементи кожного αt підсумовувались до одиниці, зберігаючи всі L векторів αt; (і.b) припускаючи, що α0=αL із кроку (і.а) і починаючи з t=1, обчислення αt=αt-1Гt, t=1,..., де глибина циклу L w - попередньо визначена мінімальна кількість стадій решітки, нормалізації результатів таким чином, щоб елементи кожного βt підсумовувались до одиниці, замінюючи βt, обчислене на кроці (іі.а), обчисленим на кроці (ii.b) для t=L,(L-1), ...,L-(Lw+1); (ііі) формування λt векторів сумісної імовірності, елементами яких є згадані сумісні імовірності λt, перемноженням елементів вказаних рядкових векторів на елементи колонкових векторів за формулою: λt(i)=αt(i)βt(i), всі і, t=1, ...,L; визначення із λt імовірності того, що отриманий біт даних, введений в шифратор в час t, дорівнює нулю, причому біт даних є m-тим з k-бітів даних, і виконує програмований вихід як функцію вказаної імовірності. 23. Спосіб по п. 22, який відрізняється тим, що включає крок виконання правила рішень для декодування вихідних бітів із імовірності того, що біт даних, введений в шифратор в час t, дорівнює нулю. 24. Спосіб по п. 22, який відрізняється тим, що в пропонований код решітки хвостових бітів уміщують код згортки. 25. Спосіб по п. 22, який відрізняється тим, що шифратор кодує блок бітів даних, а вказані біти даних групуються в k-бітові символи для шифрування, а попередньо визначена максимальна кількість рекурсій включає більшу кількість k-бітових вхідних символів в блоці бітів даних. L w, де глибина циклу L w - попередньо визначена мінімальна кількість стадій решітки, нормалізації результатів таким чином, щоб елементи кожного αt підсумовувались до одиниці, замінюючи αt, обчислене на кроці (і.а), обчисленим на кроці (і.b), для t=1,2,..., Lw; (іі.а) визначенням початкового значення βL= =(1,1,1, ...,1)T і формуванням попередніх βt зворотною рекурсією за формулою: βt=Гt+1βt+1, t=L-1,...,1; і нормалізації результатів рекурсії таким чином, щоб елементи кожного βt підсумовувались до одиниці, зберігаючи всі L векторів βt; нувати тільки апроксимацію цих імовірностей. Варіанти алгоритму виводять відносну інформацію, таку як імовірний розподіл символів даних на кожній стадії або розподіл закодованих вихідних символів на кожній стадії. Для роботи МАР-декодера необхідно, щоб був відомий початковий стан передачі кодів решітки, і в деяких випадках знання також і кінцевого стану. Тому, на жаль, МАР-декодер не може використовуватися для декодування кодів з хвостовими бітами, тобто кодів для яких початковий і кінцевий стан шифратора наперед невідомі. Зокрема, передача кодів решітки відома як кодування хвоста бітів, коли початковий стан кодування ідентичний можливому кінцевому стану для даного блоку вхідних бітів. На початку кодування основним для шифратора прямопрохідних даних (без накопичення в буфері) є знання бітів даних, які будуть відповідати кінцевому стану; звичайно це останні kmбіти блоку повідомлення, де k - кількість бітів кожного символа, що кодується, а m - кодова пам'ять. Шифратор для кодування хвостових бітів необхідно відрізняти від звичайного шифратора, в якому початковий стан встановлюється наперед, як правило, всі нулі. Звичайні шифратори можуть також залишатися в наперед заданому стані, добавляючи "хвіст" бітів km у вхідний блок повідомлень. Відмінною особливістю декодера хвостових бітів окрім виконання інших функцій є необхідність оцін Цей винахід відноситься до декодерів для коригування помилок кодів і зокрема, до декодера для кодування хвостових бітів кодової решітки. Алгоритм Вітербі (VA) - це максимально вірогідний метод декодування, який визначає найімовірнішу послідовність даних, або слово, для випадку наявності в каналах "адитивних білих Гаусівських" шумів, тобто мінімізує імовірність помилки слова, що декодується. Ця схема мас особливе значення для динамічних програм знаходження шляху через код решітки, найкоротшого для одержаної послідовності канальних виходів. З іншої сторони, імовірність помилки символа або біта мінімізується за допомогою використання так-званого максимального пост МАР-декодера. МАР-декодер вперше був сформульований і описаний Болом, Коком, Желинеком і Равивом ("BCJR-алгоритм") в "Оптимальному декодуванні лінійних кодів для мінімізування рівня символьних помилок" IEEE Transactions on Information Theory, pp. 284-287, Март, 1974. (прототип). Термін МАРдекодер або BCJR-алгоритм, тут означає декодер даних, котрий виводить розподіл імовірності станів на кожній стадії решітки і який також може вміщувати наперед відому статистику бігових даних. МАР-декодер являється оптимальним засобом для прогнозування статистики цих імовірних станів ("програмний вихід") з винятковою точністю, в той час як існуючі більш прості декодери можуть вико 5 42841 ки початкового стану шифратора. Оскільки шифратор хвостових бітів має циліндричну решітку, кодоване слово, зашифроване таким способом шифратором, може бути зображено у вигляді символів, розташованих по кругу. Декодер повинен починати роботу з деякої довільної точки на крузі, ввійти в стан синхронізації і потім декодувати біти даних. За аналог декодерів хвостових бітів був вибраний VA-декодер, який; виконує максимально вірогідну оцінку кодованого слова циліндричної решітки. З іншого боку, декодер програмного виходу повинен оцінити імовірність станів за межами циліндричної решітки, а в теперішній час такі декодери невідомі. Зокрема, як вказувалось вище, для програмного МАР-декодера необхідно знати початковий стан в решітці, а в деяких випадках і кінцевий стан. Отже, застосування МАР-декодера обмежується звичайним кодуванням без "хвоста", що в свою чергу, позбавляє його переваги покращання якості систем корекції помилок при передачі коротких блоків даних (пакетна передача), і для яких необхідний цей програмний продукт. В зв'язку з цим бажано, щоб декодер хвостових бітів решітки був точним і простим у виконанні. Відповідно до винаходу, що пропонується, циркулярний МАР-декодер для коригування помилок кодів хвостових бітів забезпечує виходи програмних рішень. Циркулярний МАР-декодер виконує оцінку імовірностей станів на першому рівні решітки, які замінюють вхідну інформацію в послідовному МАР-декодері. Винаходом, який пропонується, циркулярний МАР-декодер виконує розподіл імовірностей початкового стану одним з двох способів. Перший спосіб включає визначення результуючого значення власного вектору, яке повинно відповідати необхідному розподілу імовірностей початкового стану; при наявності інформації про початковий стан, циркулярний МАР-декодер виконує подальше декодування згідно з алгоритмом декодування МАР. Другий спосіб базується на рекурсії, яка включає конвергенцію ітерацій до розподілу початкового стану. Після отримання достатньої кількості ітерацій, стан на круговій послідовності стає відомим з високою імовірністю. Після цього циркулярний МАР-декодер виконує подальше декодування згідно з МАР-алгоритмом декодування. Винахід пояснюється кресленнями. Особливості і переваги, якими відрізняється цей винахід, стануть наявними в процесі ознайомлення з детальним описом винаходу, а також з ілюструючими його кресленнями, в яких: фіг. 1 ілюструє циліндричну решітку чотирьох станів кодів хвостових бітів у вигляді бінарних вхідних символів; фіг. 2 ілюструє стан циркулярного шифратора і вихідні послідовності для кодів решітки хвостових бітів; фіг. 3 представляє спрощену блок-схему, яка показує одну з можливих конструкцій циркулярного МАР-декодера, яка відповідає цьому винаходу; фіг. 4 ілюструє часову криву для циркулярного МАР-декодера згідно з цим винаходом; фіг. 5 ілюструє часову криву для оптимального варіанту конструкції циркулярного МАР-декодера згідно з цим винаходом; фіг. 6 представляє графік, який ілюструє залежність коефіцієнту помилкових бітів від співвідношення сигналу до шуму для циркулярного МАР-декодера при коефіцієнті, який дорівнює 1/2 при декодуванні і пам'яті, яка дорівнює коду згортки з 6 хвостових бітів згідно з цим винаходом; фіг. 7 представляє графік, який ілюструє залежність коефіцієнту помилкових бітів від співвідношення сигналу до шуму на основі статистики джерел помилок для циркулярного МАР-декодера при коефіцієнті, який дорівнює 1/2 при декодуванні і пам'яті, яка дорівнює коду згортки з 6 хвостових бітів згідно з цим винаходом; і фіг. 8 ілюструє спрощену блок-схему оптимального варіанту конструкції циркулярного МАРдекодера згідно з цим винаходом. Шифратор хвостових бітів має форму циліндричної решітки; тобто слово, яке кодується таким шифратором, можна уявити як круг символів. На фіг. 1 наведений приклад циліндричної решітки для шифратора хвостових бітів, яка мас чотири стани і бінарні вхідні символи. Недостатня кількість вхідних даних, враховуючи початковий стан шифратора при кодуванні такої решітки хвостових бітів, знижує надійність декодування за стандартним МАР (або BCJR) -алгоритмом для першої частини отриманого повідомлення. Послідовність виходу шифратора для кодування хвостових бігів решітки утворює круговий шаблон, як показано на фіг. 2. Стани шифратора зображені розташованими по кругу. Якщо умовно прийняти S0 за один з таких станів, то шифратор починає виконувати процес кодування із стану S0 зсувного регістру в час t0 і після проходження по кругу, переходячи з одного стану в інший, закінчує знову в тому ж стані S0. Декодер, що працює із зашифрованою круговою послідовністю і при цьому з кожним зашифрованим станом в цій послідовності і є декодером хвостових бітів або циркулярним декодером. Згідно з зим винаходом, циркулярний МАР-декодер для коригування помилок кодів решітки, які є хвостовими бітами, забезпечує виходи програмованих рішень. Навпаки, послідовний МАР-декодер отримує початковий стан або вузол решітки; потім він декодує шлях решітки шифратора, який виходить з цього стану. Однак, декодер хвостових бігів повинен спочатку ідентифікувати стан зашифрованої послідовності і тільки потім починати декодування. Циркулярний МАР-декодер, згідно з цим винаходом, виконує оцінку імовірностей станів на першому рівні решітки, імовірності яких замінюють вхідну інформацію в послідовному МАР-декодері. Винаходом, який пропонується, циркулярний МАРдекодер виконує розподіл імовірностей початкового стану одним з двох способів. Перший спосіб включає визначення результуючого значення власного вектору, яке повинно відповідати необхідному розподілу імовірностей початкового стану; при наявності інформації про початковий стан, циркулярний МАР-декодер виконує подальше декодування згідно з алгоритмом декодування МАР (або BCJR). Другий спосіб базується на деякій визначеній рекурсії, яка включає конвергенцію ітерацій до 6 42841 розподілу початкового стану. Після отримання достатньої кількості ітерацій, стан на круговій послідовності стає відомим з високою імовірністю. Після цього циркулярний МАР-декодер виконує подальше декодування згідно з МАР (або BCJR)-алгоритмом декодування. Метою послідовного МАР (або BCJR)-алгоритму декодування є знаходження умовних імовірностей: Р{стан m в час t/ одержані канальні виходи у1...,уL}. Термін L в цьому виразі означає довжину блоку одиничних даних, які відповідають кількості зашифрованих символів. (Шифратор для (n, k) коду оперує k-бітами вхідних символів для отримання n-бітів вихідних символів). Термін yt - це канальний вихід (символ) в час t. Фактично МАР-алгоритм декодування спершу знаходить імовірності: λt(m)=P{St=m; YLl}, (1) що означає сумісну (спільну) імовірність того, що стан шифратора в час t, St дорівнює m і що одержана послідовність канальних виходів виражається формулою YLl={y1...yL}. Вони отримуються множенням необхідних імовірностей на константу (P{YLl} - імовірність отримання послідовності канальних виходів {у1...,уL}). Тепер визначаються елементи матриці Гt за формулою: Гt(ij)=P{cтaн j в час t; /стан і в час t-1}. Матриця Гt обчислюється як функція імовірності канальних переходів R(Yt, X), імовірності pt(m/m') того, що шифратор робить перехід із стану m' в m в час t, і імовірності qt(X/m', m) того, що символ виходу шифратора є X, який показує що попередній стан шифратора був m', а дійсний стан шифратора є m. Зокрема, кожний елемент Гt обчислюється сумуванням всіх можливих виходів шифратора X за формулою: γt(m',m)= å pt(m/m')qt(X/m',m)R(yt,X) Отже вихід програмного рішення декодера обчислюється за формулою: Р{djt=0/YlL}= де: 1 å λ t (m) P{YlL } St εA tj P{YlL } = å λ L (m) і m m - індекс, який відповідає стану St. Жорстке рішення декодера або вихід декодованого біту отримується застосуванням Р{djt= =0/YlL} до наступного правила рішень: ˆ d tj = 0 Р{djt=0/YlL} > 1/2, то d tj = 0 ; ˆ якщо Р{djt=0/YlL}