Кіріспе

Витерби алгоритмімен бит ағынын декодтайды. Витерби декодері конволюциялық код немесе торлы код қолданылып кодталған бит ағынын декодтау үшін Витерби алгоритмін пайдаланады. Конволюциялық кодталған ағынды декодтау үшін басқа алгоритмдер де бар (мысалы, Фано алгоритмі). Витерби алгоритмі ең көп ресурстарды қажет етеді, бірақ максималды ықтималдықпен декодтауды жүзеге асырады. Ол көбінесе k≤3 шектеу ұзындығы бар конволюциялық кодтарды декодтау үшін қолданылады, бірақ практикада k=15-ке дейінгі мәндер де қолданылады. Витерби декоды Эндрю Ж. Витерби жасаған және жариялаған. Витерби декоды итеративті Витерби декоды алгоритмінде қолданылады.

Жолдың метрикалық бірлігі (PMU)

Жолдық метрикалық бірлік тармақтық метрикаларды жинақтап, жолдар үшін метрикаларды есептейді, мұнда K – кодтың шектеу ұзындығы, олардың бірі соңында оңтайлы деп таңдалуы мүмкін. Ол әр такта сайын шешімдер қабылдап, уәжделі түрде нашар жолдарды жоққа шығарады. Осы шешімдердің нәтижелері іздеу блогының жадына жазылады. ЖМБ-ның (Жолдық метрикалық бірлік) негізгі элементтері ACS (Қосу-Салыстыру-Таңдау) бірліктері болып табылады. Олардың бір-бірімен байланысу әдісі нақты кодтың тор диаграммасымен анықталады. Метрикалық санағыштардың толып кетуіне жол бермес үшін қосымша тізбек (суретте көрсетілмеген) болуы керек. Жолдық метриканың өсуін қадағалау қажеттілігін жоятын баламалы әдіс – жолдық метрикаға «айналуға» рұқсат беру; бұл әдісті қолдану үшін жолдық метриканың аккумуляторларында «жақсы» және «нашар» мәндердің арасындағы айырма 2(n+1)-ден кем болмайтынын қамтамасыз ету қажет. Салыстыру тізбегі негізінен өзгеріссіз қалады. Келіп түсетін биттік ағындағы шу деңгейін «жақсы» жолдық метриканың өсу қарқынын қадағалау арқылы бақылауға болады. Мұны істеудің қарапайым жолы – бір орналасқан жерді немесе «күйді» бақылау және оның аккумулятор диапазонындағы төрт дискретті деңгей арқылы «жоғары қарай» өтуін қадағалау. Ол осы шектік мәндердің әрқайсысы арқылы жоғары қарай өскен сайын, кіріс сигналдағы «шуды» көрсететін санағыш артады.

Трейсбек бірлігі (TBU)

Арқалық іздену модулі PMU шешімдерінен (шамамен) ең жоғары ықтималдық жолын қалпына келтіреді. Ол кері бағытта жасалатындықтан, Витерби декодері дұрыс ретті қайта құру үшін FILO (бірінші кірген, соңғы шыққан) буферін қамтиды. Суретте көрсетілген жүзеге асыру қос жиілікті талап ететінін ескеріңіз. Бұл талапты жоятын әдістер де бар.

Жұмсақ шешімдерді кодтау үшін кванттау

Жұмсақ шешімді декодтаудың барлық артықшылықтарын толыққанды пайдалану үшін кіріс сигналын тиісті түрде кванттау қажет. Оңтайлы кванттау аймағының ені келесі формуламен анықталады:

мұндағы – шудың қуат спектрлік тығыздығы, ал k – жұмсақ шешім үшін біттер саны.

Қайта іздеу

Трейсбекке қатысты жалпы тәсіл – шектеу ұзындығының бес есесіне дейін (5(K–1)) жол метрикаларын жинақтау, ең үлкен жинақталған құны бар түйінді табу және осы түйінден ізденуді бастау. Конволюциялық кодтың жадының бес еселенгенінен (кедергі ұзындығы K–1) қысқарту тереңдігінің жиі қолданылатын қағидасы тек 1/2 жылдамдықтағы кодтар үшін ғана дұрыс. Кез келген мөлшерлеме үшін, дұрыс қағида – 2.5(K–1)/(1–r), мұндағы r – код мөлшерлемесі. Дегенмен, ең үлкен құнын жинақтаған түйінді есептеу (ең үлкен немесе ең кіші интегралды жол метрикасы) бірнеше (әдетте 2K–1) сандардың максимумдарын немесе минимумдарын табуды қамтиды, бұл кіріктірілген аппараттық жүйелерде орындалғанда көп уақытты алуы мүмкін. Көптеген байланыс жүйелері Viterbi декодилеуін қолданады, ол дерек пакеттерінің белгілі бір мөлшерімен, бастапқыда немесе соңында белгілі бір бит/байт үлгісімен бірге жүзеге асырылады. Белгілі бит/байт үлгісін анықтама ретінде пайдалану арқылы бастапқы түйін белгілі бір мәнге орнатылып, осылайша трейсбек кезінде толыққанды ең жоғары ықтималдық жолына қол жеткізіледі.

Шектеулер

Витерби декодерінің физикалық іске асырылуы кіріс сигналының, тармақ және жол метрикаларының квантталуы мен шектеулі кері іздеу ұзындығы салдарынан нақты ең жоғары ықтималдық ағынын қамтамасыз етпейді. Іс жүзіндегі жүзеге асырулар идеалға 1 дБ-ға жуықтап келеді. Аддитивті Гаусс арнасымен зақымдалған хабарламаны декодтағанда Витерби декодерінің шығысында қателер қателік шоғырлары түрінде жинақталады. Жеке қателерді түзету кодтары мұндай шоғырларды түзетуге жете алмайды, сондықтан конволюциялық код пен Витерби декодері қателерді қанағаттанарлық деңгейге дейін төмендету үшін жеткілікті күшті болуы керек, немесе қателік шоғырларын түзету кодтары қолданылуы тиіс.

Бағдарламалық жасақтаманы іске асыру

Ең көп уақытты талап ететін операциялардың бірі – ACS бабочкасы, ол әдетте декодтау уақытын үдету үшін ассемблер тілі және тиісті нұсқаулар жиынтығының кеңейтімдерін (мысалы, SSE2) пайдаланып іске асырылады.