UA75863C2

UA75863C2 - Serial viterbi decoder (variants) and a method of serial viterbi decoding

Info

Publication number: UA75863C2
Application number: UA2001010727A
Authority: UA
Original assignee: Qualcomm Inc
Priority date: 1998-08-04
Filing date: 1999-04-08
Publication date: 2006-06-15
Also published as: CA2339257A1; RU2236084C2; ID28514A; CN1321363A; JP2002522944A; WO2000008769A1; CN1164040C; US6269130B1; BR9912705A; AU763225B2; ZA200100914B; KR20010072210A; EP1103101A1; HK1038449A1; NZ509695A; IL141228A0; AU5335799A

Description

Опис винаходу

Винахід взагалі стосується послідовних декодерів Вітербі, зокрема послідовних декодерів Вітербі, 2 призначених для використання у безпровідних системах зв'язку з паралельним доступом і кодовим ущільненням каналів (ПДКУ).

Фіг.1 містить блок-схему системи 10 ПДКУ з змінною швидкістю передачі, описану у внутрішньому стандарті

ТІА/ЕІА/5-95-А Асоціації телекомунікацій (ТА) (Стандарт сумісності мобільних і базових станцій для стільникових систем широкого спектру подвійного режиму). Ця передавальна система може бути реалізована, 70 наприклад, у базовій станції стільникової системи передачі для передачі сигналів до мобільних телефонів у комірці, що оточує базову станцію.

Вхідною лінією 11 позначено сигнал мови або даних, який може бути цифровим або аналоговим. Ця вхідна лінія може бути аналоговим або цифровим каналом зв'язку комунальної комутаторної телефонної мережі (ККТМ) або іншого джерела мовного сигналу. Якщо вхідний мовний сигнал є аналоговим, сигнал квантується і 12 цифрується у АЦП (не показаному). Джерело 12 даних змінної швидкості приймає цифровані порції мовного сигналу і кодує цей сигнал, щоб одержати пакети, тобто кадри кодованої мови однакової довжини. Джерело 12 даних може, наприклад, перетворювати цифровані порції вхідної мови у цифрові параметри, які репрезентують вхідний голосовий сигнал, використовуючи для цього процедуру лінійного кодування з прогнозуванням (ЛКП). У одному з втілень джерелом даних змінної швидкості є вокодер змінної швидкості, (описаний у патенті США 5 414 796). Таке джерело створює пакети даних змінної швидкості з одною з чотирьох швидкостей у кадрі - 9600біт/с, 4800біт/с, 240Обіт/с і 1200біт/с, які називають повною швидкістю, половинною швидкістю, швидкістю 1/2 і швидкістю 1/8. Пакети, кодовані з повною швидкістю містять 172 інформаційних біт, кодовані з половинною швидкістю - 80 інформаційних біт, кодовані з швидкістю 1/4-40 інформаційних біт і кодовані з швидкістю 1/8-16 інформаційних біт. Незалежно від розміру пакети мають тривалість 2Омс. У інших системах можуть с використовуватись інші швидкості даних і інші розміри пакетів. У цьому тексті терміни пакет і кадр є синонімами. Ге)

Пакети кодуються і передаються з різними швидкостями для компресування даних залежно почасти від складності або кількості інформації, репрезентованої кадром. Наприклад, якщо вхідний голосовий сигнал не має варіацій або варіації малі, можливо, тому, що промовлювач не розмовляє, інформаційні біти відповідного пакету компресуються і кодуються з швидкістю 1/9. Таке компресування призводить до втрати розрізнення у відповідній о дастині голосового сигналу, але, оскільки ця частина несе малу кількість або зовсім не несе інформації, це Ге) зниження розрізнення звичайне Е непомітним. Якщо ж вхідний голосовий сигнал, що відповідає пакету, несе багато інформації, можливо, внаслідок активної розмови, пакет кодується з повною швидкістю і інформаційні со біти пакету не зазнають компресії. ою

Такі компресія і кодування використовуються для обмеження середньої кількості сигналів, що передаються одночасно, і завдяки цьому смуга частот передавальної системи використовується більш ефективно, що - дозволяє одночасно обробляти більшу кількість телефонних сеансів зв'язку.

Пакети змінної швидкості, які створює джерело 12 даних, надходять до пакетувальника 13, який селективно додає біти КЦН (код циклічної надмірності) і хвостові біти, і від нього - до кодера 14, який кодує біти цих « пакетів для виявлення і корекції помилок. У одному з втілень кодер 14 є згортаючим послідовним кодером З 50 Вітербі. Кодовані з згорткою символи надсилаються до модулятора 16, який генерує модульований сигнал. с Такий модулятор (описано у патентах 5 103 459 і 4 901 307). Модульований сигнал надходить до ЦАП 22 для

Із» перетворення у аналоговий сигнал і потім до передавача 24, який підсилює сигнал і підвищує його частоту для передачі антеною 26.

Фіг.2 ілюструє відповідні компоненти мобільного телефону 28 або іншої мобільної станції, що приймає переданий сигнал. Антена 30 приймає цей сигнал, після чого він підсилюється і його частота знижується, якщо це. необхідно, у приймачі 31. Далі сигнал де-модулюється демодулятором 32 у потік символів, які залишаються сл кодованими з згорткою. Після цього сигнал надходить до послідовного декодера 34 який декодує цей потік символів і також розділяє прийнятий сигнал на пакети і визначає відповідну кадрову швидкість для кожного з бо пакетів. Цю швидкість можна визначити, наприклад, через тривалість окремих біт кадру. Опис типового

Ге»! 20 послідовного декодера Вітербі можна знайти |у заявці 08/126 477 на патент США від 24/09/1993), включеній сюди посиланням. с» Для декодування потоку символів у декодері 34 передбачено використання відгалуженого блоку 36 метрики помилок, який приймає символи від модулятора, і блок 38 до-дання-порівняння-обрання (ДПО), який генерує біти рішення, грунтуючись на символах. Для підвищення ефективності декодер крокує назад від того, що він вважає 25 метрикою найкращого режиму, використовуючи для цього блок 40 зворотних кроків, який обробляє біти рішення,

