Viterbi decoder
વિટરબી ડીકોડર બિટસ્ટ્રીમને ડીકોડ કરવા માટે વિટરબી અલ્ગોરિધમનો ઉપયોગ કરે છે જે કન્વોલ્યુશનલ કોડ અથવા ટ્રેલિસ કોડનો ઉપયોગ કરીને એન્કોડ કરવામાં આવ્યો છે. કોન્વોલ્યુશનલી એન્કોડેડ સ્ટ્રીમને ડીકોડ કરવા માટે અન્ય અલ્ગોરિધમ્સ છે (ઉદાહરણ તરીકે, ફેનો અલ્ગોરિધમ). વિટરબી અલ્ગોરિધમ સૌથી વધુ સંસાધન-વપરાશ કરનાર છે, પરંતુ તે મહત્તમ સંભાવના ડીકોડિંગ કરે છે. તેનો ઉપયોગ મોટાભાગે અવરોધ લંબાઈ k ≤ 3 સાથે કન્વોલ્યુશનલ કોડને ડીકોડિંગ કરવા માટે થાય છે, પરંતુ વ્યવહારમાં k = 15 સુધીના મૂલ્યોનો ઉપયોગ થાય છે. વિટરબી ડીકોડિંગ એન્ડ્રુ જે. વિટરબી દ્વારા વિકસાવવામાં આવ્યું હતું અને પેપરમાં પ્રકાશિત કરવામાં આવ્યું હતું વિટરબી ડીકોડરના હાર્ડવેર (મોડેમમાં) અને સોફ્ટવેર અમલીકરણ બંને છે. વિટરબી ડીકોડિંગનો ઉપયોગ પુનરાવર્તિત વિટરબી ડીકોડિંગ અલ્ગોરિધમમાં થાય છે. હાર્ડવેર અમલીકરણ મૂળભૂત (પંચર વગરના) કોડ માટે હાર્ડવેર વિટરબી ડીકોડરમાં સામાન્ય રીતે નીચેના મુખ્ય બ્લોકનો સમાવેશ થાય છેઃ શાખા મેટ્રિક એકમ (બીએમયુ) પાથ મેટ્રિક એકમ (પીએમયુ) ટ્રેસબેક એકમ (ટીબીયુ) શાખા મેટ્રિક એકમ (બીએમયુ) શાખા મેટ્રિક એકમનું કાર્ય શાખા મેટ્રિક્સની ગણતરી કરવાનું છે, જે કોડ મૂળાક્ષરમાં દરેક સંભવિત પ્રતીક અને પ્રાપ્ત પ્રતીક વચ્ચેનું પ્રમાણભૂત અંતર છે. ત્યાં સખત નિર્ણય અને નરમ નિર્ણય વિટરબી ડીકોડર્સ છે. હાર્ડ ડિસિઝન વિટરબી ડીકોડર તેના ઇનપુટ પર એક સરળ બિટસ્ટ્રીમ મેળવે છે, અને હેમિંગ અંતરનો ઉપયોગ મેટ્રિક તરીકે થાય છે. સોફ્ટ ડિસિઝન વિટરબી ડીકોડર બિટસ્ટ્રીમ મેળવે છે જેમાં દરેક પ્રાપ્ત પ્રતીકની વિશ્વસનીયતા વિશેની માહિતી હોય છે. દાખલા તરીકે, 3-બીટ એન્કોડિંગમાં, આ વિશ્વસનીયતા માહિતીને નીચે પ્રમાણે એન્કોડ કરી શકાય છેઃ અલબત્ત, વિશ્વસનીયતા ડેટાને એન્કોડ કરવાનો આ એકમાત્ર રસ્તો નથી. સ્ક્વેર્ડ યુક્લિડિયન અંતરનો ઉપયોગ સોફ્ટ ડિસિઝન ડીકોડર્સ માટે મેટ્રિક તરીકે થાય છે. પાથ મેટ્રિક એકમ (PMU) પાથ મેટ્રિક એકમ પાથ માટે મેટ્રિક્સ મેળવવા માટે શાખા મેટ્રિક્સનો સારાંશ આપે છે, જ્યાં K એ કોડની અવરોધ લંબાઈ છે, જેમાંથી એકને આખરે શ્રેષ્ઠ તરીકે પસંદ કરી શકાય છે. દરેક ઘડિયાળ તે નિર્ણયો લે છે, જાણીજોઈને બિન-શ્રેષ્ઠ માર્ગોને ફેંકી દે છે. આ નિર્ણયોના પરિણામો ટ્રેસબેક એકમની સ્મૃતિમાં લખવામાં આવે છે. પીએમયુના મુખ્ય ઘટકો એસીએસ (ઉમેરો-સરખામણી કરો-પસંદ કરો) એકમો છે. તેઓ પોતાની વચ્ચે જે રીતે જોડાયેલા છે તે ચોક્કસ કોડના ટ્રેલિસ આકૃતિ દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે. શાખા મેટ્રિક્સ હંમેશાં હોવાથી, મેટ્રિક કાઉન્ટર્સને ઓવરફ્લોથી અટકાવતી વધારાની સર્કિટ (છબી પર બતાવેલ નથી) હોવી આવશ્યક છે. પાથ મેટ્રિક વૃદ્ધિ પર દેખરેખ રાખવાની જરૂરિયાતને દૂર કરતી વૈકલ્પિક પદ્ધતિ એ છે કે પાથ મેટ્રિક્સને "રોલ ઓવર" કરવાની મંજૂરી આપવી; આ પદ્ધતિનો ઉપયોગ કરવા માટે ખાતરી કરવી જરૂરી છે કે પાથ મેટ્રિક સંચયકોમાં "શ્રેષ્ઠ" અને "સૌથી ખરાબ" મૂલ્યોને એકબીજાના 2 (એન-1) ની અંદર આવતા અટકાવવા માટે પૂરતા બિટ્સ હોય. સરખામણી સર્કિટ અનિવાર્યપણે અપરિવર્તિત છે. "શ્રેષ્ઠ" પાથ મેટ્રિકની વૃદ્ધિ દરનું નિરીક્ષણ કરીને આવતા બીટ સ્ટ્રીમ પર અવાજના સ્તરનું નિરીક્ષણ કરવું શક્ય છે. આવું કરવાની એક સરળ રીત એ છે કે એક સ્થાન અથવા "રાજ્ય" નું નિરીક્ષણ કરવું અને તેને સંચયકર્તાની શ્રેણીમાં ચાર અલગ સ્તરોમાંથી "ઉપરની તરફ" પસાર થતું જોવું. જેમ જેમ તે આ દરેક થ્રેશોલ્ડમાંથી ઉપર તરફ પસાર થાય છે, તેમ તેમ એક કાઉન્ટર વધારવામાં આવે છે જે આવતા સિગ્નલ પર હાજર "ઘોંઘાટ" ને પ્રતિબિંબિત કરે છે. ટ્રેસબેક યુનિટ (ટીબીયુ) બેક-ટ્રેસ યુનિટ પીએમયુ દ્વારા લેવામાં આવેલા નિર્ણયોમાંથી (લગભગ) મહત્તમ-આજીવિકા માર્ગને પુનઃસ્થાપિત કરે છે. તે તેને વિપરીત દિશામાં કરે છે, તેથી વિટરબી ડીકોડરમાં સાચા ક્રમનું પુનઃનિર્માણ કરવા માટે FILO (ફર્સ્ટ-ઇન-લાસ્ટ-આઉટ) બફરનો સમાવેશ થાય છે. નોંધ લો કે છબી પર દર્શાવેલ અમલીકરણ માટે બમણી આવર્તનની જરૂર છે. કેટલીક યુક્તિઓ છે જે આ જરૂરિયાતને દૂર કરે છે. અમલીકરણના મુદ્દાઓ સોફ્ટ ડિસિઝન ડીકોડિંગ માટે ક્વોન્ટાઇઝેશન સોફ્ટ ડિસિઝન ડીકોડિંગના લાભોનો સંપૂર્ણ ઉપયોગ કરવા માટે, ઇનપુટ સિગ્નલને યોગ્ય રીતે માપવાની જરૂર છે. શ્રેષ્ઠ ક્વોન્ટાઇઝેશન ઝોનની પહોળાઈને નીચેના સૂત્ર દ્વારા વ્યાખ્યાયિત કરવામાં આવે છેઃ જ્યાં ઘોંઘાટ શક્તિ વર્ણપટ ઘનતા છે, અને k એ નરમ નિર્ણય માટે સંખ્યાબંધ બિટ્સ છે. યુક્લિડિયન મેટ્રિક ગણતરી કોડ મૂળાક્ષરમાં પ્રાપ્ત થયેલા અને વાસ્તવિક પ્રતીકો વચ્ચેના વર્ગ ધોરણ () અંતરને રેખીય સરવાળો/તફાવત સ્વરૂપમાં વધુ સરળ બનાવી શકાય છે, જે તેને ઓછી ગણતરીત્મક રીતે સઘન બનાવે છે. 1/2 કન્વોલ્યુશનલ કોડનો વિચાર કરો, જે દરેક ઇનપુટ બીટ (1 અથવા 0) માટે 2 બિટ્સ (00,01,10 અથવા 11) જનરેટ કરે છે. આ રીટર્ન-ટુ-ઝીરો સંકેતો સાથે દર્શાવેલ નોન-રીટર્ન-ટુ-ઝીરો સ્વરૂપમાં અનુવાદિત થાય છે. દરેક પ્રાપ્ત પ્રતીકને વેક્ટર સ્વરૂપમાં vr = {r0, r1} તરીકે રજૂ કરી શકાય છે, જ્યાં r0 અને r1 નરમ નિર્ણય મૂલ્યો છે, જેનું પરિમાણ પ્રાપ્ત વેક્ટરની સંયુક્ત વિશ્વસનીયતાને સૂચવે છે, vr. કોડ મૂળાક્ષરમાં દરેક પ્રતીક, તેવી જ રીતે, વેક્ટર vi = {±1, ±1} દ્વારા રજૂ થઈ શકે છે. યુક્લિડિયન અંતર મેટ્રિકની વાસ્તવિક ગણતરી આ પ્રમાણે છેઃ દરેક ચોરસ પદ એક પ્રમાણભૂત અંતર છે, જે પ્રતીકની ઊર્જાને દર્શાવે છે. ઉદાહરણ તરીકે, પ્રતીક vi = {±1, ±1} ની ઊર્જાની ગણતરી આ રીતે કરી શકાય છે. એડ-કમ્પેર-સિલેક્ટ (ACS) ઓપરેશન પ્રાપ્ત થયેલ પ્રતીક | |vr | | અને કોડ મૂળાક્ષરમાંના કોઈપણ 2 પ્રતીકો વચ્ચેના મેટ્રિક અંતરની સરખામણી કરે છે, જેમના પાથ અનુરૂપ ટ્રેલિસમાં નોડ પર મર્જ થાય છે, | |vi (0) | અને | |vi (1) |. પરંતુ, ઉપરથી આપણે જાણીએ છીએ કે vi ની ઊર્જા અચળ (2 ના (સામાન્યીકૃત) મૂલ્યની બરાબર) છે, અને બંને કિસ્સાઓમાં vr ની ઊર્જા સમાન છે. આ 2 (મધ્યમ) ડોટ પ્રોડક્ટ શરતો વચ્ચેના મિનિમા ફંક્શનની સરખામણીને ઘટાડે છે, કારણ કે નકારાત્મક સંખ્યાઓ પરની કામગીરીને હકારાત્મક જથ્થા પર સમકક્ષ કામગીરી તરીકે અર્થઘટન કરી શકાય છે. દરેક ડોટ પ્રોડક્ટ ટર્મને વિસ્તૃત કરી શકાય છે, જ્યાં દરેક ટર્મના ચિહ્નો પ્રતીકો, vi (0) અને vi (1) પર આધારિત છે, જેની સરખામણી કરવામાં આવી રહી છે. આમ, શાખા મેટ્રિકની ગણતરી કરવા માટે વર્ગ યુક્લિડિયન મેટ્રિક અંતરની ગણતરી સરળ ઉમેરો/બાદબાકી કામગીરી સાથે કરી શકાય છે. ટ્રેસબેકનો સામાન્ય અભિગમ અવરોધ લંબાઈ (5 (કે-1)) ના પાંચ ગણા સુધી પાથ મેટ્રિક્સ એકઠા કરવાનો છે, સૌથી વધુ સંચિત કિંમત સાથે નોડ શોધો અને આ નોડમાંથી ટ્રેસબેક શરૂ કરો. કોન્વોલ્યુશનલ કોડની મેમરી (અવરોધ લંબાઈ K-1) ની પાંચ ગણી કાપણીની ઊંડાઈનો સામાન્ય રીતે ઉપયોગમાં લેવાતો અંગૂઠાનો નિયમ માત્ર અડધા દરના કોડ માટે સચોટ છે. મનસ્વી દર માટે, અંગૂઠાનો સચોટ નિયમ 2.5 (K-1)/(1-r) છે જ્યાં r એ કોડ દર છે. જો કે, નોડની ગણતરી કે જેણે સૌથી મોટો ખર્ચ (સૌથી મોટો અથવા સૌથી નાનો અભિન્ન પાથ મેટ્રિક) એકત્રિત કર્યો છે તેમાં કેટલાક (સામાન્ય રીતે 2K-1) નંબરોની મહત્તમ અથવા લઘુત્તમ શોધનો સમાવેશ થાય છે, જે એમ્બેડેડ હાર્ડવેર સિસ્ટમ્સ પર અમલમાં મૂકવામાં આવે ત્યારે સમય લાગી શકે છે. મોટાભાગની સંચાર પ્રણાલીઓ નિશ્ચિત કદના ડેટા પેકેટોને સમાવતી વિટરબી ડીકોડિંગનો ઉપયોગ કરે છે, જેમાં ડેટા પેકેટની શરૂઆતમાં અથવા/અને અંતે નિશ્ચિત બીટ/બાઈટ પેટર્ન હોય છે. સંદર્ભ તરીકે જાણીતા બીટ/બાઈટ પેટર્નનો ઉપયોગ કરીને, સ્ટાર્ટ નોડને નિશ્ચિત મૂલ્ય પર સેટ કરી શકાય છે, જેનાથી ટ્રેસબેક દરમિયાન સંપૂર્ણ મહત્તમ શક્યતા પાથ પ્રાપ્ત થાય છે. મર્યાદાઓ ઇનપુટ સિગ્નલ, શાખા અને પાથ મેટ્રિક્સ અને મર્યાદિત ટ્રેસબેક લંબાઈના જથ્થાને કારણે વિટરબી ડીકોડરનું ભૌતિક અમલીકરણ ચોક્કસ મહત્તમ-આજીવિકા પ્રવાહ પ્રાપ્ત કરશે નહીં. વ્યવહારુ અમલીકરણ આદર્શના 1 ડી. બી. ની અંદર પહોંચે છે. વિટેરબી ડીકોડરનું આઉટપુટ, જ્યારે એડિટિવ ગૌસીયન ચેનલ દ્વારા ક્ષતિગ્રસ્ત સંદેશને ડીકોડ કરે છે, ત્યારે ભૂલોને ભૂલ વિસ્ફોટોમાં જૂથબદ્ધ કરવામાં આવે છે. એકલા સિંગલ-એરર-કરેક્ટિંગ કોડ્સ આવા વિસ્ફોટોને સુધારી શકતા નથી, તેથી કાં તો કન્વોલ્યુશનલ કોડ અને વિટરબી ડીકોડરને એટલી શક્તિશાળી ડિઝાઇન હોવી જોઈએ કે ભૂલોને સ્વીકાર્ય દરે ઘટાડી શકાય, અથવા બર્સ્ટ એરર-કરેક્ટિંગ કોડનો ઉપયોગ કરવો આવશ્યક છે. પંક્ચર્ડ કોડ્સ પંક્ચર્ડ કોડ્સના હાર્ડવેર વિટરબી ડીકોડરને સામાન્ય રીતે એવી રીતે લાગુ કરવામાં આવે છેઃ એક ડેપંક્ચરર, જે ઇનપુટ સ્ટ્રીમને સ્ટ્રીમમાં પરિવર્તિત કરે છે, જે જ્યાં બિટ્સ ભૂંસી નાખવામાં આવ્યા હતા ત્યાં ERASE ગુણ સાથે મૂળ (બિન પંક્ચર્ડ) સ્ટ્રીમ જેવો દેખાય છે. આ ERASE ગુણને સમજતું મૂળભૂત વિટરબી ડીકોડર (એટલે કે, તેનો ઉપયોગ શાખા મેટ્રિક ગણતરી માટે થતો નથી). સોફ્ટવેર અમલીકરણ સૌથી વધુ સમય લેતી કામગીરીઓમાંની એક એ. સી. એસ. બટરફ્લાય છે, જે સામાન્ય રીતે ડીકોડિંગ સમયને ઝડપી બનાવવા માટે એસેમ્બલી લેંગ્વેજ અને યોગ્ય સૂચના સેટ એક્સ્ટેન્શન્સ (જેમ કે SSE2) નો ઉપયોગ કરીને અમલમાં મૂકવામાં આવે છે. કાર્યક્રમો વિટેરબી ડીકોડિંગ અલ્ગોરિધમનો વ્યાપકપણે નીચેના ક્ષેત્રોમાં ઉપયોગ થાય છેઃ રેડિયો સંચારઃ ડિજિટલ ટીવી (એટીએસસી, ક્યુએએમ, ડીવીબી-ટી, વગેરે. ), રેડિયો રિલે, ઉપગ્રહ સંચાર, કલાપ્રેમી રેડિયો માટે પી. એસ. કે. 31 ડિજિટલ મોડ. ડીકોડિંગ ટ્રેલિસ-કોડેડ મોડ્યુલેશન (ટી. સી. એમ.), 3 કિલોહર્ટ્ઝ-બેન્ડવિડ્થ એનાલોગ ટેલિફોન લાઇનમાંથી ઉચ્ચ વર્ણપટ કાર્યક્ષમતાને દબાવવા માટે ટેલિફોન-લાઇન મોડેમમાં ઉપયોગમાં લેવાતી તકનીક છે. હાર્ડ ડિસ્ક ડ્રાઇવ જેવા કમ્પ્યુટર સંગ્રહ ઉપકરણો. સ્વયંચાલિત વાણી ઓળખ સંદર્ભો બાહ્ય કડીઓ વિટેરબી ડીકોડિંગ પર વિગતો, તેમજ ગ્રંથસૂચિ. હાર્ડવેર અમલીકરણ મુદ્દાઓ પર ધ્યાન કેન્દ્રિત કરીને વિટરબી અલ્ગોરિધમનો સમજૂતી. આર = 1/6 કે = શનિના કેસિની મિશન માટે 15 કોડિંગ. ઓપ્ટિમાઇઝ્ડ સોફ્ટવેર વિટરબી ડીકોડર્સ (જી. પી. એલ.) નું ઓનલાઇન જનરેટર. ચાર પ્રમાણભૂત કોડ માટે જી. પી. એલ. વિટરબી ડીકોડર સોફ્ટવેર. કે = 24 વિટરબી ડીકોડરનું વર્ણન, જે વ્યવહારુ ઉપયોગમાં અત્યાર સુધીનું સૌથી મોટું માનવામાં આવે છે. જેનરિક વિટરબી ડીકોડર હાર્ડવેર (જી. પી. એલ.). ડેટા ટ્રાન્સમિશન ભૂલ શોધ અને સુધારણા ઉચ્ચ-મહત્વપૂર્ણ લેખો