[發明專利]一種兩階段的低復雜度極化碼構造方法

在審

• 申請號: 201910074150.X
• 申請日: 2019-01-25
• 公開（公告）號: CN109787640A
• 公開（公告）日: 2019-05-21
• 發明（設計）人: 劉榮科;馮寶平
• 申請（專利權）人: 北京航空航天大學
• 主分類號: H03M13/13
• 分類號: H03M13/13
• 代理公司: 北京永創新實專利事務所 11121
• 代理人: 祗志潔

1.一種兩階段的極化碼構造方法，其特征在于，包括如下步驟：

步驟1：根據碼長N和碼率R，獲得信息位長度K＝N*R；

步驟2：對子信道索引，根據加法規則Addition Operator和左交換規則Left-swapOperator進行運算，建立子信道之間可靠性的相對大小關系；

步驟3：根據得到的相對大小關系構建二分圖，二分圖中將每個子信道作為一步驟2個頂點，對于兩個子信道u和v，當且僅當u的可靠性小于v的可靠性時，二者之間存在一條邊；然后采用最大匹配優化Hopcroft-Karp算法得到二分圖的最大匹配；

步驟4：根據二分圖的最大匹配將所得的二分圖劃分成鏈，每條鏈中的所有元素以偏序關系“＜”順序連接；

步驟5：執行粗構造過程，從鏈元素中選擇子信道加入信息集中，包括：

(1)從鏈中選取劃分元，設置閾值；每次尋找所有鏈中選擇的劃分元所對應的子信道中可靠性最大的元素作為當前閾值；(2)根據當前閾值，在所有鏈中選擇可靠性大于該閾值的子信道并加入信息集中；對于閾值所在的鏈直接選擇劃分元之前的元素加入信息集；對于其余鏈，對每條鏈的劃分元之前的元素利用二分查找法找到第一個小于劃分元的元素位置，然后將該位置之前的元素都加入到信息集中；

步驟6：設當前信息集中的元素數目為K’，判斷K’是否大于K，若是，則對當前加入信息集中的所有鏈元素，執行步驟5的粗構造過程，若否，繼續執行步驟7；

步驟7：當前信息集中的元素數目K’小于K時，執行細構造過程；所述的細構造過程提供三種選擇方法如下：

(A)繼續執行步驟5的粗構造過程，從剩余的鏈元素中選取K-K’個元素；

(B)設剩余的鏈的數目為S，對每條鏈剩余的元素，選取鏈首n個元素，使得(n-1)S<K-K’<nS，計算所選取的nS個元素的可靠性，排序選出其中可靠性最高的K-K’個元素加入信息集中；

(C)設剩余的鏈的數目為S，對每條鏈剩余的元素，選取鏈首n個元素，使得(n-1)S<K-K’<nS，對所選取的nS個元素，根據子信道的索引計算子信道的權重系數，排序選出其中權重系數最高的K-K’個元素加入信息集中。

2.根據權利要求1所述的方法，其特征在于，所述的步驟5中，根據隨機選擇法、中值選擇法或碼率選擇法從鏈中選取劃分元。

3.根據權利要求1所述的方法，其特征在于，所述的步驟5中，采用中值選擇法從鏈中選取劃分元，包括：根據碼率R將每條鏈在中點處劃分為兩部分，設第t條鏈的長度為L_t，對第t條鏈，選擇該鏈的第|L_t|/2個元素作為劃分元。

4.根據權利要求1所述的方法，其特征在于，所述的步驟5中，采用碼率選擇法從鏈中選取劃分元，包括：將每條鏈按照R：(1-R)的比例劃分為兩部分，設第t條鏈的長度為L_t，對第t條鏈，選擇該鏈的第|L_t|*R個元素作為劃分元。

5.根據權利要求1或4所述的方法，其特征在于，所述的步驟6中，當步驟5中選取碼率選擇法從鏈中選取劃分元時，首先更新率R＝(K—K’)/(N—K’)，然后再執行步驟5。

6.根據權利要求1所述的方法，其特征在于，所述的步驟6中，還設置粗構造過程的終止條件為0<K-K′≤M，如果當前信息集的元素數目K′滿足該條件，則終止粗構造過程，否則需要繼續執行粗構造過程。