維特比演算法代碼

⑴ Viterbi解碼的解碼演算法

viterbi解碼演算法是一種卷積碼的解碼演算法。優點不說了。缺點就是隨著約束長度的增加演算法的復雜度增加很快。約束長度N為7時要比較的路徑就有64條，為8時路徑變為128條。 (2<<(N-1))。所以viterbi解碼一般應用在約束長度小於10的場合中。
先說編碼（舉例約束長度為7）：編碼器7個延遲器的狀態（0，1）組成了整個編碼器的64個狀態。每個狀態在編碼器輸入0或1時，會跳轉到另一個之中。比如110100輸入1時，變成101001（其實就是移位寄存器）。並且輸出也是隨之而改變的。
這樣解碼的過程就是逆過程。演算法規定t時刻收到的數據都要進行64次比較，就是64個狀態每條路有兩條分支（因為輸入0或1），同時，跳傳到不同的兩個狀態中去，將兩條相應的輸出和實際接收到的輸出比較，量度值大的拋棄（也就是比較結果相差大的），留下來的就叫做倖存路徑，將倖存路徑加上上一時刻倖存路徑的量度然後保存，這樣64條倖存路徑就增加了一步。在解碼結束的時候，從64條倖存路徑中選出一條量度最小的，反推出這條倖存路徑（叫做回溯），得出相應的解碼輸出。

⑵ 維特比解碼

糾錯編碼與調制是各自獨立設計DMT和卷積編碼結合後的編碼增益比傳統編碼的編碼在這里維特比解碼演算法的核心是回退的觀點，採用動態規劃法存儲數據，如果對

⑶ 什麼是Viterbi演算法怎麼理解Viterbi演算法

http://www.pudn.com/detail77170.html

⑷ 如何用R實現Viterbi演算法

Viterbi解碼演算法是由Viterbi於1967年提出的一種最大似然解碼辦法，解碼器根據接收序列R按最大似然准則力圖找出正確的原始碼序列。隨著大規模集成電路技術的發展，採用Viterbi演算法的卷積編碼技術已成為廣泛應用的糾錯方案。Viterbi解碼過程可用狀態表示。Sj，t和Sj N/2，t表示t時刻的兩個狀態。在t1時刻，這兩個狀態值根據路徑為0或者1，轉移到狀態S2j，t1和S2j1，t1。每一種可能的狀態轉移都根據接收到的有雜訊的序列R計算路徑度量，然後選擇出各個狀態的最小度量路徑(倖存路徑)。Viterbi演算法就是通過在狀態中尋找最小量路徑向前回溯L步，最後得到的即為解碼輸出。
在卷積碼(n，k，m)表示法中，參數k表示每次輸入信息碼位數，n表示編碼的輸出卷積碼位數，m稱為約束長度(一些書中採用k=m1為約束長度，也可稱(2，1，2)碼網格圖，r=k/n稱為信息率，即編碼效率。本文運用的是(2，1，3)碼，約速長度為2，狀態數為22=－4。
TMS320C6000系列DSPs(數字信號處理器)是TI公司推出的一種並行處理的數字信號處理器，是基於TI的VLIW技術的。本文採用的是TMS320C6211。該處理器的工作頻率經過倍頻可達到150MHz，每個時鍾周期最多可並行執行8條指令，從而可以實現1200MIPS定點運算能力。

⑸ Python實現viterbi演算法原理流程是什麼樣的

維特比演算法說白了就是動態規劃實現最短路徑，只要知道「動態規劃可以降低復雜度」這一點就能輕松理解維特比演算法
維特比演算法是一個特殊但應用最廣的動態規劃演算法，利用動態規劃，可以解決任何一個圖中的最短路徑問題。而維特比演算法是針對一個特殊的圖——籬笆網路的有向圖（Lattice )的最短路徑問題而提出的。 它之所以重要，是因為凡是使用隱含馬爾可夫模型(Hidden Markov Model，HMM)描述的問題都可以用它來解碼，包括今天的數字通信、語音識別、機器翻譯、拼音轉漢字、分詞等。——《數學之美》 ps 多處摘錄此書，不再贅述。
籬笆網路有向圖的特點是同一列節點有多個，並且和上一列節點交錯地連接起來。同一列節點代表同一個時間點上不同的狀態的並列，大概因為這種一列一列整齊的節點和交錯的邊很像籬笆而得名。