ГФ) прийняті від ДПО 38. У кожному циклі обробки блок зворотних кроків зберігає у пам'яті 41 зворотних кроків 2 юю біт рішення, де К - довжина обмеження коду декодера. Режим, що відповідає найнижчій метриці найкращого режиму, передається від ДПО до блоку зворотних кроків як найкращий режим.

Після завершення Г/. циклів обробки починається утворення ланцюжка зворотних кроків, яке здійснюється під 60 керуванням контролера 42 зворотних кроків. Утворення ланцюжка зворотних кроків починається з зчитування з пам'яті зворотних кроків біт рішення для найкращого режиму попереднього (1-1) циклу обробки. Зчитаний біт рішення зсувається на місце наймолодшого біту найкращого стану. Далі блок зворотних кроків зчитує з пам'яті зворотних кроків біти рішення для найкращого режиму циклу 1-2 обробки. Ця процедура виконується Г. разів з зчитуванням наприкінці біт рішення для найкращого режиму циклу 0 обробки. Останній біт рішення є бітом бо декодованої інформації. Кожний зчитаний біт модифікує адресу наступного зчитування. У наступному циклі обробки (І 41) вся процедура повторюється, причому біти рішення щодо режиму зчитуються з циклів від І до 1.

Це продовжується протягом стількох циклів обробки, скільки потрібно для одержання необхідної кількості інформаційних біт у даній системі.

Фіг.3 ілюструє приклади виконання зворотних кроків. Якщо процедура зворотних кроків виконується після 4 циклів обробки і після цих циклів найкращому режиму відповідає код 101, то зчитування, що виконуються для завершення процедури зворотних кроків, позначено входами, затемненими сірим. Буде зчитаний перший режим 101 циклу З обробки, потім режим 011 циклу 2, потім режим 111 циклу 1, потім режим 110 циклу 0, що дасть вихідний біт рішення 0. Якщо на початку циклу 5 обробки найкращому режиму відповідає код 010, то перші /о результати зчитування дадуть найкращий режим 101. Отже, наступні три зчитування будуть здійснені, як і раніше, а саме, як послідовність кроків, затемнених сірим. Цього разу, хоча вихідний біт рішення зчитаний з циклу 1, результуючий біт рішення буде 0. Якщо на початку циклу 6 обробки найкращому режиму відповідає код 001, то перші результати зчитування дадуть найкращий режим 010, а наступні три зчитування будуть здійснені, як і раніше, причому вихідний біт рішення зчитаний з циклу 2 і результуючий біт рішення будуть 1.

Декодер 34 (Фіг.2) формує декодований пакет разом з сигналом, що ідентифікує кадрову швидкість у цьому пакеті, які надсилаються до вузла 43 перевірки якості кадру, який намагається підтвердити відсутність помилок передачі або помилок визначення кадрової швидкості. У типовому втіленні вузол 43 перевіряє КЦН, частоту появи хибних символів і метрику Ямамото. Для перевірки частоти появи хибних символів вузол 43 перевірки рекодує символи декодованого пакету і порівнює рекодовані символи з символами, уведеними у вузол 43 для 2о виявлення розбіжностей. Для перевірки метрики Ямамото вузол 43 перевірки надсилає прийняті кадри до матричного декодера і визначає прийнятність одержаної метрики. Прийнятні кадри спрямовуються до декодера 44 мови для перетворення назад у цифрові голосові сигнали. Ці сигнали перетворюються у аналогові у ЦАП (не показаному) для одержання вихідного сигналу, що подається до гучномовця 46 мобільного телефону, завдяки чому оператор може чути мову, введену у систему (лінія 11 Фіг.1). сч

Мобільний телефон (Фіг.2) може мати додаткові компоненти для введення аналогового мовного сигналу від оператора і для обробки і передачі сигналу з використанням ПДКУ. Ці додаткові компоненти можуть бути і) подібними до зображених на Фіг.1. Крім того передавальна система Фіг.1 може мати додаткові компоненти для прийому сигналів, переданих стільниковим телефоном, їх обробки і надсилання вихідного аналогового або цифрового мовного сигналу, наприклад, у лінію ККТМ. Додаткові компоненти Фіг.ї1 можуть бути подібними до с зо зображених на Фіг.2.

Отже, важливим компонентом усієї системи є послідовний декодер Вітербі, призначений декодувати передані со символи. Як уже відзначалось, у декодері 34 використовується процедура зворотних кроків. Для одержання со суттєвого підвищення ефективності довжина ланцюжка зворотних кроків має у З - 5 разів перевищувати довжину обмеження кодера (К-9 для ПДКУ), причому ефективність зростає з зростанням довжини ланцюжка зворотних о кроків. Однак, при цьому збільшуються розміри схеми і зростає споживання енергії. Збільшення розмірів схеми ї- зумовлюється потребою у більшій пам'яті для зберігання біт рішення ланцюжка зворотних кроків. Наприклад, для декодера з довжиною обмеження К для кожного інформаційного біту треба зберігати 2 КК біт рішення. При довжині ланцюжка зворотних кроків І. необхідно зберігати 1721 біт, Споживання енергії зростає тому, що для « формування одного біту даних необхідно виконати | зчитувань. Крім того, зростає затримка на виконання зворотних кроків. Подібно до системи з ПДКУ з використанням декодера Вітербі такі ж проблеми виникають і у - с інших системах, де використовуються такі і подібні їм декодери. а Отже, бажано винайти спосіб суттєвого зниження споживання енергії і часу на обробку у блоці зворотних "» кроків при невеликому збільшенні розмірів схеми. Це і є головним об'єктом винаходу.

