[發明專利]譯碼方法及其裝置

有效

• 申請號: 200910178186.9
• 申請日: 2009-10-19
• 公開（公告）號: CN102045070A
• 公開（公告）日: 2011-05-04
• 發明（設計）人: 林東升;何天行;洪紹評;莊景翔;顧育先
• 申請（專利權）人: 晨星軟件研發(深圳)有限公司;晨星半導體股份有限公司
• 主分類號: H03M7/00
• 分類號: H03M7/00;H03M13/00;H03K19/20
• 代理公司: 北京市浩天知識產權代理事務所 11276
• 代理人: 劉云貴

技術領域

本發明有關于譯碼裝置及其方法，特別是有關于一種用于譯碼程序中決定較佳存活路徑的譯碼方法及其裝置。

背景技術

在通訊系統中，發射端發射通信訊號至遠程的接收端，通信訊號經過無線信道通常會造成訊號衰減(fading)并導致訊號錯誤等現象。因此，通信訊號需進行回旋編碼(convolutional?encoding)后才發射至遠程，再由遠程的接收器對回旋編碼后的通信訊號進行回旋譯碼(convolutional?decoding)以取得通信訊號，如此即可減少訊號錯誤的現象。回旋編碼系一種信道編碼(channel?encoding)，可由信道編碼器執行。在信道編碼中碼字(codeword)的輸出不但與目前輸入的消息位(information?bit)有關，更受到之前輸入的消息位的影響，所以碼字具有記憶性。一般而言，回旋碼包括三個參數(n，k，m)，亦即每k個位消息產生n個碼字輸出，而且這n個位碼字輸出是由前面m個消息位與目前輸入的k個消息位所決定；其中，k與n的比值R＝k/n，稱為回旋碼的碼率(code?rate)，代表每個碼字所含有的消息量，而m定義為記憶級數(memory?order)，表示輸入消息位在編碼器中需儲存的單位時間，也就是編碼器所需的緩存器數目，記憶級數越高回旋碼的錯誤更正能力也越高。另一常用的系數是束縛長度(constraint?length)，對于k＝1的編碼器而言，束縛長度可以表示為K＝m+1，其代表編碼器輸出的位可被影響的最大位數目。

回旋碼編碼器可視為一個有限狀態機(finite?state?machine)，可以用一個狀態圖(state?diagram)來描述其輸入與輸出的關系，所有狀態都是由編碼器的位移緩存器中的內容所定義而成。

圖1(a)為現有技術的(2，1，2)回旋碼狀態圖，圖1(b)為現有技術的(2，1，2)回旋碼柵狀圖。(2，1，2)回旋碼編碼器其記憶級數m＝2，因此共有2²＝4個狀態。建立其狀態圖如第一圖A，可以將每一單位時間對應狀態轉移的表達方式進一步地將狀態圖擴展形成柵狀圖(trellis?diagram)，如第一圖B。

由柵狀圖可得知每一輸入消息序列(information?sequence)編碼時所經過的路徑及所對應的碼字。如狀態S₀由輸入消息位0或1，改變至狀態S₀或狀態S₁。輸出的碼字不僅與目前的狀態有關，而且與輸入的消息位有關。在接收端也可透過接收序列并利用柵狀圖找出可能傳送的碼字，這就是回旋碼的譯碼動作。

至目前為止，現有技術針對回旋碼所提出的譯碼算法有相當多種，而維特比算法(Viterbi?algorithm)是其中較有效率的近似譯碼算法。以下舉(2，1，2)回旋碼說明如何利用維特比算法譯碼回旋碼。首先介紹一些名詞定義。兩個碼字的距離代表兩個碼字不相等的位的數目，例如：(10)與(01)的距離為2，而(11)與(01)的距離為1。分支路徑計量值(branch?metric)表示接收到的序列與分支路徑碼字間的距離，由狀態S_i在時間T＝t時進入狀態S_j的分支路徑計量值，記為BM_i，j，t。累積路徑計量值(accumulated?path?metric)表示至時間T＝t時，所有會到狀態S_j的路徑其分支路徑計量值總和的最小值，記為PM_j，t。存活路徑(survivor?path)表示至譯碼結束后，進入具有最小累積路徑計量值的狀態的路徑。

舉例而言，初始狀態為S₀，時間由T＝0開始，傳送的消息序列為u＝(0，1，0，1，0)，經過(2，1，2)回旋編碼器之后得到的碼字為v＝(00，11，10，00，10，11，00)。受到二位對稱信道的影響，接收到的碼字序列(codeword?s?equence)為r＝其中有一個位發生錯誤(以粗體表示)。