假設上圖每一列分別有n1……nn個節點，如果不使用動態的話，那麼計算復雜度就是O(n1*n2……nn)。
而維特比演算法的精髓就是，既然知道到第i列所有節點Xi{j=123…}的最短路徑，那麼到第i+1列節點的最短路徑就等於到第i列j個節點的最短路徑+第i列j個節點到第i+1列各個節點的距離的最小值。
這是一句大白話，所謂中文偽碼。
分析一下復雜度，假設整個籬笆有向圖中每一列節點最多有D個（也就是圖的寬度為D），並且圖一共有N列，那麼，每次計算至多計算D*D次（從i列的D個節點中挑一個計算到i+1列D個節點的距離）。至多計算N次。那麼復雜度驟減為O（ND2），遠遠小於窮舉O（DN）。

⑹ 維特比解碼演算法n*n=18時有幾條路徑

給定一個觀察序列O=O1O2...OT,和模型μ=（A,B,π），如何快速有效地選擇在一定意義下「最優」的狀態序列Q=q1q2...qT，使該狀態最好地解釋觀察序列。
一種想法是求出每個狀態的概率rt(i)最大(rt(i)=P(qt=si,O|μ）)，記q't(i)=argQmax(rt(i))，但是這樣做，忽略了狀態之間的關系，很可能兩個狀態之間的概率為0，即aq't(i)q't+1(i)=0,這樣求得的「最優」狀態序列是不合法的。
為防止狀態之間轉移概率為0（斷續問題），換一種思路，不是求單個狀態求得最大值，而是求得整個狀態序列最大值，即求
Q'= argQmaxP(Q|O,μ）
此時用維特比演算法，先定義下維特比變數δt(i):在時間t，HMM沿著一條路徑到達狀態si，並輸出觀察序列O=O1O2...Ot的最大概率:
δt(i)=max P(q1q2...qt=si,O1O2...Ot|μ)

⑺ 如何用r語言編寫viterbi演算法

Viterbi解碼演算法是由Viterbi於1967年提出的一種最大似然解碼辦法，解碼器根據接收序列R按最大似然准則力圖找出正確的原始碼序列。隨著大規模集成電路技術的發展，採用Viterbi演算法的卷積編碼技術已成為廣泛應用的糾錯方案。Viterbi解碼過程可用狀態表示。Sj，t和Sj N/2，t表示t時刻的兩個狀態。在t1時刻，這兩個狀態值根據路徑為0或者1，轉移到狀態S2j，t1和S2j1，t1。每一種可能的狀態轉移都根據接收到的有雜訊的序列R計算路徑度量，然後選擇出各個狀態的最小度量路徑(倖存路徑)。Viterbi演算法就是通過在狀態中尋找最小量路徑向前回溯L步，最後得到的即為解碼輸出。
在卷積碼(n，k，m)表示法中，參數k表示每次輸入信息碼位數，n表示編碼的輸出卷積碼位數，m稱為約束長度(一些書中採用k=m1為約束長度，也可稱(2，1，2)碼網格圖，r=k/n稱為信息率，即編碼效率。本文運用的是(2，1，3)碼，約速長度為2，狀態數為22=－4。
TMS320C6000系列DSPs(數字信號處理器)是TI公司推出的一種並行處理的數字信號處理器，是基於TI的VLIW技術的。本文採用的是TMS320C6211。該處理器的工作頻率經過倍頻可達到150MHz，每個時鍾周期最多可並行執行8條指令，從而可以實現1200MIPS定點運算能力。

⑻ 求一段維特比硬判決解碼的matlab代碼。

%一個是硬判決，一個是軟判決的函數，各自存了，然後再調用，注意是兩個函數，別弄混了

function decoder_output=viterbi_hard(y,L)

global G;
n=size(G,1);
K=size(G,2);
number_of_states=2^(K-1);
%------------------------------------------------
%-------------生成各分支的輸出--------------------
%------------------------------------------------
for j=0:number_of_states-1
for t=0:1
[next_state,memory_contents]=next_state_fun(j,t,K);
input(j+1,next_state+1)=t;
branch_output=rem(memory_contents*G',2);
nextstate(j+1,t+1)=next_state;
output(j+1,t+1)=bin2deci(branch_output);
end
end
%------------------------------------------------
metric_of_states=zeros(1,number_of_states); %各狀態的度量metric
metric_of_states_c=zeros(number_of_states,2); %各狀態兩個輸入的度量
length_seq=length(y)/n; %符號個數
decoder_output=zeros(1,length_seq-K+1); %解碼輸出
channel_output_matrix=reshape(y,n,length_seq); %將解調輸出的比特按符號排列
survivor_state=zeros(number_of_states,length_seq+1); %留存路徑
input_of_state=zeros(number_of_states,length_seq+1,2); %匯聚到各狀態的分支對應的輸入
state_sequence=zeros(1,length_seq+1);
count=zeros(1,number_of_states);
for i=1:length_seq-K+1
%------------------------------------------------
for j=0:number_of_states-1
for t=0:1
binary_output=deci2bin(output(j+1,t+1),n); %將各分支的輸出轉換為2進制
branch_metric=Hamming_dis(channel_output_matrix(:,i)',binary_output); %計算分支度量
count(nextstate(j+1,t+1)+1)=count(nextstate(j+1,t+1)+1)+1;
metric_of_states_c(nextstate(j+1,t+1)+1,count(nextstate(j+1,t+1)+1))=metric_of_states(j+1)+branch_metric; %計算累積度量（加）
input_of_state(nextstate(j+1,t+1)+1,:,count(nextstate(j+1,t+1)+1))=survivor_state(j+1,:); %該分支所在路徑的對應的輸入
input_of_state(nextstate(j+1,t+1)+1,i,count(nextstate(j+1,t+1)+1))=t;
end;
end;
%----------------比較匯聚到同一狀態的兩條路徑，選取距離較小的-----------------
for j=0:number_of_states-1
if metric_of_states_c(j+1,1)>=metric_of_states_c(j+1,2)
metric_of_states(j+1)=metric_of_states_c(j+1,2);
survivor_state(j+1,:)=input_of_state(j+1,:,2);
else
metric_of_states(j+1)=metric_of_states_c(j+1,1);
survivor_state(j+1,:)=input_of_state(j+1,:,1);
end;
end;
count=zeros(1,number_of_states);
%--------------------------截短輸出------------------------------------
if i>L
[min_metric,location]=min(metric_of_states);
decoder_output(i-L)=survivor_state(location,i-L);
end;
end
%---------------------最後L個比特解碼輸出--------------------------------
[min_metric,location]=min(metric_of_states);
decoder_output(length_seq-K+1-L+1:length_seq-K+1)=survivor_state(location,length_seq-K+1-L+1:length_seq-K+1);
========================華麗的分割線=================================

%以上為硬判決，一下為軟判決

function decoder_output=viterbi_soft(y,L)
global G;
n=size(G,1);
K=size(G,2);
number_of_states=2^(K-1);
for j=0:number_of_states-1
for t=0:1
[next_state,memory_contents]=next_state_fun(j,t,K);
input(j+1,next_state+1)=t;
branch_output=rem(memory_contents*G',2);
nextstate(j+1,t+1)=next_state;
output(j+1,t+1)=bin2deci(branch_output);
end
end
metric_of_states=zeros(1,number_of_states);
metric_of_states_c=zeros(number_of_states,2);
length_seq=length(y)/n;
decoder_output=zeros(1,length_seq-K+1);
channel_output_matrix=reshape(y,n,length_seq);
survivor_state=zeros(number_of_states,length_seq+1);
input_of_state=zeros(number_of_states,length_seq+1,2);
state_sequence=zeros(1,length_seq+1);
count=zeros(1,number_of_states);
for i=1:length_seq-K+1
flag=zeros(1,number_of_states);
for j=0:number_of_states-1
for t=0:1
binary_output=deci2bin(output(j+1,t+1),n);
branch_metric=cor_dis(channel_output_matrix(:,i)',binary_output);
count(nextstate(j+1,t+1)+1)=count(nextstate(j+1,t+1)+1)+1;
metric_of_states_c(nextstate(j+1,t+1)+1,count(nextstate(j+1,t+1)+1))=metric_of_states(j+1)+branch_metric;
input_of_state(nextstate(j+1,t+1)+1,:,count(nextstate(j+1,t+1)+1))=survivor_state(j+1,:);
input_of_state(nextstate(j+1,t+1)+1,i,count(nextstate(j+1,t+1)+1))=t;
end;
end;
for j=0:number_of_states-1
if metric_of_states_c(j+1,1)<=metric_of_states_c(j+1,2)
metric_of_states(j+1)=metric_of_states_c(j+1,2);
survivor_state(j+1,:)=input_of_state(j+1,:,2);
else
metric_of_states(j+1)=metric_of_states_c(j+1,1);
survivor_state(j+1,:)=input_of_state(j+1,:,1);
end;
end;
count=zeros(1,number_of_states);
if i>L
[max_metric,location]=max(metric_of_states);
decoder_output(i-L)=survivor_state(location,i-L);
end;
end

[max_metric,location]=max(metric_of_states);
decoder_output(length_seq-K+1-L+1:length_seq-K+1)=survivor_state(location,length_seq-K+1-L+1:length_seq-K+1);

⑼ 誰有Turbo碼軟輸入軟輸出的迭代解碼程序（Map和Max_Log_Map）VC++的更好

編碼率是一個裝置，以確保可以恢復原始信息流速度。一般流率越低，編碼效率越高。

1993年兩個法國教授Berrou，Glavieux和緬甸博士生Thitimajshima，發表在柏林國際會議Turbo碼接近香農限的錯誤糾正編碼和解碼：Turbo碼「，一個新的物種的編碼 - Turbo碼它巧妙兩個簡單的分量代碼，通過偽隨機交織器並聯串聯構造的長碼的偽隨機性質，和由兩個軟輸入/軟輸出（SISO）1/2的Turbo碼解碼器的迭代次數之間實現了偽隨機解碼
該
模擬結果表明，AWGN信道，比特率達到了（這種情況下的誤碼率（BER）≤10-5時，Eb/N0的只有約0.7分貝實現理想的通道的Eb/N0值0分貝的能力），遠遠超過了其他編碼，有時會造成在該領域的信息和編碼理論的轟動。
自那時以來，受到了廣泛的關注和Turbo碼發展，產生了深遠的影響，在今天的編碼理論和研究方法，信道編碼學校也進入了一個新的階段。
-> Turbo碼的通道，由於其接近Shannon行業，突出的糾錯能力已成為熱點問題在近年來的編碼理論研究。編碼器組成的反饋系統中的兩個（或更多），通過並行級聯卷積碼的交織器，從接收端一般按位最大後驗概率解碼器，通過迭代周期解碼。
渦輪代碼是一個重要特徵是其更復雜的解碼比傳統卷積碼的絡合物，這種復雜的，僅在它的解碼Turbo碼使用的演算法迭代過程中，所使用的演算法是也比較復雜。鍵是不僅要能夠每個位進行解碼，同時還伴有解碼翻譯的每一個位的信息的可靠性，並且這些信息，以進行的迭代。Turbo碼解碼的具體演算法為：MAP（最大後驗後）
</最大-LOG-MAP LOG-MAP和軟輸出維特比演算法（SOVA）演算法。MAP演算法是1974年的卷積碼解碼，但仍然需要做一些Turbo碼解碼;最大LOG-MAP，LOG-MAP地圖演算法是基於的量的計算進行了重大的改進，雖然性能的一些下降，但該Turbo碼解碼的復雜性大大降低，和更適合於實際使用的維特比演算法是不適合的Turbo碼翻譯代碼，原因是，有沒有可靠的資料翻譯位輸出的SOVA演算法，改進與軟信息輸出，適合Turbo碼解碼演算法的復雜度和性能有一些差異。系統地了解這些演算法的原則是Turbo碼的基礎上的比較研究這些演算法的復雜度和性能也將有助於渦輪增壓的應用研究。

⑽ 誰能通俗的講解下viterbi演算法嗎

Viterbi 演算法是一種動態規劃演算法，一般用於序列的解碼。簡單地說，序列中每一個點有一個狀態，Viterbi 演算法的目的是要找到每一個點的狀態，使得這個序列的解碼結果全局較優。一般的路徑規劃演算法的搜索空間大，Viterbi 演算法對狀態轉移進行了限制，大大減少了搜索空間，解碼速度是 O(n^2) 的。通過後向鏈接，Viterbi 的解碼結果可以以序列方式呈現。