Однією з задач винаходу є удосконалення послідовного декодера Вітербі, призначеного для декодування потоку кодованих з згорткою символів з використанням пам'яті зворотних кроків для зберігання біт рішення для -і кожного з сукупності циклів обробки. Удосконалення полягає у запровадженні кешу зворотних кроків, пов'язаного сл з пам'яттю зворотних кроків і призначеного для зберігання біт рішення, визначених у попередньому циклі обробки. (ее) У одному з типових втілень послідовний декодер Вітербі включає відгалужений блок метрики помилок, ДПО, б» 50 блок зворотних кроків з пам'яттю, повний кеш зворотних кроків і контролер зворотних кроків. Кеш зворотних кроків може приймати усі зчитування. Інше типове втілення не передбачає повного кешу зворотніх кроків, але сю блок зворотних кроків включає пам'ять на І 1 біт (тут і далі вважається, що це пам'ять з довільним доступом (КАМ)), реверсивний лічильник і зсувний регістр, що емулюють кеш зворотних кроків. У ще одному втіленні використовується зсувний регістр на | біт замість комбінації пам'яті на І 41 біт з реверсивним лічильником. У різних втіленнях блок зворотних кроків пристосований виконувати лише одне зчитування зворотних кроків у кожному циклі обробки або виконувати т зчитувань зворотних кроків у кожному циклі обробки перед спробою о використати кеш. У інших втіленнях блок зворотних кроків пристосовано виконувати а і потім Б зчитувань іме) протягом кожної процедури зворотних кроків, причому після а зчитувань кеш перевіряється для кожного чергового зчитування, доки у кожній процедурі зворотних кроків не буде виконано Б зчитувань або доки на буде 60 досягнуто збігу. У ще одному втіленні блок зворотних кроків пристосовують виконувати процедури зворотних кроків для багатьох циклів обробки, а не єдиного такого циклу. Винахід включає також різні комбінації елементів цих втілень.

У різних втіленнях застосування кеш-пам'яті для біт рішення з попередніх циклів обробки дозволило досягти значних знижень споживання і витрат часу на обробку з лише незначним ускладненням схем. 65 Особливості, об'єкти і переваги винаходу наведені у подальшому детальному описі з посиланнями на креслення, у яких:

Фіг.1 - блок-схема компонентів передавальної системи змінної швидкості з ПДКУ,

Фіг2 - блок-схема компонентів мобільного телефону або іншої мобільної станції, що приймає сигнал, переданий передавальною системою з ПДКУ (Фіг.1) і декодує сигнал декодером Вітербі, який містить блок

Зворотних кроків,

Фіг.3 - схема процедури зворотних кроків, яку виконує блок зворотних кроків мобільного телефону Фіг.2,

Фіг.4 - блок-схема, що на вищому рівні ілюструє відповідні компоненти мобільного телефону або іншої мобільної станції, у якій, згідно з винаходом, використано послідовний декодер Вітербі з блоком і кешем зворотних кроків, 70 Фіг.5А, 58 - детальна ілюстрація першого втілення блоку зворотних кроків мобільного телефону Фіг.4,

Фіг.бА, 68 - детальна ілюстрація другого втілення блоку зворотних кроків мобільного телефону Фіг.4,

Фіг.7 - частина третього втілення блоку зворотних кроків мобільного телефону Фіг.4.

Фіг.4 ілюструє належні компоненти мобільного телефону 128 або іншої мобільної станції, що приймає переданий сигнал ПДКУ. Вузли мобільного телефону 128 працюють подібно до телефону Фіг.2 і будуть описані /5 лише побіжно.

Антена 130 приймає сигнал, після чого він підсилюється і його частота знижується, якщо необхідно, у приймачі 131. Далі сигнал демодулюється демодулятором 132 з перетворенням у потік символів, кодованих з згорткою. Після цього сигнал надходить до модифікованого послідовного декодера 134, який декодує цей потік символів, використовуючи відгалужений блок 136 метрики помилок, ДПО 138 і блок 140 зворотних кроків. Блок 140 має пам'ять 141 зворотних кроків, контролер 142 зворотних кроків і кеш 145 зворотних кроків, призначений лише для зчитувань. Режим, що відповідає найнижчій метриці найкращого режиму, передається від ДПО до блоку зворотних кроків як найкращий режим, і зберігається у пам'яті зворотних кроків, а також у кеші зворотних кроків, звідки вони можуть бути легко зчитані. Як буде описано нижче, декодер не обов'язково має фактично включати повну окрему кеш-пам'ять, як це показано на Фіг.4. Однак, у подальшому описі для кращого сч ов розуміння роботи системи зворотних кроків з кешем ми вважатимемо, що використовується повна кеш-пам'ять.

Процедура зворотних кроків з використанням кеш-пам'яті (Фіг.43 виконується шляхом зчитування з кешу 145 і) зворотних кроків біт рішення, що визначають метрику найкращого режиму, якщо поточна метрика найкращого режиму, обчислена після одного зчитування у новому циклі обробки, збігається з початковою метрикою найкращого режиму останнього циклу обробки. У випадку незбігу цих метрик виконуються звичайні зворотні со зо Кроки. Зокрема, на початку циклу обробки метриці найкращого режиму призначається змінна епсзіай(е. З пам'яті зворотних кроків зчитується перший біт рішення, місце якого визначається через епсзіайе, і зсувається у ісе) наймолодший біт епсзіаі(е. Далі нове значення епсзіаге порівнюється з параметром, позначеним Іазі бБезівіаїйе, со який містить метрику найкращого режиму попереднього циклу обробки. Якщо значення збігаються, зникає потреба у виконанні додаткових 1-1 зчитувань для завершення процедури зворотних кроків. Завершальний біт о зв Може бути просто зчитаний з кешу (епсзіаїе і Іазі ревівіаїе не показані на Фіг4, але є у інших Фіг. ї- розглянутих далі). Якщо необхідно виконати І-1 додаткових зчитувань, блок зворотних кроків зчитує з пам'яті зворотних кроків біти рішення, які відповідають значенню епсзіа(е для біт рішень, записаних протягом циклу обробки 1-2. Ця процедура виконується усі І. разів з зчитуванням наприкінці біту рішення обчисленого епсвіаіе для циклу обробки 0. Цей остаточний біт рішення є декодованим інформаційним бітом. Кожний зчитаний біт «

Змінює адресу для подальшого зчитування. У наступному циклі обробки (14-41) процедура повторюється з з с зчитуванням біт рішення для режиму для циклів обробки від І до 1. Це продовжується протягом стількох циклів

Й обробки, скільки потрібно для одержання необхідної кількості інформаційних біт у даній системі. и?» Після завершення звичайної процедури зворотних кроків, уся послідовність біт рішення, генерована цією процедурою, зберігається у кеші 145 зворотних кроків і, отже, зникає необхідність виконувати повну процедуру зворотних кроків у наступному циклі обробки. Зокрема, після зворотних кроків першого циклу обробки у -І подальших циклах обробки перше зчитування призведе до прийняття змінною епсвзіаге значення, яке вона мала на початку попереднього циклу і тому значення епсзіа(е збігатиметься з значенням Іазі Брезівіаіе. Це має місце 1 не завжди, але у більшості випадків внаслідок властивості шляхової конвергенції, притаманної кодам з

Го! згорткою. Отже, найбільш імовірно, що у даному циклі обробки 1-1 зчитувань будуть такими ж, як у попередньому циклі і остаточний біт рішення буде попереднім до останнього біту, зчитаного у попередньому

Ме, циклі. Таким чином, використання кешу зворотних кроків дозволяє просто зчитати з кешу біти рішення |І-1 сю зчитувань, включаючи остаточний біт рішення, без повторного обчислення, що підвищує ефективність роботи.

Декодер 134 формує декодований пакет разом з сигналом, що ідентифікує кадрову швидкість у цьому пакеті, і надсилає їх до вузла 143 перевірки якості кадру, який намагається підтвердити відсутність помилок передачі або помилок визначення кадрової швидкості, використовуючи для цього перевірку КЦН, частоти появи хибних символів і метрики Ямамото. Прийнятні кадри спрямовуються до декодера 144 мови для зворотного

Ф) перетворення у цифрові голосові сигнали. Ці сигнали перетворюються у аналогові у ЦАП (не показаному) для ка одержання вихідного сигналу, що подається до гучномовця 146 мобільного телефону. Мобільний телефон (Фіг.4) може мати додаткові компоненти (не показані) для введення аналогового мовного сигналу від оператора і для во обробки і передачі сигналу з використанням ПДКУ. Ці додаткові компоненти можуть бути подібними до зображених на Фіг.1.

Отже, Фіг.4 ілюструє на високому рівні мобільний телефон, оснащений послідовним декодером Вітербі, який має блок зворотних кроків з повним окремим кешем зворотних кроків, пристосованим для зберігання зчитувань.

Логіка кеш-пам'яті за своєю природою забезпечує зберігання копії біт рішення різних зчитувань у її власній 65 пам'яті. Загальної економії енергії можна досягти, якщо споживання енергії кеш-пам'ятью не перевищує зниження споживання, зумовленого відповідною відмовою від доступу до пам'яті зворотних кроків. Крім того,

залежно від втілення може бути знижений час на декодування порівняно з часом, що витрачається без використання кешу. Такий виграш часу зумовлюється тим, що у випадку збігу система виконує лише одне зчитування з кешу замість Ї-1 додаткових зчитувань з пам'яті зворотних кроків, якщо збігу не одержано.

Зниження часу на декодування є особливо значним у системах, де пам'ять зворотних кроків працює повільно, а кеш швидко.

Порівняння роботи блоку зворотних кроків з кешем і таких же блоків без нього дає такі результати. У системі стандарту І5-95 для каналу швидкості 1 з відносною кількістю помилок 195 послідовний декодер Вітербі без кешу може виконати 289 процедур зворотних кроків з І/-63. Відзначимо, що останні 72 біти пакету /о одержуються однією процедурою зворотних кроків. Повна кількість зчитувань з пам'яті зворотних кроків становить 289763-18207. Для 100 кадрів даних епсзіаїе після одного зчитування збігається з значенням резівіаїе попереднього циклу обробки у середньому приблизно 233 рази на кадр (з 289 процедур зворотних кроків). Отже, при використанні кешу у блоці зворотних кроків повна кількість зчитувань з пам'яті зворотних кроків становитиме лише 56"63-233-3761, тобто середня економія на кадр - 14446 зчитувань. У системі 7/5 стандарту ІЗ-95 для каналу швидкості 2 з відносною кількістю помилок 195 послідовний декодер Вітербі без кешу може виконати 437 процедур зворотних кроків з І -95. Відзначимо, що останні 104, біти пакету одержуються однією процедурою. Повна кількість зчитувань з пам'яті зворотних кроків становить 437795-141515. Для 23 кадрів даних епсзіай(е після одного зчитування збігається з значенням бБезівіаїе попереднього циклу обробки у середньому приблизно 383 рази на кадр (з 457 процедур зворотних кроків). Отже, при використанні кешу у блоці Зворотних кроків повна кількість зчитувань з пам'яті зворотних кроків становитиме лише 997955338-9743, тобто середня економія на кадр - 31772 зчитувань. У інших системах результати можуть бути іншими.

Блок зворотних кроків (Фіг.4) може бути реалізований різними схемами, включаючи такі, що забезпечують подальше зниження споживання енергії або зменшення розмірів схеми. Дали описано деякі конкретні схеми.

Фіг.5А, 58 ілюструють більш досконале втілення блоку зворотних кроків, яке забезпечує додаткове зниження сч ов Кількості зчитувань з пам'яті зворотних кроків шляхом використання невеликої пам'яті об'ємом І-1 біт або регістру для зберігання біт рішення, зчитаних у кожному циклі обробки. Блок зворотних кроків включає пам'ять і) 204 зворотних кроків на І 41 біт, реверсивний лічильник 206 і зсувний регістр 208, які мають зв'язки з іншими регістрами і логічними елементами, як це показано на Фіг. Після Ї циклів обробки перша процедура зворотних кроків завершується. Найкращий режим бБезівзіаїе для попереднього циклу зберігається у зсувному регістрі 208, с зо Вихід якого позначено раніше як епосзіа(е. І. біт, зчитаних з пам'яті 202 зворотних кроків, зберігаються у

Ї -1-бітовій пам'яті 204 (один біт додано для спрощення схеми). Окремий регістр 210 використовується для ісе) стеження за попередніми значеннями бБезівіаіе, позначеними раніше як Іазі Бревзівіаіе. У наступному циклі нове со значення бБезівіаге фіксується у зсувному регістрі 208. Перше зчитування циклу обробки дає біт рішення, який зсувається у положення наймолодшого біту регістру 208. Цей біт, як і раніше, також зберігається у пам'яті о 204. Якщо епсзіаїе тепер збігається з Іазі резівіаіе, то біт, що відповідає найменшому/найстарішому циклу, ї- видаляється з пам'яті 204 і стає вихідним бітом. Цей біт є тим бітом, який був би одержаний в результаті повної процедури зворотних кроків з пам'яттю зворотних кроків; просто цей біт був одержаний коротшим і простішим шляхом. Якщо після одного зчитування епсзіа(е не збігається з Іавзі резівіа(їе, виконується повна процедура зворотних кроків з одночасним заповненням усіх І -1 біт пам'яті 204. У будь-якому випадку наприкінці « циклу обробки значення резівіа(е заноситься у Іазі резівіаіе і подальший цикл обробки виконується, як щойно в с описаний. Додання І 1-бітової пам'яті у блок зворотних кроків зменшує кількість процедур зчитування з пам'яті зворотних кроків і додатково знижує споживання енергії усією схемою декодера. з Втілення Фіг.5А, 5В може здаватись дещо складним, але порівняно з варіантом з блоком зворотних кроків з доступом до кешу у кожному циклі обробки блок зворотних кроків Фіг5А, 5В вимагає лише додання реверсивного лічильника 206, Ї -1-бітової пам'яті 204 (або іншого запам'ятовуючого регістру) і різних -І однобітових регістрів і комбінаторної логіки. Це дає ту перевагу, що у циклах обробки з одержанням збігу необхідно виконати лише одне (замість І) зчитування з пам'яті зворотних кроків і одне зчитування з 1 Ї -1-бітової пам'яті і запис, який є відносно незначним. У випадку незбігу необхідно виконати | зчитувань з

Го! пам'яті зворотних кроків і | записів у І ї1-бітову пам'ять. Ці записи не вимагають багато енергії, оскільки 5р розмір пам'яті незначний і частота незбігів звичайно є невеликою. При використання запам'ятовуючого регістру

Ме, споживання енергії є ще меншим. 4) Блок зворотних кроків Фіг.5А, 5В одержує ряд сигналів керування, які генеруються іншими схемами (не показанами). Далі наведено ці сигнали. гевеї - сигнал початкового встановлення логіки. резівіаїе - сигнал надходить від ДПО 138 (Фіг.4) і вказує на режим з найнижчою метрикою помилок для останнього циклу обробки. Цей сигнал змінюється до імпульсів зіагі спаіпраск і після імпульсів допе спаіпраск.

Ф) десівіоп Бії - генерується у ДПО. Це дані, що підлягають зберіганню у пам'яті зворотних кроків. ка віаг спаіпраск - імпульси на початку кожного циклу обробки, які вказують на можливість виконання процедури зворотних кроків. во допе спаіпраск - імпульси наприкінці кожного циклу обробки, які вказують на завершення процедури зворотних кроків. епаріє саспе геай - уможливлює використання І 1-бітової пам'яті або регістру для одержання вихідного біту. Імпульси епаріе саспе геай синхронізують 1 часовий цикл з першим імпульсом сбгеад у кожному циклі обробки. 65 сбгеад - у кожному циклі обробки надсилає І імпульсів для виконання | зчитувань з пам'яті зворотних кроків. Перший надсилається після віагі спаіпраск і останній - перед допе спаіпраск. Якщо має місце збіг,

виконується лише перше зчитування, а решта маскується схемою. срмутіге - імпульс надсилається кожного разу, коли біт рішення готовий для збереження у пам'яті зворотних кроків. спгат адаг - нормальна адреса, що ініціює пам'ять зворотних кроків. Для економії енергії ці лінії маскуються і утримуються у статичному стані у випадку, коли останні Ї - 1 зчитувань з пам'яті зворотних кроків не виконуються. до сотраге - внутрішній сигнал, що вказує на необхідність використання результату порівняння, тобто блок зворотних кроків порівнює поточне значення епсзіаїе з значенням бБевзівіаєе останнього циклу обробки, 70 збережене у Іазі Безівіагйе, і визначає наявність або, відсутність збігу. таїспй - внутрішній сигнал, що вказує на збіг значення епсзіаїе з значенням Іазі Бревівіаїе останнього циклу обробки. тівтаїсі - внутрішній сигнал, що вказує незбіг значення епсзіа(е з значенням Іавзі Брезівіа(е після першого зчитування з пам'яті зворотних кроків. сбгеад тихеа - внутрішній сигнал, подібний до сбгеад, але маскується у випадку збігу. геай Іаві бії - внутрішній сигнал для пересилання вихідного біту з | н1-бітової пам'яті у регістр. спгат доці - внутрішній сигнал, який є бітом, зчитаним з пам'яті зворотних кроків.

ФігбА, 6В ілюструють втілення, подібне до ілюстрованого Фіг.5А, 5В, де замість І 1-бітової пам'яті з реверсивним лічильником використано І-бітовий зсувний регістр. Зокрема, блок зворотних кроків Фіг.бА, 6В го Включає пам'ять 302 зворотних кроків, Ї-бітовий зсувний регістр ЗО5 і зсувний регістр 308, пов'язані з різними регістрами і елементами логіки. Після першого зчитування у циклі обробки зчитаний біт зсувається у зсувний регістр 308, виходом якого є епсзвіаїе. Якщо епсзіаїе тепер збігається з Іазі Бревзівіа(е, зчитаний біт зсувається на місце найстаршого біту І-бітового зсувного регістру, а наймолодший біт цього регістру стає вихідним бітом процедури зворотних кроків. Якщо епсвзіаїе не збігається з Іаві резівіа(їе, зчитаний біт сч ов Зсувається на місце наймолодшого біту І -бітового зсувного регістру, а інші І-1 зчитаних біт також зсуваються у наймолодший біт. (8)

Слід відзначити, що І -бітовий зсувний регістр має бути здатним зсувати у обох напрямках, тобто І -бітовий зсувний регістр Фіг.бА, 6В відрізняється від стандартного тим, що включає додатковий вхід "ліворуч", що визначає напрямок зсуву. Крім того, при кожному зчитуванні біту з пам'яті зворотних кроків усі | бітів с зо необхідно зсувати відразу, що збільшує споживання енергії порівняно з втіленням Фіг.5А. 5В. У іншому втіленні (не ілюстрованому) споживання енергії додатково знижується доданням декодуючої логіки для обрання кожного ісе) біту окремо з завантаженням окремо кожного біту зсувного регістру. Тоді при завантаженні | біт кожний з них со завантажується окремо. Отже, регістр має виконувати зсув лише при наявності збігу (одноразово у циклі обробки), що знижує витрати енергії. Ще одне втілення передбачає схему перевірки збігу після перших двох або о більше зчитувань у процесі виконання зворотних кроків, що збільшує імовірність збігу і додатково зменшує ї- споживання енергії і тривалість декодування. Таку схему можна використати у втіленнях Фіг.5А, 5В або Фіг.бА, 6В і у інших втіленнях.

У описаних вище втіленнях схема блоку зворотних кроків працює у кожному циклі обробки і виконує одне зчитування перед прийняттям рішення про використання (або відмову від нього) кешу для завершення « процедури зворотних кроків. Фіг.7 ілюструє втілення, у якому у кожному циклі обробки передбачено виконання то ств) с зчитувань перед прийняттям рішення про використання (або відмову від нього) кешу. Зокрема, на Фіг.1 зображено схему, призначену генерувати сигнал таїспй на підставі т зчитувань. Схема Фіг.7 може бути з використана у блоках зворотних кроків з кешем, ілюстрованих Фіг.5А, 5В або Фіг.бА, 6В, замість відповідної схеми формування сигналу таїсі, використаної у них. Схема таїсі Фіг.7 виконує у циклі обробки т зчитувань і

Порівнює поточне значення епсвіаїе з значенням є, одержаним після т-1 зчитувань, виконаних протягом -І попереднього циклу. У цьому втіленні імпульс сигналу епаріе саспе геад синхронізований з т-им зчитуванням.

Крім того, замість збереження значення Бевзівіаїе на початку кожної процедури зворотних кроків зберігається о значення епсзіаїе після т-1 зчитувань. Вибір т залежить від співвідношення між кількістю зчитувань (т) У

Го! кожному циклі і імовірністю збігу. Збільшення т знижує імовірність збігу після т зчитувань. Слід відзначити, 5р що схема Фіг.7 приймає додатковий сигнал заме зіаїе для фіксації епсвіаїе після т-1 зчитувань. Сигнал ме) до сотраге також відрізняється від описаного вище тим, що виникає після т зчитувань, а не одного, і 4) використовується для фіксації значення епсзіаіе, зафіксованого попереднім зчитуванням, що робить його доступним для порівняння у наступному циклі.

У іншому, більш узагальненому втіленні, замість перевірки значення епсзіа(їе після 1 або т зчитувань у дв Кожному циклі обробки епсзіа(е порівнюється після а і потім 5 зчитувань, тобто після а зчитувань зворотних кроків епсвіаЇїе порівнюється з значенням епсзіаіїе, збереженим у попередньому циклі після а-1 зчитувань, а

Ф) після наступного зчитування (ан1) епсзіаїе порівнюється з значенням епсзіа(їе, збереженим у попередньому ка циклі після а зчитувань і т. д., доки у цьому циклі обробки не буде виконано Б зчитувань.

У такому втіленні значення епсзіаїе для р-ан1 режимів зберігаються, бажано, у зсувному регістрі. Кожне бор наступне значення епсзіа(е є просто результатом лівого зсуву попереднього значення з новим наймолодшим бітом. Сигнал епаріе саспе геай повторюється для усіх зчитувань і припиняється після б зчитувань або після появи збігу. Вибір а і Б визначається співвідношенням таких факторів, як складність і збереження енергії.

Втілення Фіг.5А, 5Б і Фіг.бА, 6В відповідають значенням а-р0-1, тобто одному зчитуванню, після якого схема швидко вирішує, був збіг або ні. Описане вище втілення, у якому виконуються т зчитувань, відповідає випадку бе ат, р-т, коли порівняння здійснюється після т зчитувань.

Вибір значень а і Б для кожної системи визначається типом системи, статистикою конвергенцій (тобто типовою кількістю зчитувань, необхідних для конвергенції до шляху, зчитаного у попередньому циклі обробки), складністю обладнання і енергетичними вимогами. Для спрощення обладнання р-а має бути малим. Для зниження споживання енергії а має бути малим, а 5 залежати від статистики системи. Взагалі, збільшення р підвищує імовірність знаходження збігу.

У інших втіленнях процедури зворотних кроків здійснюються у багатьох циклах обробки. У описаних вище втіленнях було передбачене одноразове виконання зворотних кроків у кожному циклі. Однак, ці втілення можна модифікувати і виконувати процедуру у кількох циклах обробки. Наприклад, у втіленні, де процедура зворотних кроків виконується кожні 4 цикли обробки і результатом є 4 декодовані біти, сигнальний імпульс /о епаріе саспе геад можна генерувати лише при четвертому зчитуванні зворотних кроків. Однак, генерування епаріє саспе геад для кожного 4-го зчитування не є обов'язковим. Навіть коли процедура зворотних кроків виконується на 4 циклах обробки, визначення, коли порівнювати епсзіа(е, може залежати від значень а і 6.

Сигнал епаріє саспе геай може бути повторений 4 рази, якщо мав місце збіг і це дало 4 біти декодованої інформації, зчитаних з кешу. Інше втілення передбачає виконувати процедуру, використовуючи 4-бітові відрізки (або іншого розміру), і тоді при виконання процедури зворотних кроків при виявленні збігу система здійснює перевірку після 4 зчитувань. У цьому випадку система зчитує останні 4 біти кешу і видає їх, у іншому разі система продовжує виконання зворотних кроків і зберігає останні 4 зчитування з пам'яті зворотних кроків.

Описані вище втілення стосуються канальних інформаційних систем з обробкою пакетованої інформації, тобто блок даних кодується з згорткою з доданням хвостових біт, для переустановлення стану кодера між го пакетами. Отже, система чекає ІК циклів обробки, потім починає зворотні кроки і наприкінці виконує одну кінцеву процедуру зворотних кроків, формуючи І «К біт. Інші втілення винаходу передбачають використання у непакетованих інформаційних каналах зв'язку, наприклад, синхроканалах або пейджерних каналах згідно з І5-95.

Для таких каналів дані кадруються, але між кадрами стан кодера не переустановлюється. Отже, декодер виконує процедуру зворотних кроків у кожному циклі обробки. Зрозуміло, що принципи винаходу можуть бути застосовані с дв У майже будь-якому декодері Вітербі незалежно від типу каналів зв'язку системи.

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

Зо Типових втілень дозволяє будь-якому фахівцю використати винахід, виконавши, якщо необхідно, потрібні модифікації на підставі базових принципів винаходу. Отже, описані втілення не обмежують винаходу, концепції ісе) якого мають ширше поле застосування. со

ІС)

Claims

Формула винаходу і -

1. Послідовний декодер Вітербі, який має: приймач, призначений приймати кодований із згорткою потік символів; схему підсумовування-порівняння-вибору, призначену генерувати множину бітів рішення із кодованого із « 70 Згорткою потоку символів протягом кожного з множини циклів обробки, ш-в с модуль, який включає: пам'ять, призначену зберігати зазначену множину бітів рішення для кожного із зазначеної множини циклів :з» обробки, причому схема підсумовування-порівняння-вибору генерує протягом кожного нового циклу обробки біт рішення, що представляє показник оптимального стану, починаючи з поточного початкового показника оптимального стану, з подальшим виконанням наступної операції зворотної послідовності для -І множини бітів рішення, збережених у пам'яті зворотної послідовності, для кожного з множини циклів обробки, і кеш-пам'ять, що з'єднана з пам'яттю і використовується для зберігання послідовності бітів рішення, о доступних протягом попереднього циклу зворотної послідовності, і для виводу біта рішення, який був би о згенерований у іншому випадку, причому кеш-пам'ять крім того використовується для зберігання показника оптимального стану з (22) попереднього циклу обробки, для зберігання послідовності бітів рішення, доступних протягом попереднього «Фо» циклу обробки, і прийому показника оптимального стану для поточного циклу обробки, причому модуль додатково включає: контролер, призначений порівнювати зсунуту версію показника оптимального стану для поточного циклу обробки з показником оптимального стану попереднього циклу обробки і, якщо має місце збіг, виконувати вибірку самого раннього біта рішення з кеш-пам'яті. (Ф; 2.

Послідовний декодер Вітербі за п. 1, який відрізняється тим, що кеш-пам'ять виконує зчитування від а до ГІ Б протягом кожного циклу обробки, причому після а зчитувань кеш-пам'ять виконує перевірку при кожному подальшому зчитуванні, доки не будуть виконані 6 зчитувань або не буде досягнутий збіг. во З.

Послідовний декодер Вітербі за п. 2, який відрізняється тим, а - 5 - т, причому т - кількість зчитувань зворотної послідовності у кожному циклі обробки, до спроби використати кеш-пам'ять.

4. Послідовний декодер Вітербі за п. 2, який відрізняється тим, щоа - 5 - 1.

5. Послідовний декодер Вітербі, який має: приймач, призначений приймати кодований зі згорткою потік символів; 65 схему підсумовування-порівняння-вибору, призначену генерувати множину бітів рішення із кодованого зі згорткою потоку символів протягом кожного з множини циклів обробки,

модуль, який включає: пам'ять, призначену зберігати зазначену множину бітів рішення для кожного із зазначеної множини циклів обробки, причому схема підсумовування-порівняння-вибору генерує протягом кожного нового циклу обробки біт Вішення, що представляє показник оптимального стану, починаючи з поточного початкового показника оптимального стану, з подальшим виконанням наступної операції зворотної послідовності для множини бітів рішення, збережених у пам'яті зворотної послідовності, для кожного з множини циклів обробки, і кеш-пам'ять, що з'єднана з пам'яттю і використовується для зберігання послідовності бітів рішення, доступних протягом попереднього циклу зворотної послідовності, і для виводу біта рішення, який був би 7/о згенерований у іншому випадку, причому кеш-пам'ять має: регістр із зсувом вліво для прийому показника оптимального стану поточного циклу обробки, і (І -1)-бітову оперативну пам'ять з довільним доступом для зберігання послідовності бітів рішення, доступних протягом попередньої операції зворотної послідовності, де І. - довжина зворотної послідовності.

6. Послідовний декодер Вітербі за п. 5, який відрізняється тим, що регістр із зсувом вліво сконфігурований 7/5 Під регістр-засувку показника оптимального стану для попереднього циклу обробки.

7. Послідовний декодер Вітербі, який має: приймач, призначений приймати кодований із згорткою потік символів; схему підсумовування-порівняння-вибору, призначену генерувати множину бітів рішення із кодованого зі згорткою потоку символів протягом кожного з множини циклів обробки, модуль, який включає: пам'ять, призначену зберігати зазначену множину бітів рішення для кожного із зазначеної множини циклів обробки, причому схема підсумовування-порівняння-вибору генерує протягом кожного нового циклу обробки біт рішення, що представляє показник оптимального стану починаючи з поточного початкового показника оптимального стану з подальшим виконанням наступної операції зворотної послідовності для множини бітів сч ов рішення, збережених у пам'яті зворотної послідовності, для кожного з множини циклів обробки, і кеш-пам'ять, що з'єднана з пам'яттю і використовується для зберігання послідовності бітів рішення, (8) доступних протягом попереднього циклу зворотної послідовності, і для виводу біта рішення, який був би згенерований у іншому випадку, причому кеш-пам'ять має: регістр-засувку для зберігання показника оптимального стану з попереднього циклу обробки, со зо регістр із зсувом вліво для прийому показника оптимального стану поточного циклу обробки і для зсуву бітів рішення, со компаратор для порівняння показника оптимального стану попереднього циклу обробки із зсунутою версією со показника оптимального стану поточного циклу обробки і, якщо має місце збіг, виведення сигналу про збіг, і регістр із зсувом на І бітів для зберігання послідовності бітів рішення, доступних протягом попередньої о операції зворотної послідовності, де І. - довжина зворотної послідовності, ї- вихідну схему, з'єднану з регістром із зсувом на І! бітів і компаратором, для прийому сигналу про збіг від компаратора і керування регістром із зсувом на І бітів для виводу самого раннього біта рішення, збереженого у ній.

8. Послідовний декодер Вітербі, який має: « приймач, призначений приймати кодований із згорткою потік символів; в с схему підсумовування-порівняння-вибору, призначену генерувати множину бітів рішення із кодованого із згорткою потоку символів протягом кожного з множини циклів обробки, ;» модуль, який включає: пам'ять, призначену зберігати зазначену множину бітів рішення для кожного із зазначеної множини циклів обробки, причому схема підсумовування-порівняння-вибору генерує протягом кожного нового циклу обробки біт -І рішення, що представляє показник оптимального стану, починаючи з поточного початкового показника оптимального стану, з подальшим виконанням наступної операції зворотної послідовності для множини бітів о рішення, збережених у засобі пам'яті зворотної послідовності, для кожного з множини циклів обробки, і Го! кеш-пам'ять, що з'єднана з пам'яттю і використовується для зберігання послідовності бітів рішення, 5р доступних протягом попереднього циклу зворотної послідовності, і для виводу біта рішення, який у іншому Ме, випадку був би згенерований, сю причому кеш-пам'ять має: регістр із зсувом вліво для зсуву показника оптимального стану поточного циклу обробки, множину послідовних регістрів для збереження раніше зсунутих версій показника оптимального стану, компаратор для порівняння вихідних даних регістру із зсувом вліво з вихідними даними одного з останніх з множини послідовних регістрів і, якщо має місце збіг, виведення сигналу про збіг, Ф) (І -1)-бітову оперативну пам'ять з довільним доступом для зберігання послідовності бітів рішення, ка доступних протягом попередньої операції зворотної послідовності, де ! - довжина зворотної послідовності, і вихідну схему, з'єднану з (І 41)-бітовою оперативною пам'яттю з довільним доступом і з компаратором для во прийому від компаратора сигналу про збіг і для керування (І -1)-бітовою оперативною пам'яттю з довільним доступом для виведення самого раннього біта рішення, збереженого у ній.

9. Спосіб виконання послідовного декодування Вітербі, який включає операції: прийому потоку кодованих зі згорткою символів, генерування множини бітів рішення з потоку кодованих із згорткою потоку символів протягом кожного з б5 Множини циклів обробки, збереження зазначеної множини бітів рішення у пам'яті для кожного з зазначеної множини циклів обробки,

визначення протягом кожного нового циклу обробки біта рішення, що представляє показник оптимального стану, починаючи з поточного початкового показника оптимального стану, з подальшим виконанням наступної операції зворотної послідовності для множини бітів рішення, збережених у пам'яті для кожного з множини циклів обробки, і збереження послідовності бітів рішення, доступних протягом попередньої операції зворотної послідовності в кеш-пам'яті, і виведення біта рішення, який у іншому випадку був би згенерований наступною операцією зворотної послідовності, якщо зсунута версія показника оптимального стану для нового циклу обробки збігається з показником оптимального стану останнього циклу обробки. 70 10. Спосіб за п. 9, який відрізняється тим, що операція збереження послідовності бітів рішення, доступних протягом попередньої операції зворотної послідовності у кеш-пам'яті, і виведення біта рішення, що представляє показник оптимального стану, якщо поточний показник оптимального стану для нового циклу обробки вказує на початковий показник останнього циклу обробки, включає операції: зберігання показника оптимального стану з попереднього циклу обробки, зберігання послідовності бітів рішення, доступних протягом попередньої операції зворотної послідовності, зсуву показника оптимального стану для поточного циклу обробки, і порівняння показника оптимального стану попереднього циклу обробки із зсунутим показником оптимального стану поточного циклу обробки і, якщо має місце збіг, виведення самого раннього біта рішення, збереженого протягом попередньої операції зворотної послідовності.

11. Спосіб за п. 10, який відрізняється тим, що операція збереження послідовності бітів рішення, доступних протягом попередньої операції зворотної послідовності в кеш-пам'яті, і виведення біта рішення, що представляє показник оптимального стану, якщо поточний показник оптимального стану для нового циклу обробки вказує на початковий показник контрольованого останнього циклу обробки, керує виконанням зчитувань від а до Б протягом кожного циклу обробки, причому після а зчитувань засіб кеш-пам'яті виконує перевірку при кожному с подальшому зчитуванні, доки не будуть виконані 5 зчитувань або не буде досягнутий збіг.

12. Спосіб за п. 11, який відрізняється тим, що а-р-т. (8)

13. Спосіб за п. 11, який відрізняється тим, що а-р-1. (зе) (Се) (ее) ІФ) і -

- . и? -і 1 (ее) (о) сю» іме) 60 б5