論文封面格式

中 華 大 學 碩 士 論 文 設 計 一 個 結 構 化 的 低 密 度 同 位 元 檢 查 碼 使 能 有 較 大 周 長 及 改 進 錯 誤 率 平 緩 之 現 象 Design of Structured LDPC Codes with Large Girth and Low Error Floor 系 所 別 : 資 訊 工 程 系 碩 士 班 學 號 姓 名 :M09702038 董 致 銓 指 導 教 授 : 王 俊 鑫 教 授 中 華 民 國 100 年 8 月

摘 要 低 密 度 同 位 元 檢 查 碼 (LDPC codes) 近 年 來 已 受 到 各 界 的 矚 目, 可 應 用 在 通 訊 系 統 或 是 資 料 儲 存 上, 我 們 透 過 實 驗 來 最 佳 化 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 的 演 算 法 中 放 大 倍 率 的 選 擇, 在 固 定 長 度 下 的 低 密 度 同 位 元 檢 查 碼 可 以 將 最 小 周 長 放 得 更 大, 在 固 定 的 最 小 周 長 限 制 下 可 以 減 少 所 需 的 碼 的 長 度 和 文 獻 中 的 方 法 比 較, 除 了 保 有 原 有 演 算 法 的 優 點, 可 以 建 構 任 意 的 行 權 重 列 權 重 及 最 小 周 長 的 矩 陣 外, 本 論 文 的 貢 獻 為 證 明 了 要 達 到 目 標 的 最 小 周 長 而 放 大 的 倍 率 可 以 縮 小 很 多, 藉 此 可 大 幅 降 低 硬 體 所 需 的 複 雜 度 及 成 本 此 外, 模 擬 結 果 顯 示 依 照 本 文 中 演 算 法 所 建 構 出 的 LDPC code 之 位 元 錯 誤 率 具 有 較 低 的 錯 誤 率 可 以 縮 小 平 緩 之 現 象 關 鍵 字 : 最 小 周 長 (girth) 低 密 度 同 位 元 檢 查 碼 (LDPC code) 迴 圈 (cycle) 二 分 圖 (Bipartite graph) i

ABSTRACT LDPC (low-density parity-check) code has been popular in recent years with applications in communication systems or data storage. In this paper, we present a fine-tuned partition-and-shift LDPC code construction algorithm with better choice of scaling factors. It is proved that we can either increase the girth of a fixed-length LDPC code or reduce the required code-length for a fixed girth constraint. Similar to the existing method in the literature, the constructed LDPC codes can have arbitrary column weight, row weight and girth. The codes we constructed have smaller scaling factors which implies lower hardware complexity and cost. With the reduced code length or increased girth, our simulation shows the error floor can be extended even lower. Keywords: girth LDPC codes cycle Bipartite graph ii

致 謝 寫 著 這 致 謝 的 同 時, 也 將 整 個 碩 士 生 涯 快 速 的 瀏 覽 一 遍, 果 然, 記 憶 裡 那 種 痛 苦 掙 扎 的 感 覺 是 淡 了 些, 而 那 些 曾 經 在 緊 要 關 頭 讓 我 突 破 困 境 的 關 鍵 畫 面 卻 還 是 一 樣 鮮 明! 從 碩 士 一 年 級 開 始, 我 就 認 為 做 研 究 是 一 個 很 艱 辛 的 任 務, 隨 著 時 光 流 失, 也 拼 過 來 了, 感 謝 的 人 真 的 是 不 少 首 先 我 要 感 謝 指 導 教 授 翁 文 彥 老 師 三 年 來 的 栽 培 與 關 懷, 謝 謝 他 讓 我 在 學 習 的 過 程 中 給 予 我 相 當 大 的 幫 助, 還 給 了 我 充 分 的 機 會 與 空 間, 鼓 勵 我 勇 敢 的 拼 下 去, 引 導 我 對 自 己 的 未 來 譜 出 不 同 以 往 的 願 景, 讓 我 在 學 術 上 與 生 活 上 都 留 下 許 多 深 刻 且 精 彩 美 好 的 體 驗 與 成 長 在 碩 士 班 的 日 子 裡, 實 驗 室 就 像 第 二 個 家, 在 這 裡 所 結 識 的 夥 伴 都 是 幫 助 我 成 長 的 重 要 人 物 因 此 我 要 感 謝 實 驗 室 裡 的 所 有 同 學 : 小 三 阿 哲 小 飛 阿 光 及 阿 緯 學 弟, 不 論 是 在 哈 拉 還 是 在 做 研 究 上, 都 給 我 了 我 相 當 大 的 關 心 與 幫 助, 像 是 會 幫 我 看 我 的 論 文 哪 邊 寫 的 不 好 阿 句 子 順 不 順 阿 無 聊 的 時 候 又 能 夠 哈 拉 一 下 能 夠 認 識 你 們, 是 我 碩 士 生 涯 加 大 學 生 涯 中 最 重 要 的 收 穫 最 後, 我 要 感 謝 我 的 家 人 為 我 提 供 一 個 溫 暖 安 靜 的 窩, 讓 我 可 以 沈 澱 忙 碌 的 實 驗 和 慌 亂 的 情 緒, 謝 謝 爸 爸 媽 媽 對 我 的 寵 愛 和 信 任, 讓 我 可 以 全 心 專 注 在 自 己 的 課 業 上, 不 用 為 許 多 繁 瑣 的 事 情 分 心 在 完 成 這 份 論 文 的 過 程 中, 我 一 直 是 患 得 患 失 的, 而 今 能 走 到 最 後, 繳 出 一 份 令 人 滿 意 的 成 果, 最 要 感 謝 的 是 還 是 這 一 路 上 曾 幫 助 過 我 的 師 長 與 朋 友 們, 感 謝 你 們, 我 願 把 這 份 榮 耀 和 你 們 分 享, 謝 謝! iii

目 錄 摘 要... i ABSTRACT... ii 致 謝... iii 目 錄... iv 表 目 錄... v 圖 目 錄... vi 一 簡 介... 1 二 背 景 介 紹... 4 2.1 錯 誤 更 正 碼... 4 2.2 低 密 度 同 位 元 檢 查 碼 - 編 碼... 6 2.3 低 密 度 同 位 元 檢 查 碼 - 解 碼... 8 三 PS-LDPC code... 12 3.1 分 割 及 位 移 設 計... 12 3.2 迴 圈 與 位 移 的 關 係... 16 3.3 最 小 周 長 的 邊 界... 17 3.4 任 意 的 最 小 周 長... 18 四 針 對 分 割 及 位 移 LDPC code 之 改 進... 24 4.1 已 知 演 算 法 之 缺 點... 24 4.2 改 進 方 法... 24 4.3 實 驗 結 果 與 比 較... 26 五 錯 誤 率 之 模 擬 與 分 析... 31 六 結 論... 34 參 考 文 獻... 35 iv

表 目 錄 表 4-1. 達 到 最 小 周 長 為 g 所 需 的 最 小 p 值... 28 表 4-2. [ 實 驗 2] 方 法 1 的 結 果... 29 表 4-3. [ 實 驗 2] 方 法 2 的 結 果... 29 v

圖 目 錄 圖 2-1. 錯 誤 更 正 碼 的 運 作 流 程... 4 圖 2-2. 舉 例 的 模 擬 圖... 5 圖 2-3. IEEE 802.16e 標 準 奇 偶 檢 查 矩 陣 格 式... 6 圖 2-4. 二 分 圖 與 LDPC codes 矩 陣 H 的 轉 換... 8 圖 2-5. MPA 初 始 二 分 圖... 9 圖 2-6. Row processing 示 意 圖... 10 圖 2-7. column processing 示 意 圖... 11 圖 3-1. 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 的 二 分 圖... 13 圖 3-2. 二 分 圖 轉 換 的 矩 陣 圖... 13 圖 3-3. 試 算 位 移 值... 14 圖 3-4. 二 分 圖 所 相 對 應 的 位 移 矩 陣 S... 14 圖 3-5. (a): S 中 的 封 閉 路 徑 (b): 在 二 分 圖 中 的 6 迴 圈... 17 圖 3-6. 演 算 法 1 的 pseudo code[10]... 19 圖 3-7. 演 算 法 1 的 流 程 圖... 20 圖 3-8. 演 算 法 2 的 pseudo code[10]... 22 圖 3-9. 演 算 法 2 的 流 程 圖... 23 圖 4-1. 建 樹 的 舉 例 圖... 25 圖 4-2. 避 免 掉 4 迴 圈 的 S 矩 陣... 26 圖 4-3. 最 小 周 長 為 14 的 S 矩 陣... 27 圖 4-4. 最 小 周 長 為 16 的 S 矩 陣... 28 圖 4-5. 最 小 周 長 為 6 的 矩 陣 H... 29 圖 5-1. 模 擬 1... 31 圖 5-2. 模 擬 2... 32 vi

一 簡 介 隨 著 無 線 或 有 線 的 通 訊 系 統 資 料 儲 存 的 應 用 蓬 勃 發 展, 在 資 料 傳 輸 上, 訊 息 的 流 通 量 急 速 增 加, 造 成 高 傳 輸 率 高 可 靠 度 的 通 訊 系 統 是 必 頇 的 但 資 料 傳 輸 過 程 中, 常 常 會 因 為 外 在 的 因 素 導 致 資 料 受 到 破 壞, 為 了 達 到 高 可 靠 度 及 高 效 率 的 傳 輸 品 質, 錯 誤 更 正 碼 (Correction Code) 就 扮 演 舉 足 輕 重 的 角 色, 目 的 就 是 能 將 錯 誤 的 資 料 救 回 來 的 一 個 機 制, 確 保 資 料 傳 輸 的 正 確 性 錯 誤 更 正 碼 早 已 廣 泛 運 用 於 有 線 通 訊 無 線 通 訊 及 許 多 儲 存 媒 體 系 統 上, 藉 著 額 外 加 入 的 位 元 訊 息 來 保 護 原 始 的 資 料, 也 就 是 編 碼 的 過 程 在 資 料 接 收 端, 利 用 額 外 加 入 的 位 元 訊 息 來 達 到 傳 輸 過 程 中 之 位 元 錯 誤 的 偵 測 (Error Detection), 修 正 錯 誤 的 能 力 通 常 與 額 外 加 上 的 資 料 多 寡 有 關, 一 般 而 言, 額 外 的 資 料 越 多, 所 能 修 正 的 錯 誤 也 越 多, 這 就 是 解 碼 的 過 程, 並 且 能 將 錯 誤 的 資 訊 更 正 為 正 確 的, 有 效 降 低 位 元 錯 誤 率 (Bit Error Rate) 早 在 1948 年 Shannon 提 出 Shannon- 極 限 定 理 後, 各 種 錯 誤 更 正 碼 就 開 始 被 提 出 討 論, 初 期 較 為 人 熟 知 的 有 區 塊 碼 (Block Code) 漢 明 碼 (Hamming Code) 迴 旋 碼 (Convolutional Code), 以 及 近 十 年 來 比 較 重 視 的 渦 輪 碼 (Turbo Code) 和 Low-Density-Parity-Check Code (LDPC) LDPC Code 在 1962 年 由 Gallager[1] 所 發 明, 不 過 當 時 的 電 腦 無 法 處 理 龐 大 的 運 算 而 且 硬 體 複 雜 度 過 高 導 致 此 理 論 只 能 束 之 高 閣, 被 人 們 遺 忘 了 將 近 30 年,1993 年 發 明 的 渦 輪 碼, 距 離 通 道 容 量 只 有 1db, 直 到 1995 年 Mackay 與 Neal 重 新 提 出 研 究 後 而 發 展 的 解 碼 演 算 法, 卻 可 以 逼 近 通 道 容 量 至 0.0045db[16], 且 相 較 於 渦 輪 碼 亦 有 較 低 的 計 算 複 雜 度 才 開 始 被 廣 泛 的 討 論 應 用, 所 以 在 最 新 的 無 線 通 訊 標 準 IEEE 802.16e 標 準 中, 已 經 將 LDPC Code 納 入 其 解 碼 器 的 選 項 之 一 而 且 在 下 一 代 的 衛 星 數 位 視 訊 廣 播 標 準 (DVB-S2) 中, 也 將 低 密 度 同 位 元 檢 查 碼 取 代 了 渦 輪 碼, 拜 現 今 硬 體 製 作 技 術 的 進 步, 高 速 的 平 行 解 碼 製 作 方 式 得 以 實 現, 使 得 LDPC Codes 已 成 為 目 前 相 當 熱 門 的 研 究 領 域 在 通 訊 系 統 中, 資 料 在 傳 輸 時 因 為 有 某 些 外 在 因 素, 使 得 接 收 到 的 資 料 發 生 錯 誤 像 是 受 到 雜 訊 干 擾, 或 者 傳 輸 媒 介 可 靠 度 不 佳 等 等 錯 誤 更 正 碼 藉 由 傳 遞 多 餘 的 1

校 正 資 訊, 使 得 解 碼 器 能 在 資 訊 發 生 錯 誤 時, 設 法 於 更 正 回 來 低 密 度 同 位 元 檢 查 碼 (Low Density Parity-Check Code; 簡 稱 LDPC Code)[1], 就 是 一 種 效 能 很 好 的 錯 誤 更 正 碼, 能 夠 有 效 修 正 產 生 錯 誤 的 資 訊, 使 得 錯 誤 率 能 夠 下 降 低 密 度 同 位 元 檢 查 碼 常 以 二 分 圖 (Bipartite graph) 來 表 示 [2], 在 二 分 圖 中, 最 短 的 迴 圈 (the shortest cycle) 之 長 度 稱 為 此 二 分 圖 的 最 小 周 長 (girth) 設 計 在 二 分 圖 中 使 能 夠 有 較 大 的 最 小 周 長 對 於 低 密 度 同 位 元 檢 查 碼 的 效 能 有 重 要 意 義 在 低 密 度 同 位 元 檢 查 碼 的 解 碼 程 序 之 中, 透 過 和 積 演 算 法 (sum-product algorithm) 將 事 後 機 率 (posteriori probability) 的 問 題 最 佳 化, 並 且 重 複 的 週 期 運 算 (iteration) 二 分 圖 裡 的 短 迴 圈 會 造 成 解 碼 上 運 算 的 負 擔, 使 解 碼 後 的 結 果 無 法 收 斂 到 正 確 的 解 [3] 因 此, 較 大 的 最 小 周 長 通 常 是 設 計 低 密 度 同 位 元 檢 查 碼 時 的 一 個 重 要 目 標 研 究 發 現 [10], 在 低 密 度 同 位 元 檢 查 碼 的 設 計 裡, 碼 中 的 最 小 距 離 (minimum distance, 簡 稱 d min )[2] 會 決 定 低 密 度 同 位 元 檢 查 碼 在 高 訊 雜 比 (high-snr) 時 的 效 能 然 而, 設 計 一 個 有 較 大 的 最 短 距 離 的 低 密 度 同 位 元 檢 查 碼, 複 雜 度 極 高 [10] 發 現, 最 小 距 離 會 與 最 小 周 長 有 正 相 關, 因 此 可 藉 由 較 低 複 雜 度 的 演 算 法 來 加 大 最 小 周 長, 進 而 設 計 出 有 較 大 的 最 小 距 離 的 低 密 度 同 位 元 檢 查 碼 在 許 多 不 同 類 型 的 低 密 度 同 位 元 檢 查 碼 架 構 中, 循 環 (cyclic) 和 類 循 環 (quasi-cyclic) 是 兩 種 硬 體 實 作 複 雜 度 較 低 的 設 計, 類 似 架 構 的 編 碼 包 含 有 限 幾 何 碼 (finite-geometry codes)[4] 平 衡 不 完 全 區 塊 設 計 碼 (BIBD codes)[5] 代 數 建 構 (algebraic construction)[6] 及 佛 索 瑞 爾 法 (Fossorier s work)[7] 等 等 [8][9] 佛 索 瑞 爾 法 [7] 能 證 實 它 能 夠 讓 循 環 和 類 循 環 這 兩 種 的 同 位 元 檢 查 矩 陣 (parity-check matrix) 沒 有 零 的 區 塊 且 最 小 周 長 至 少 能 到 達 12 然 而 嚴 格 的 循 環 和 類 循 環 這 兩 種 架 構 不 太 適 合 應 用 在 碼 的 長 度 非 常 長 的 時 候, 因 為 它 們 較 小 的 最 小 周 長 在 碼 的 長 度 很 長 時 會 限 制 住 它 們 的 應 用 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 (Partition-and-Shift LDPC; 簡 稱 PS-LDPC)[10] 是 一 種 特 殊 結 構 的 低 密 度 同 位 元 檢 查 碼, 其 保 有 部 分 類 循 環 LDPC code 低 硬 體 複 雜 度 的 優 點, 又 能 達 到 較 大 的 最 小 周 長, 可 以 說 是 一 個 具 有 實 用 性 的 折 衷 方 案 本 文 參 考 [10] 的 方 法, 用 PS-LDPC code 來 建 構 有 任 意 的 最 小 周 長 任 意 的 行 權 重, 以 及 有 彈 性 的 碼 率 的 LDPC code, 並 且 嘗 試 將 其 最 佳 化 透 過 實 驗, 我 們 發 現 欲 達 到 所 設 定 的 girth 目 標 所 需 的 LDPC 矩 陣 之 大 小 可 以 大 幅 度 的 降 低, 所 設 計 出 的 LDPC code 之 錯 誤 率 表 現 也 較 前 人 之 成 果 更 佳 2

本 論 文 裡, 採 用 分 割 及 位 移 LDPC Codes(PS-LDPC code) 的 架 構, 再 加 入 條 件 檢 查 特 性 為 : 1. 利 用 分 割 及 位 移 的 方 法 再 加 入 迴 圈 條 件, 可 以 避 免 迴 圈 的 產 生 2. 使 用 Lu 的 演 算 法 1 及 演 算 法 2, 再 透 過 放 大 倍 率 P 的 限 制 式, 可 以 將 原 本 最 小 周 長 為 g 的 矩 陣, 最 多 放 大 成 3g, 也 就 是 最 小 周 長 最 大 可 以 放 大 3 倍 我 們 針 對 Lu[10] 的 方 法 提 出 疑 點, 在 Lu 的 實 驗 中, 透 過 放 大 倍 率 P 的 限 制 式, 要 將 girth 從 6 放 大 到 14 所 需 要 的 P 值 為 9332 倍, 可 是 實 驗 裡 使 用 的 P 值 卻 只 有 607 倍, 差 距 有 點 大, 這 會 令 人 懷 疑 是 否 真 的 能 讓 最 小 周 長 是 否 真 的 能 最 大 放 大 3 倍, 或 者 是 超 過 3 倍 當 達 成 一 樣 的 最 小 周 長 g 時, 假 如 碼 的 長 度 可 以 比 Lu 的 方 法 做 出 來 的 短, 代 表 放 大 的 P 值 比 Lu 的 方 法 小 也 可 以 說, 碼 的 長 度 一 樣 時, 假 如 最 小 周 長 還 可 以 比 改 進 前 放 的 更 大 的 話, 表 式 錯 誤 率 就 能 得 到 更 低 的 錯 誤 率 了 這 就 是 我 們 這 篇 論 文 的 研 究 動 機 與 目 的 本 篇 論 文 分 為 六 個 章 節, 第 一 章 介 紹 了 撰 寫 本 篇 論 文 的 動 機 和 目 的, 第 二 章 介 紹 了 LDPC Codes 的 背 景, 包 含 編 碼 及 解 碼 的 介 紹 第 三 章 介 紹 了 PS-LDPC code 的 相 關 研 究 及 設 計 方 法 第 四 章 提 出 針 對 已 知 PS-LDPC code 設 計 方 法 的 質 疑, 並 且 提 出 方 法 加 以 改 良 第 五 章 為 本 篇 論 文 之 實 驗 與 設 計 之 結 果 與 錯 誤 率 之 模 擬, 並 與 前 人 之 成 果 加 以 比 較 第 六 章 則 為 本 篇 論 文 的 總 結 3

二 背 景 介 紹 本 章 節 將 會 介 紹 錯 誤 更 正 碼 的 基 本 原 理 LDPC codes 的 編 碼 及 解 碼 相 關 介 紹 2.1 錯 誤 更 正 碼 錯 誤 更 正 碼 的 原 理 是 在 原 始 的 資 料 來 源 端, 因 為 傳 送 的 環 境 可 能 惡 劣 或 者 是 外 在 因 素 的 關 係 會 使 得 資 料 遭 受 到 破 壞, 所 以 必 頇 加 上 額 外 的 資 料 來 保 護 原 始 的 資 料, 這 就 是 編 碼 在 接 收 資 料 端, 利 用 這 些 額 外 加 上 的 資 料, 來 判 別 原 始 資 料 是 否 有 錯 誤, 將 保 護 過 的 資 料 解 碼 後 成 為 原 始 我 們 要 的 資 料, 這 過 程 就 是 解 碼 更 正 錯 誤 的 能 力 通 常 與 額 外 加 上 的 資 料 多 寡 有 關, 一 般 而 言, 額 外 的 資 料 越 多, 所 能 更 正 的 錯 誤 也 越 多, LDPC 也 是 利 用 此 種 方 式 來 達 到 更 正 錯 誤 的 效 果 如 下 圖 2-1, 就 是 一 個 錯 誤 更 正 碼 的 運 作 流 程 圖 2-1. 錯 誤 更 正 碼 的 運 作 流 程 4

如 上 圖 2-1, 錯 誤 更 正 碼 是 應 用 在 OSI 網 路 七 層 中 的 實 體 層, 資 料 在 傳 送 之 前, 會 先 經 過 編 碼 (encode), 過 程 中 的 傳 輸 環 境 我 們 稱 為 一 個 通 道 (channel), 在 通 道 中 可 能 會 有 一 些 雜 訊 外 在 干 擾 或 者 訊 號 衰 退 的 關 係, 導 致 原 本 傳 送 端 的 資 料 被 破 壞, 故 在 接 收 端 要 收 到 資 料 之 前, 就 有 一 個 解 碼 (decode) 的 機 制, 解 碼 的 機 制 就 能 將 錯 誤 的 資 料 解 回 正 確 的 當 然 一 個 設 計 良 好 的 編 碼 對 解 碼 的 效 能 影 響 也 是 很 大 的, 除 了 本 身 解 碼 的 演 算 法 好 壞 會 影 響 到 效 能, 編 碼 設 計 的 好, 對 於 解 碼 就 會 有 更 大 的 幫 助, 本 篇 論 文 是 在 探 討 編 碼 在 錯 誤 更 正 碼 中, 錯 誤 率 的 平 緩 現 象 (error floor), 往 往 會 影 響 整 個 效 能, 不 論 是 在 無 線 的 環 境 中, 還 是 資 料 儲 存 上, 當 然 是 希 望 錯 誤 率 越 低 越 好, 要 讓 錯 誤 率 越 來 越 低, 也 就 是 希 望 它 錯 誤 率 的 平 緩 現 象 是 越 來 越 晚 發 生 的 下 圖 2-2 為 舉 例 的 模 擬 圖 分 別 標 示 了 waterfall region 與 error floor 圖 2-2. 舉 例 的 模 擬 圖 Waterfall region 代 表 的 意 思 是 錯 誤 率 正 在 急 驟 下 降 中 的 現 象, 通 常 在 規 則 性 結 構 的 LDPC codes 會 比 較 早 出 現, 萬 一 碼 設 計 的 不 好 的 話,error floor 也 有 可 能 會 比 較 早 5

出 現, 相 對 的 非 規 則 性 結 構 的 LDPC codes 雖 然 waterfall region 會 比 較 晚 出 現, 但 是 通 常 error floor 也 會 比 規 則 性 結 構 的 晚 出 現, 相 對 的 設 計 上 也 會 比 較 複 雜 要 判 斷 錯 誤 更 正 碼 的 效 率 好 壞, 通 常 就 會 像 圖 2-2 一 樣, 會 有 這 種 模 擬 圖 來 呈 現, 一 個 好 的 錯 誤 更 正 碼, 在 當 SNR( 雜 訊 比 ) 值 越 高 的 時 候, 代 表 資 料 加 入 更 多 的 保 護, 所 以 錯 誤 率 一 定 是 要 越 來 越 低 的 才 對, 所 以 我 們 設 計 的 碼, 就 必 頇 讓 error floor 越 晚 出 現 越 好 2.2 低 密 度 同 位 元 檢 查 碼 - 編 碼 LDPC codes 為 一 種 線 性 區 塊 碼 (Linear Block Code), 此 編 碼 的 原 理 是 用 一 個 生 成 矩 陣 (Generate matrix) 與 將 所 要 傳 輸 的 訊 息 作 相 乘 的 動 作, 會 產 生 比 原 始 資 料 還 要 長 的 編 碼 字 (code word), 編 碼 字 長 度 越 長, 則 編 碼 的 效 益 就 越 高 接 收 端 接 收 到 此 訊 號 後 會 與 轉 置 後 的 奇 偶 檢 查 矩 陣 (Parity-Check matrix) 相 乘 來 檢 查 及 修 正 接 收 到 的 資 料 假 設 奇 偶 檢 查 矩 陣 乘 上 編 碼 字 後 得 到 的 結 果 若 全 為 0, 則 此 編 碼 字 為 有 效 的 編 碼 字, 再 經 過 解 碼 回 復 到 原 始 資 料 的 狀 態 一 個 好 的 編 碼 設 計 可 以 增 加 解 碼 的 效 能 一 般 來 說, 奇 偶 檢 查 矩 陣 的 形 式 會 如 下 圖 2-3 表 示 圖 2-3. IEEE 802.16e 標 準 奇 偶 檢 查 矩 陣 格 式 6

這 一 個 奇 偶 檢 查 矩 陣 是 在 2001 年 由 一 個 叫 做 Richardson 的 學 者 所 提 出 來 的, 將 這 矩 陣 分 成 了 六 個 block 其 中 T 為 一 個 下 三 角 矩 陣 令 原 始 資 料 位 元 為 u, 則 傳 輸 資 料 的 codeword 就 為 v=[u p 1 p 2 ](p 1 和 p 2 為 檢 查 位 元 ) 利 用 m n 的 奇 偶 檢 查 矩 陣 H 的 定 義 H v T =0 這 個 關 係 式 : 得 出 : Au T +Bp T 1 +Tp T 2 =0 (2.1) Cu T +Dp T 1 +Ep T 2 =0 (2.2) 由 式 (2.1) 可 得 : p T 2 =T -1 = (AuT+Bp T 1 ) (2.3) 將 式 (2.3) 帶 入 (2.2) 可 得 (D+ET -1 B) p T 1 = (ET -1 A+C) u T (2.4) 令 ø =-ET -1 B+D, 定 義 ø 為 單 位 矩 陣, 所 以 可 推 得 : P 1 T= (ET -1 A+c) u T (2.5) 最 後 完 成 編 碼 字 v=[u p 1 p 2 ] 在 LDPC 碼 的 表 示 中, 一 種 是 用 矩 陣 來 表 示, 另 外 一 種 是 以 二 分 圖 來 表 示, 兩 種 表 示 法 可 以 互 相 轉 換 在 一 個 LDPC code 矩 陣 H 或 由 LDPC code 矩 陣 H 所 轉 換 的 二 分 圖 中, 矩 陣 的 形 式 為 由 0 或 1 所 組 成 的 稀 疏 矩 陣, 由 m 個 檢 查 節 點 (check nodes) 及 n 個 位 元 節 點 (Bit nodes) 所 組 成, 每 一 個 位 元 節 點 由 (0) 2 或 (1) 2 組 成, 每 一 個 檢 查 節 點 會 去 蒐 集 與 自 己 連 接 的 位 元 節 點 的 資 料, 算 看 看 是 否 加 總 為 0, 假 如 為 0, 即 為 正 確 ; 假 如 不 為 0, 資 料 就 發 生 錯 誤, 就 必 頇 透 過 設 計 演 算 法 去 解 決 下 圖 2-4 為 二 分 圖 與 LDPC codes 矩 陣 H 之 間 的 轉 換,V 代 表 位 元 節 點,C 代 表 檢 查 節 點, 總 共 有 3 個 檢 查 節 點 及 3 個 位 元 節 點,V 與 C 有 相 連 的 話 在 矩 陣 上 會 填 入 1, 沒 有 相 連 則 填 入 0 7

圖 2-4. 二 分 圖 與 LDPC codes 矩 陣 H 的 轉 換 一 個 (n,k) 的 LDPC code,n 代 表 碼 的 長 度 (Codeword),k 代 表 資 料 位 元 (Information Bits) 的 長 度, 碼 率 (code rate) 為 R=k/n 在 一 個 LDPC code 矩 陣 H 中, 行 權 重 (column weight) 與 列 權 重 (row weight) 的 相 同 與 否, 我 們 又 可 以 將 LDPC code 矩 陣 H 矩 陣 分 為 規 則 性 (regular) 與 非 規 則 性 (irregular) 的 結 構 列 權 重 為 一 列 中 1 的 個 數 為 多 少, 行 權 重 為 一 行 中 1 的 個 數 為 多 少, 假 設 H 矩 陣 中 行 權 重 跟 列 權 重 都 固 定, 則 此 H 就 為 規 則 性 的 相 反 的, 都 不 固 定 的 H 矩 陣 為 非 規 則 性 結 構 在 效 能 方 面, 非 規 則 性 的 矩 陣 錯 誤 率 平 緩 之 現 象 會 比 較 晚 出 現, 代 表 錯 誤 率 下 降 的 比 較 多, 但 是 硬 體 設 計 上 也 相 對 的 比 較 複 雜 2.3 低 密 度 同 位 元 檢 查 碼 - 解 碼 在 1962 年,Gallager 除 了 介 紹 LDPC 碼 的 存 在 外, 也 提 出 一 個 最 接 近 Shannon 限 界 結 果 的 解 碼 演 算 法, 稱 為 疊 代 解 碼 演 算 法 (Iterative Decoding Algorithm), 簡 單 來 說,LDPC 的 解 碼 方 式, 是 把 傳 輸 資 料 由 位 元 節 點 端 輸 入, 經 過 一 些 公 式 運 算 後, 再 傳 出 新 的 訊 號 至 檢 查 節 點 端 作 運 算, 之 後 再 回 傳 至 位 元 節 點 端, 重 複 來 回 的 運 算, 直 到 資 料 訊 息 收 斂 不 再 變 化 為 止, 這 就 是 疊 代 解 碼 演 算 法 此 後 的 學 者 根 據 此 演 算 法 也 提 出 眾 多 相 關 的 研 究 解 碼 的 演 算 法 有 很 多 種, 像 是 和 積 演 算 法 (SPA) Log-Domain 8

演 算 法 最 小 和 演 算 法 BP 演 算 法 (Belief propagation decoding algorithm) MPA 演 算 法 (Message passing algorithm) 等 等, 不 管 是 編 碼 上 還 是 解 碼 上 或 者 是 code design, 都 是 有 很 多 人 在 研 究 的, 每 年 的 論 文 數 也 都 不 少 Row(i) 代 表 的 是 由 check nodes 所 形 成 的 集 合,column(j) 代 表 的 是 由 bit nodes 所 形 成 的 集 合, 每 一 個 bit node 由 (0) 2 或 (1) 2 組 成, 每 一 個 check nodes 會 去 蒐 集 與 自 己 連 接 的 bit nodes 的 資 料, 算 看 看 是 否 加 總 為 0, 假 如 為 0, 即 為 正 確, 假 如 不 為 0, 資 料 就 發 生 錯 誤, 就 必 頇 透 過 設 計 演 算 法 去 解 決 以 下 我 們 就 介 紹 MPA 演 算 法 簡 單 來 說 MPA 演 算 法 指 的 就 是 bit nodes 跟 check nodes 會 互 相 幫 忙 解 出 彼 此 所 需 要 的 答 案 Step1: "Row processing",check nodes 會 去 收 集 bit node 的 資 料 後, 回 傳 給 bit node 為 1 或 者 0 ; Step2 :"Column processing",bit nodes 會 去 收 集 check nodes 所 提 供 的 資 料 後, 再 回 傳 給 bit nodes 為 1 或 0 經 過 多 次 的 iteration 後, 得 出 所 需 要 的 解 且 MPA 演 算 法 也 為 平 行 解 碼 的 方 式, 適 合 應 用 在 當 今 高 技 術 的 硬 體 上 Message passing decoding algorithm 下 圖 2-5 為 一 進 行 MPA 演 算 法 前 的 初 始 圖 初 始 : 圖 2-5. MPA 初 始 二 分 圖 9

步 驟 1: Pass message from V to C (Row processing) 步 驟 2: Pass message from C to V (Column processing) 一 次 的 步 驟 1+ 步 驟 2 稱 為 一 個 iteration, 經 過 多 次 的 iteration 後, 就 會 得 出 所 需 要 的 解 V to C and Row processing 步 驟 1: 如 下 圖 2-6 所 示,pass message from V to C,C 1 會 根 據 他 收 到 V 1 V 2 V 3 的 資 訊, 來 回 傳 給 V 4 所 需 要 的 正 確 的 值 1+1+0+?=0,so?=0 圖 2-6. Row processing 示 意 圖 10

C to V and column processing 步 驟 2: pass message from C to V processing 如 下 圖 2-7 所 表 示,column processing 會 作 多 數 決 的 投 票 (majority vote),v i 會 去 收 集 check nodes 所 提 供 的 資 料 後, 再 回 傳 給 V i 正 確 的 值 圖 2-7. column processing 示 意 圖 經 過 多 次 的 檢 查 及 運 算 後, 即 解 碼 為 正 確 的 值, 利 用 彼 此 之 間 消 息 互 相 傳 遞 的 機 制 來 達 到 解 碼 效 果 所 以 說, 假 設 設 計 出 來 的 LDPC 碼 的 最 小 周 長 可 以 很 大 的 話, 表 示 能 夠 透 過 彼 此 傳 遞 訊 息 的 資 料 也 越 多, 資 源 比 較 多, 代 表 透 過 傳 遞 訊 息 得 出 正 確 的 解 的 機 會 也 越 大 ; 相 反 的, 假 如 最 小 周 長 很 小, 能 夠 透 過 彼 此 傳 遞 訊 息 的 資 料 也 越 少, 資 源 比 較 少 表 示 能 透 過 傳 遞 訊 息 得 出 正 確 的 解 的 機 會 也 越 小, 所 以 我 們 希 望 能 夠 設 計 一 個 較 大 的 最 小 周 長 的 LDPC 碼 11

三 PS-LDPC code 3.1 分 割 及 位 移 設 計 我 們 可 以 從 二 分 圖 裡 去 建 構 一 個 低 密 度 同 位 元 檢 查 碼 令 V c 為 一 個 包 含 所 有 m 個 檢 查 節 點 (check nodes) 的 集 合 以 及 V b 為 一 個 包 含 所 有 n 個 位 元 節 點 (bit nodes) 的 集 合 接 著 取 一 個 大 小 (size) 同 樣 為 p 的 值 將 V c 分 割 成 N c 個 互 斥 (disjoint) 的 子 集 合, 故 m=n c p,p 屬 於 正 整 數 相 同 的, 用 同 樣 的 p 值, 將 V b 分 割 成 N b 個 互 斥 的 子 集 合, 故 n=n b p,p 屬 於 正 整 數 這 裡 要 求 N c j 且 N b k (j 為 位 元 節 點 的 權 重,k 為 檢 查 節 點 的 權 重 ), 二 分 圖 裡 的 每 一 個 子 集 合 裡 的 元 素 分 別 的 將 它 們 編 上 索 引 (0 至 p-1) 同 樣 的 也 將 V c 裡 的 每 個 子 集 合 編 上 索 引 (1 至 N c ) 及 V b 裡 的 每 個 子 集 合 編 上 索 引 (1 至 N b ) 我 們 命 名 參 數 p 為 每 個 子 集 合 的 基 數 (cardinality) 當 下 列 兩 點 成 立 時, 我 們 稱 一 個 檢 查 節 點 子 集 合 A 連 到 一 個 位 元 節 點 子 集 合 B: (1) 子 集 合 A 裡 的 p 個 檢 查 節 點, 每 一 個 檢 查 節 點 都 有 連 到 子 集 合 B 裡 面 的 位 元 節 點 (2) 子 集 合 A 裡 不 同 的 檢 查 節 點 就 必 頇 連 到 在 子 集 合 B 中 不 同 的 位 元 節 點 因 此, 兩 個 子 集 合 之 間 的 點 建 立 成 兩 個 子 集 合 連 結 的 關 係 是 一 對 一 的 為 了 去 建 構 一 個 能 夠 使 檢 查 節 點 權 重 k 和 位 元 節 點 權 重 j 一 樣 的 規 則 性 低 密 度 同 位 元 檢 查 碼, 我 們 讓 每 一 個 檢 查 節 點 的 子 集 合 連 到 k 個 位 元 節 點 子 集 合 並 且 每 一 個 位 元 節 點 子 集 合 連 到 j 個 檢 查 節 點 子 集 合 接 著 再 更 進 一 步 的 在 加 入 下 列 限 制 : 每 一 個 檢 查 節 點, 在 檢 查 節 點 子 集 合 裡 的 第 α 的 位 置, 編 上 索 引 為 X c, 相 連 到 在 位 元 節 點 子 集 合 裡 的 p p 第 β 的 位 置, 編 上 索 引 為 X b, 也 就 是 X b =X c S α,β,0 S α,β p-1 且 表 示 為 除 以 p 取 餘 數 做 加 法 (modulo-p addition) 故 用 以 上 這 樣 的 方 法 定 義 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 (PS-LDPC codes) 圖 3-1 表 示 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 的 二 分 圖 圖 中 有 由 位 元 節 點 形 成 的 6 個 子 集 合 並 且 能 夠 被 檢 查 節 點 相 連, 但 每 一 個 檢 查 節 點 只 能 剛 好 12

被 3 個 位 元 節 點 連 結 圖 3-2 為 圖 3-1 二 分 圖 轉 換 成 矩 陣 的 示 意 圖, 每 個 區 塊 由 p p 的 單 位 矩 陣 組 成, 並 且 會 有 位 移 的 資 訊 圖 3-1. 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 的 二 分 圖 圖 3-2. 二 分 圖 轉 換 的 矩 陣 圖 參 數 定 義 :S α,β,1 α N c,1 β N b, 上 數 的 定 義 就 稱 為 位 移 (shifts) 用 一 樣 位 移 S α,β 的 值 做 檢 查 節 點 裡 同 樣 第 α 個 子 集 合 裡 的 檢 查 節 點 去 連 接 位 元 節 點 裡 同 樣 為 第 β 個 子 集 合 裡 的 位 元 節 點 挑 選 在 N c N b 矩 陣 裡 所 有 的 S α,β 值 之 後, 把 它 稱 為 位 移 矩 陣 (shift matrix) S=[S α,β ] S 中 的 第 α 列 儲 存 與 檢 查 節 點 的 第 α 個 相 連 的 子 集 合 之 位 13

移 值 ;S 中 的 第 β 行 儲 存 與 位 元 節 點 的 第 β 個 相 連 的 子 集 合 之 位 移 值 因 此, 在 S 中 列 的 對 外 連 結 個 數 α, 行 的 對 外 連 結 各 數 β, 就 是 決 定 第 α 檢 查 節 點 子 集 合 如 何 去 連 接 第 β 個 子 集 合 後 形 成 的 S α,β 假 如 在 第 α 個 檢 查 節 點 子 集 合 與 第 β 個 位 元 節 點 子 集 合 沒 有 互 相 連 結, 表 示 他 沒 有 對 外 連 結, 在 位 移 矩 陣 S 中 的 入 口 (entry) 就 以 * 來 表 示 每 一 個 檢 查 節 點 子 集 合 只 有 連 到 k 個 位 元 子 集 合, 而 且 總 合 又 為 N c 個 檢 查 節 點 子 集 合, 故 只 有 存 在 k N c 個 非 * 位 移 值 圖 3-3 為 舉 例 圖, 用 群 與 群 之 間 的 連 接 方 式 算 出 位 移 值 圖 3-4 為 圖 3-1 二 分 圖 所 相 對 應 的 位 移 矩 陣 S 圖 3-3. 試 算 位 移 值 圖 3-4. 二 分 圖 所 相 對 應 的 位 移 矩 陣 S 14

從 以 上 的 建 構 方 式 可 得 出 碼 率, 在 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 裡, 行 權 重 j 及 列 權 重 k 已 經 不 受 限 制 所 以 我 們 可 以 設 計 一 個 有 任 意 行 權 重 j 及 列 權 重 k 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 在 一 個 規 則 性 的 碼 中, 假 如 少 數 的 線 性 相 依 同 位 元 檢 查 方 程 式 忽 略 不 做, 則 碼 率 ρ=1-(j/k) 因 此, 我 們 可 以 調 整 j 與 k 的 值 產 生 想 要 的 碼 率 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 舉 例 來 說, 假 如 想 要 一 個 ρ=8/9 且 行 權 重 為 3 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼, 就 可 以 調 整 設 定 j=3 及 k=27 15

3.2 迴 圈 與 位 移 的 關 係 因 為 小 的 迴 圈 會 對 低 密 度 同 位 元 檢 查 碼 的 解 碼 有 害, 所 以 必 頇 將 它 消 除 首 先 用 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 的 二 分 圖 找 出 在 位 移 矩 陣 S 中 與 迴 圈 有 相 關 的 封 閉 路 徑 (closed path) 定 理 1(2t 迴 圈 )[10]: 若 且 為 若 在 位 移 矩 陣 S 中 有 任 一 條 長 度 為 2t 的 封 閉 路 徑 且 擁 有 2t 個 轉 角 (corner) S S 1,.. 1 2t, 2 t 違 反 迴 圈 條 件 (Cycle Condition) : p p p 2t ( i 1 1) S S S... S S... i 1 i, i 1, 1 2, 2 2i 1, 2i 1 2i, S S 0 ( p 表 示 為 除 以 p 2 i 2t 1, 2t 1 2t, 2t 取 餘 數 做 減 法 : modulo-p subtraction), 則 此 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 的 二 分 圖 裡 就 不 包 含 2t 迴 圈 此 定 理 1 之 證 明 請 參 考 文 獻 [10] 舉 例 來 說, 圖 3-5(b) 的 6 迴 圈, 它 是 一 條 由 彼 此 相 關 的 6 個 轉 角 S 2,5 S 3,5 S 3,4 S 4,4 S 4,6 和 S 2,6 所 組 成 且 長 度 為 6 的 封 閉 路 徑, 封 閉 路 徑 裡 彼 此 關 係 是 連 續 不 斷 的, 就 像 圖 3-5(a) 裡 右 下 的 一 個 封 閉 路 徑 在 S 中 擁 有 2t 個 轉 角 S S S 1,, 1 2,.. 2 2t, 2 t p p 的 任 一 條 封 閉 迴 圈, 假 如 不 符 合 迴 圈 條 件 定 理 的 話, 則 此 二 分 圖 不 會 有 2t 迴 圈 存 在 換 句 話 說, 圖 3-5 裡 的 封 閉 路 徑 S 2,5 -S 2,6 +S 4,6 -S 4,4 +S 3,4 -S 3,5 算 出 來 的 總 位 移 值 只 要 能 讓 它 不 為 0 的 話, 則 在 H 裡 就 能 避 免 6 迴 圈 的 出 現 (a) 16

(b) 圖 3-5. (a): S 中 的 封 閉 路 徑 (b): 在 二 分 圖 中 的 6 迴 圈 3.3 最 小 周 長 的 邊 界 定 理 1 表 示 迴 圈 條 件 可 以 預 防 2t 迴 圈, 可 是 定 理 1 卻 沒 有 告 訴 我 們 是 否 可 以 找 到 所 有 長 度 為 2t 且 違 反 迴 圈 條 件 的 封 閉 路 徑 形 成 的 位 移 矩 陣 S 可 以 從 下 列 定 理 2[10] 與 定 理 3[10] 知 道 答 案 A. 最 小 周 長 之 上 界 (Upper Bound on Girth) 定 理 2 [10] : 每 一 個 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 是 由 擁 有 最 小 周 長 g 2(L(C 1 )+L(C 2 )-L(C 1 C 2 )) 的 位 移 矩 陣 S 建 構 而 來 的, 其 C 1 和 C 2 是 在 S 中 的 任 意 兩 條 封 閉 路 徑 且 C 1 C 2 ø 在 [10] 有 定 理 2 之 證 明 B. 達 成 最 小 周 長 的 邊 界 (Achieving the Girth Bound) 以 下 為 表 示 定 理 2 中 最 小 周 長 g 之 上 界 是 可 以 達 成 的 定 理 3[10] : 基 於 位 移 矩 陣 S, 我 們 可 以 建 構 一 個 任 意 最 小 周 長 g 2min C1,C2 (L(C 1 )+L(C 2 )-L(C 1 C 2 )) 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼, 其 C 1 和 C 2 是 在 S 中 的 任 意 兩 條 封 閉 路 徑 且 C 1 C 2 ø 在 [10] 有 定 理 3 之 證 明 且 p 的 限 制 [10] 為 17

p [(j-1)(k-1)] (g/2-1) (j k-j-k) (3.1) 藉 由 定 理 3, 可 以 導 出 一 個 結 論 結 論 1: 從 一 個 最 小 周 長 為 g 的 小 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼, 可 以 建 構 出 一 個 任 意 最 小 周 長 為 g c 3g 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 在 [10] 有 結 論 1 之 證 明 但 是, 在 文 獻 [10] 作 者 提 出 的 p 0 =607 最 小 周 長 放 大 到 14 的 實 驗 與 結 論 1 作 比 較, 有 些 令 人 質 疑 的 地 方 如 下 : 1. 最 小 周 長 從 6 放 大 到 14, 並 沒 有 將 原 本 的 最 小 周 長 為 g 的 S, 經 過 實 驗 後 達 到 3g 2. 從 p 的 限 制 式 (1) 中, 作 者 的 j=3 k=4 算 出 來 的 p 值 應 該 是 9332, 是 一 個 很 大 的 值, 然 而 Lu 發 表 的 結 果 只 有 607 理 論 和 實 驗 結 果 有 存 在 差 距 會 讓 人 覺 得 也 許 可 以 把 原 本 最 小 周 長 為 g 的 S, 經 過 實 驗 後 變 成 超 過 3g 3. 原 作 者 提 出 的 最 小 周 長 邊 界 為 上 界, 最 多 就 是 放 大 3 倍, 但 在 實 作 上 的 時 候, 可 能 會 比 較 不 理 想, 且 不 夠 嚴 謹, 如 果 能 夠 給 下 界 的 話, 譬 如 最 小 周 長 從 g 放 大 成 3g 時, 需 要 的 p 值 為 一 個 下 界 (p min ), 我 想 這 樣 對 於 實 作 上, 才 會 有 最 大 的 幫 助 以 上, 我 們 發 現 實 驗 跟 定 理 的 差 距 有 點 大, 所 以 我 們 透 過 自 己 的 實 驗 來 驗 證 最 小 周 長 邊 界 條 件 是 否 嚴 謹 3.4 任 意 的 最 小 周 長 藉 由 結 論 1[10], 可 以 將 一 個 設 計 有 最 小 周 長 為 3g 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼, 這 樣 困 難 的 問 題 轉 換 成 設 計 一 個 比 較 簡 單 且 最 小 周 長 只 有 g 的 低 密 度 同 位 元 檢 查 碼 假 如 最 小 周 長 為 g 的 分 割 及 低 密 度 同 位 元 檢 查 碼 還 是 很 難 建 構 出 來, 我 們 還 可 以 再 進 一 步 將 最 小 周 長 的 需 求 減 少 為 g /3 用 這 樣 的 方 法, 最 後 就 可 以 將 所 設 計 的 碼 的 最 小 周 長 減 少 為 g 12, 藉 由 結 論 1, 我 們 可 以 根 據 一 個 j k 且 全 為 1 的 矩 陣 去 設 計 出 行 權 重 為 j, 列 權 重 為 k, 且 最 小 周 長 g 12 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 18

以 下 為 藉 由 結 論 1, 基 於 最 小 周 長 為 g 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼, 建 構 最 小 周 長 為 g c 3g 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 之 演 算 法 1[10] 與 演 算 法 2[10] 演 算 法 1: 從 最 小 周 長 為 g 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼, 建 構 最 小 周 長 為 g c 3g 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼, 下 圖 3-6 為 Lu 的 演 算 法 1 之 pseudo code, 說 明 如 何 建 構 一 個 S 矩 陣 (g c : construct g) 圖 3-6. 演 算 法 1 的 pseudo code[10] 19

下 圖 3-7 為 演 算 法 1 之 流 程 圖,S 矩 陣 中 每 個 欄 位 產 生 的 位 移 值, 透 過 迴 圈 條 件 下 去 檢 查, 沒 有 達 成 迴 圈 條 件, 則 此 位 移 值 就 為 可 以 用 的, 直 到 每 個 欄 位 的 值 都 產 生 好 為 止, 即 建 構 出 一 個 S 矩 陣 圖 3-7. 演 算 法 1 的 流 程 圖 20

演 算 法 1: 初 始 化 : 令 H 為 有 最 小 周 長 g 之 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 的 同 位 元 檢 查 矩 陣 (parity-check matrix) 設 H 為 位 移 矩 陣 S 的 關 聯 矩 陣 (incidence matrix) S 中 的 欄 位 除 了 *, 剩 下 的 k N c 個 欄 位 為 未 確 定 的 值 用 S 1,S 2.,S k Nc 來 表 示 這 些 k N c 個 欄 位 儲 存 的 方 式 是 由 左 至 右, 逐 列 運 作 1. r=1 2. 步 驟 一 :S r 值 為 亂 數 產 生 (0 S r <p) 3. for (g/2 t g c /2-1) 4. for (S 中 的 每 一 條 長 度 為 2t 的 封 閉 路 徑,S r 有 參 5. 與 到 哪 一 條 封 閉 路 徑, 則 此 條 封 閉 迴 圈 的 起 始 值 6. 至 結 束 S r, 做 迴 圈 條 件 i 1 (-1)i+1 S αi,βi, 是 否 為 0) 7. 把 會 使 得 迴 圈 條 件 成 立 的 k 值 加 入 禁 止 位 移 陣 列 8. (Prohibit_shift array 裡 ) 9. k=k+1; 10. end for 11. while(s r 值 不 為 Prohibit_shift array 裡 的 值 ) 12. 則 迴 圈 條 件 不 成 立, 將 S r 填 入 S 裡 13. end while 14. 將 Prohibit_shift array 清 除 15. end for 16. if (r=k N c ) 17. 到 步 驟 二 18. else 19. r=r+1, 回 到 步 驟 一 20. 步 驟 二 : 基 於 結 果 S 矩 陣 建 立 分 割 及 21. 位 移 低 密 度 同 位 元 檢 查 碼 2t 21

演 算 法 2: 建 構 一 個 任 意 最 小 周 長 g 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼, 下 圖 3-6 為 Lu 的 演 算 法 2 之 pseudo code, 說 明 只 要 透 過 演 算 法 2, 就 可 以 得 到 任 意 最 小 周 長 的 PS-LDPC codes 圖 3-8. 演 算 法 2 的 pseudo code[10] 22

下 圖 3-9 為 演 算 法 2 的 流 程 圖, 演 算 法 2 是 把 演 算 法 1 包 起 來, 說 明 除 了 能 夠 建 構 任 意 最 小 周 長 的 PS-LDPC codes 之 外, 在 設 計 上 的 最 小 周 長 假 如 太 大, 可 以 透 過 2 ( g t 1) / 6, 則 可 以 問 題 簡 化 成 最 小 周 長 設 計 到 12 就 好 g t 12 2 ( 1) / g t 6 2 ( 1) / g t 6 2 ( 1) / g t 6 圖 3-9. 演 算 法 2 的 流 程 圖 如 此 一 來, 透 過 Lu 的 演 算 法 1 及 演 算 法 2 就 可 以 建 構 任 意 最 小 周 長 的 PS-LDPC codes 了 23

四 針 對 分 割 及 位 移 LDPC code 之 改 進 在 Lu 的 方 法 中, 經 過 3.3 我 們 自 己 的 實 驗 後, 出 來 的 結 果 的 確 是 有 讓 人 質 疑 的 地 方, 實 驗 和 定 理 是 有 點 差 距 的, 這 也 表 示 應 該 是 可 以 做 的 更 好 才 對, 也 就 是 可 以 將 矩 陣 的 最 小 周 長 放 的 更 大 接 下 來 我 們 就 提 出 本 論 文 的 改 進 方 法, 再 加 以 證 實 可 以 比 Lu 的 方 法 做 的 更 好 4.1 已 知 演 算 法 之 缺 點 透 過 3.4 的 演 算 法 1 與 演 算 法 2, 我 們 可 以 經 由 放 大 p 倍 後, 產 生 一 個 比 原 本 最 小 周 長 只 有 g 的 位 移 矩 陣 S, 放 大 成 最 小 周 長 為 3g 的 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 舉 例 來 說, 假 如 有 一 個 最 小 周 長 為 4 的 位 移 矩 陣 S, 就 可 以 透 過 以 上 的 方 法 放 大 p 倍 得 到 一 個 最 小 周 長 為 12 的 H 0 但 是 p 的 大 小 與 周 長 邊 界 條 件 是 否 嚴 謹 是 我 們 可 以 探 討 的 地 方 在 Lu 的 方 法 中 [10], 告 訴 我 們 經 過 他 的 演 算 法 就 一 定 能 將 最 小 周 長 最 多 放 大 3 倍, 可 是 放 大 倍 率 的 值 確 實 是 讓 人 質 疑 的, 不 夠 嚴 謹, 而 且 Lu 的 實 驗 裡, 最 小 周 長 從 6 放 大 到 最 小 周 長 14, 所 需 要 的 p 值 與 限 制 式 (3.1) 算 出 來 的 值 相 差 太 大, 造 成 碼 的 長 度 太 冗 長, 假 如 能 將 碼 的 長 度 減 少, 又 能 將 最 小 周 長 放 大, 這 樣 才 是 最 好 的 在 3.3 章 節 中 我 們 有 提 出 質 疑 的 地 方, 接 下 來 我 們 會 提 供 一 個 改 進 的 方 法 4.2 改 進 方 法 利 用 慢 慢 增 加 p 的 大 小, 來 實 驗 長 度 相 同 的 碼, 最 小 周 長 能 放 大 到 多 少, 再 來 與 Lu 的 方 法 做 比 較 在 我 們 的 方 法 中, 首 先, 用 的 演 算 法 1 跟 Lu 作 者 是 一 樣 的, 但 是 為 了 我 們 能 夠 利 用 慢 慢 增 加 p 值 來 探 討 當 p 值 增 加 到 多 少 時, 此 時 的 矩 陣 最 小 周 長 能 放 大 到 多 少, 所 以 我 們 必 頇 先 建 好 能 夠 再 矩 陣 中 找 迴 圈 的 工 具 在 本 論 文 的 實 驗 裡, 我 們 分 別 建 了 24

找 能 夠 在 矩 陣 中 找 到 4- 迴 圈 6- 迴 圈 8- 迴 圈 10- 迴 圈 12- 迴 圈 14- 迴 圈 16- 迴 圈, 當 然 也 不 一 定 只 能 夠 找 到 16- 迴 圈, 這 隻 程 式 是 可 以 繼 續 發 展 下 去 的, 只 是 因 為 要 跟 Lu 作 者 的 方 法 下 去 做 比 較 而 已 而 且 在 做 迴 圈 條 件 的 時 候, 譬 如 我 們 現 在 想 要 一 個 不 包 含 10- 迴 圈 以 下 的 矩 陣 H, 也 就 是 一 個 最 小 周 長 為 12 的 矩 陣, 此 時 的 迴 圈 條 件 裡 就 必 頇 同 時 加 入 4- 迴 圈 6- 迴 圈 8- 迴 圈 10- 迴 圈, 有 了 這 項 找 迴 圈 的 工 具 就 讓 我 們 的 實 驗 能 夠 更 順 利 執 行 下 面 我 們 就 來 說 明 如 何 建 立 在 矩 陣 中 分 別 尋 找 4- 迴 圈 6- 迴 圈 8- 迴 圈 10- 迴 圈 等 等 圖 4-1. 建 樹 的 舉 例 圖 步 驟 1. 在 一 個 矩 陣 H 中, 由 列 元 素 C 1 C 2 C x ( 檢 查 節 點 ) 及 行 元 素 B 1 B 2 B y ( 位 元 節 點 ) 組 成 因 為 有 1~y 個 位 元 節 點, 所 以 可 以 建 出 y 棵 樹, 樹 根 分 別 為 B 1 B 2 B y 步 驟 2. 由 步 驟 1 建 出 樹 根 後, 接 著 建 出 與 每 個 樹 根 有 相 連 的 第 一 層, 舉 例 來 說, 如 上 圖 十 三 在 矩 陣 中 B 1 這 行 可 以 找 到 C 1 C 3 C 5 的 值 為 1, 就 代 表 這 三 個 檢 查 結 點 與 B 1 樹 根 有 相 連, 這 三 個 檢 查 結 點 為 這 一 棵 樹 的 第 一 層 步 驟 3. 建 出 每 一 棵 樹 的 第 二 層 資 料, 乘 步 驟 2 的 例 子 說 明, 從 B 1 中 找 到 了 C 1 C 3 C 5 後, 再 分 別 從 C 1 C 3 C 5 這 三 列 找 到 欄 位 為 1 的 位 元 節 點, 且 找 到 的 位 元 節 點 不 能 跟 樹 根 重 複, 並 且 將 第 二 層 的 位 元 節 點 是 由 第 一 層 的 哪 一 個 檢 查 節 點 相 連 的 位 置 儲 存 步 驟 4. 建 出 每 一 棵 樹 的 三 層 資 料, 且 找 到 的 檢 查 節 點 不 會 跟 第 一 層 的 檢 查 結 點 重 覆 一 樣 也 要 將 第 三 層 檢 查 節 點 與 上 一 層 的 哪 一 個 位 元 節 點 相 連 的 位 置 儲 存 25

步 驟 5. 建 了 三 層 的 資 料 ( 不 包 含 樹 根 ) 後, 就 可 以 得 知 矩 陣 裡 所 有 6- 迴 圈 的 資 料 假 如 要 找 4- 迴 圈 的 資 料, 樹 建 到 第 二 層 即 可 ; 如 果 要 找 到 8- 迴 圈 的 資 料, 樹 就 必 頇 建 到 第 四 層, 以 此 類 推 如 此, 就 可 以 把 找 迴 圈 的 程 式 套 用 在 Lu 作 者 演 算 法 1 的 迴 圈 條 件 裡 面 了, 譬 如 想 要 最 小 周 長 為 8 的 矩 陣, 就 把 4- 迴 圈 及 6- 迴 圈 的 資 料 都 找 出 來, 然 後 再 加 以 避 免 改 進 的 方 法 : 修 改 Lu 的 演 算 法 2, 重 點 在 於 利 用 慢 慢 放 大 p 的 值, 再 去 觀 察 是 否 能 減 少 碼 的 長 度 而 能 得 到 較 大 的 最 小 周 長 目 的 : 如 果 產 生 出 來 的 矩 陣 最 小 周 長 跟 Lu 的 一 樣, 但 是 長 度 比 較 小 ; 或 者 是 長 度 一 樣, 但 是 最 小 周 長 能 變 大, 則 方 法 成 功 步 驟 1: 利 用 演 算 法 1 產 生 出 來 的 H 矩 陣, 當 作 S 步 驟 2: 在 S 矩 陣 中 給 個 初 始 p 值, p 最 小 從 4 開 始, 放 大 p 倍 得 出 來 的 矩 陣 H, 再 用 找 迴 圈 (4- 迴 圈 6- 迴 圈 8- 迴 圈 10- 迴 圈 12- 迴 圈 14- 迴 圈 16- 迴 圈 等 等 ) 的 程 式, 去 檢 測 最 小 周 長 已 經 放 大 到 幾 倍 步 驟 3: 假 如 想 達 到 的 最 小 周 長 沒 辦 法 達 成, 則 p=p+1, 直 到 產 生 出 來 為 止 4.3 實 驗 結 果 與 比 較 [ 實 驗 1] 用 Lu 的 方 法 與 我 們 自 己 提 出 的 方 法 來 做 比 較 首 先 建 一 個 行 權 重 j=3 列 權 重 k=4 p 1 =5 且 避 免 掉 4 迴 圈 的 S 矩 陣, 如 圖 4-2 圖 4-2. 避 免 掉 4 迴 圈 的 S 矩 陣 26

基 於 S, 可 以 建 構 出 一 個 最 小 周 長 為 6 碼 率 為 0.25 的 15 20 同 位 元 檢 查 矩 陣 H 1 ( 方 法 A) 使 用 Lu 的 方 法, 將 最 小 周 長 為 6 的 H 1 矩 陣 放 大 到 最 小 周 長 為 14 的 矩 陣 H 0 (n=12140 j=3 k=4), 需 要 的 最 小 p 0 值 為 607 如 下 圖 4-3 為 最 小 周 長 為 14 的 S 矩 陣 ( 位 移 值 = -1 代 表 群 與 群 之 間 無 相 連 ) 圖 4-3. 最 小 周 長 為 14 的 S 矩 陣 ( 方 法 B) 用 我 們 自 己 的 方 法 將 最 小 周 長 為 6 的 H 1 矩 陣 放 大 到 最 小 周 長 為 14 的 矩 陣 H 0, 需 要 的 最 小 p 0 值 只 要 150 不 僅 如 此, 放 大 到 最 小 周 長 為 16 時, 需 要 的 最 小 p 0 值 也 只 需 要 520, 如 此, 碼 的 長 度 會 變 短, 效 能 也 會 提 升 下 表 4-1 為 用 我 們 的 方 法, 矩 陣 放 大 到 最 小 周 長 為 多 少 時, 需 要 的 最 小 p 值 (p min ) 為 多 少 下 圖 4-4 為 最 小 周 長 為 16 的 S 矩 陣 27

圖 4-4. 最 小 周 長 為 16 的 S 矩 陣 表 4-1. 達 到 最 小 周 長 為 g 所 需 的 最 小 p 值 g 8 10 12 14 16 18 p min 4 15 44 150 520 1570 從 實 驗 1 結 果, 可 以 發 現 用 相 同 的 S 建 出 來 H 0, 我 們 的 方 法 建 出 來 的 最 小 周 長 的 確 是 比 Lu 的 方 法 還 要 大, 也 可 以 說 固 定 想 達 到 的 最 小 周 長 為 多 少 時, 我 們 的 方 法 建 出 來 的 碼 的 長 度, 會 比 Lu 的 方 法 建 出 來 的 碼 的 長 度 短, 所 以 Lu 的 確 沒 有 做 到 最 好 [ 實 驗 2] 初 始 矩 陣 的 選 擇 : 根 據 我 們 提 出 的 方 法, 實 驗 用 最 小 周 長 為 6 作 為 初 始 矩 陣 與 較 大 的 最 小 周 長 矩 陣 作 為 初 始 矩 陣, 所 得 到 的 實 驗 結 果 做 比 較 ( 方 法 1) 初 始 用 最 小 周 長 為 6 的 15 20(j=3 k=4)h, 如 下 圖 4-5, 經 由 我 們 的 方 法, 實 驗 的 結 果 為 下 表 4-2 ( 方 法 2) 將 下 圖 4_5 的 H, 經 由 我 們 得 方 法,p 0 =4, 可 以 得 到 最 小 周 長 為 8 的 60 80 H 當 作 初 始 矩 陣, 實 驗 的 結 果 為 下 表 4-3 28

圖 4-5. 最 小 周 長 為 6 的 矩 陣 H 表 4-2. [ 實 驗 2] 方 法 1 的 結 果 g 8 10 12 14 16 18 p min 4 14 42 142 432 1400 表 4-3. [ 實 驗 2] 方 法 2 的 結 果 g 10 12 14 16 18 p min 6 20 66 263 1170 備 註 : 表 4-3 的 p min 值 必 頇 4 才 能 與 表 4-2 作 比 較 從 實 驗 2 可 以 發 現, 用 較 小 的 最 小 周 長 為 6 的 S 作 為 初 始 矩 陣, 和 用 較 大 的 最 小 周 長 為 8 的 S 作 為 初 始 矩 陣, 當 H 的 長 度 n 一 樣 的 時 候, 發 現 用 較 小 的 最 小 周 長 S 作 為 初 始 矩 陣 得 到 的 H 的 最 小 周 長 會 比 較 大, 也 可 以 說 想 要 達 成 一 樣 的 最 小 周 長 的 29

時 候, 初 始 矩 陣 的 最 小 周 長 小 一 點 可 能 會 比 較 好 舉 例 來 說, 從 實 驗 2 得 到 的 表 4-2 及 4-3 中, 最 小 周 長 從 6 直 接 放 大 到 14 所 需 要 的 p 值 最 小 為 142, 相 對 於 最 小 周 長 從 6 放 大 到 8 再 放 大 到 14 所 需 要 的 p 值 為 66 4=264 所 以 在 這 些 特 定 的 條 件 下, 這 樣 的 方 法 經 過 我 們 實 驗 2 所 得 出 來 的 結 果, 也 許 矩 陣 的 最 小 周 長 利 用 分 段 式 放 大 的 方 法, 不 一 定 會 比 較 好 也 說 明 了 初 始 矩 陣 的 選 擇, 的 確 是 有 可 能 是 個 影 響 很 大 的 因 素, 但 是 能 不 能 證 明 使 用 較 小 的 最 小 周 長 當 成 初 始 矩 陣 來 放 大 會 比 較 好, 這 是 需 要 再 經 過 非 常 多 次 實 驗 的 30

五 錯 誤 率 之 模 擬 與 分 析 模 擬 環 境 : 利 用 Lu[10] 的 演 算 法 1 及 本 論 文 改 進 的 演 算 法, 使 用 的 程 式 語 言 工 具 為 MATLAB, 將 矩 陣 H 建 出 來 後, 跑 模 擬 的 工 具 為 C 語 言, 位 元 錯 誤 率 (bit error rate: ber) 的 效 能 比 較 是 在 高 斯 通 道 (Gaussian channels) 上 進 行 用 我 們 提 出 來 的 演 算 法 將 圖 4-5 的 (15 20) 矩 陣 當 作 我 們 初 始 的 S 矩 陣, 放 大 的 倍 率 p 為 142, 去 建 構 一 個 行 權 重 為 4 列 權 重 為 3 碼 率 為 0.25 且 最 小 周 長 為 14 的 H(2130 2840) 比 較 的 對 象 為 Random LDPC code, 行 權 重 為 4 列 權 重 為 3 最 小 周 長 為 6, 長 度 一 樣 為 2130 2840 如 下 圖 5-1, 為 我 們 的 模 擬 1 圖 5-1. 模 擬 1 在 模 擬 1 中, 因 為 我 們 選 擇 碼 率 較 低 的 矩 陣, 矩 陣 中 也 許 會 有 比 較 多 的 小 迴 圈, 導 致 在 模 擬 的 進 行 上 需 要 花 比 較 久 的 時 間 由 於 模 擬 的 環 境 是 用 軟 體 模 擬, 效 率 沒 有 用 硬 體 模 擬 來 的 好, 如 果 是 用 硬 體 來 執 行 模 擬 的 話, 也 許 模 擬 執 行 上 速 度 就 會 比 用 軟 31

體 快 了 更 多, 所 以 碼 率 較 低 的 模 擬 結 果, 可 能 為 無 法 預 期 的, 因 為 當 SNR 值 越 高 的 時 候, 錯 誤 率 會 用 來 越 低, 在 模 擬 中 就 會 花 越 多 的 時 間 去 找 出 發 生 錯 誤 的 地 方 但 是 已 經 有 學 者 提 出 一 個 事 實, 在 同 樣 的 碼 的 長 度 下, 只 要 最 小 周 長 比 較 大, 則 跑 出 來 的 模 擬 結 果 錯 誤 率 一 定 會 比 較 低 在 第 二 個 模 擬 中, 我 們 則 選 擇 碼 率 較 高 的 矩 陣 來 跑 模 擬, 如 下 圖 5-2 圖 5-2. 模 擬 2 模 擬 2 中, 同 樣 的 用 我 們 提 出 來 的 演 算 法 加 上 Lu 方 法 中 的 演 算 法 1, 將 行 權 重 為 6 列 權 重 為 2 最 小 周 長 為 6 且 碼 率 為 0.67 的 矩 陣 H(12 36), 當 作 我 們 初 始 的 S 矩 陣, 放 大 的 倍 率 p 為 50, 去 建 構 一 個 最 小 周 長 為 12 行 權 重 為 6 列 權 重 為 2 的 矩 陣 H(600 1800) 比 較 的 對 象 為 Random LDPC code, 行 權 重 為 6 列 權 重 為 2 最 小 周 長 為 6, 矩 陣 大 小 一 樣 為 600 1800 的 H 在 模 擬 2 中, 由 於 我 們 選 擇 是 一 個 碼 率 較 高 的 矩 陣, 矩 陣 中 的 小 迴 圈 也 許 就 會 比 碼 率 較 低 的 矩 陣 來 的 少, 在 SNR 值 較 高 的 情 況 下, 就 會 比 較 容 易 找 到 發 生 錯 誤 的 地 方, 因 此 從 模 擬 圖 中 可 以 明 顯 的 看 出 來 我 32

們 用 改 進 後 的 方 法 建 出 來 的 矩 陣, 錯 誤 率 的 確 是 可 以 比 Random LDPC code 降 的 更 低, 因 為 在 SNR 值 較 高 的 情 況 下,Random LDPC code 的 錯 誤 率 似 乎 已 經 沒 辦 法 在 持 續 下 降 的 很 多 了, 但 是 我 們 的 方 法 看 的 出 來 錯 誤 率 還 是 在 持 續 下 降 中, 的 確 是 縮 小 了 錯 誤 率 平 緩 的 現 象 33

六 結 論 低 密 度 同 位 元 檢 查 碼 近 年 來 已 經 應 用 到 通 訊 廣 播 及 HDD 硬 碟 等 領 域, 如 今 已 成 為 業 界 注 目 的 焦 點 本 篇 論 文 採 用 的 架 構 為 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼, 針 對 Lu 的 方 法 加 以 改 進 我 們 透 過 實 驗 來 最 佳 化 分 割 及 位 移 低 密 度 同 位 元 檢 查 碼 的 演 算 法 中 放 大 倍 率 的 選 擇, 在 固 定 長 度 下 的 低 密 度 同 位 元 檢 查 碼 可 以 將 最 小 周 長 放 得 更 大, 在 固 定 的 最 小 周 長 限 制 下 可 以 減 少 所 需 的 碼 的 長 度 和 文 獻 中 的 方 法 比 較, 除 了 保 有 原 有 演 算 法 的 優 點, 可 以 建 構 任 意 的 行 權 重 列 權 重 及 最 小 周 長 的 矩 陣 外, 本 論 文 的 貢 獻 為 證 明 了 要 達 到 目 標 的 最 小 周 長 而 放 大 的 倍 率 可 以 縮 小 很 多, 藉 此 可 大 幅 降 低 硬 體 所 需 的 複 雜 度 及 成 本, 且 經 過 我 們 改 進 的 方 法 後, 的 確 能 證 實 放 大 的 倍 率 可 以 縮 小 很 多 在 實 驗 二 裡, 我 們 提 出 了 初 始 矩 陣 的 選 擇 這 個 議 題, 實 驗 二 的 結 果 是 初 始 矩 陣 用 較 小 的 最 小 周 長 進 行 放 大 最 小 周 長 會 比 較 好, 但 是 對 於 初 始 矩 陣 的 選 擇, 未 來 也 許 能 夠 在 進 行 更 多 的 實 驗 去 下 結 論 此 外, 模 擬 結 果 顯 示 依 照 本 文 中 演 算 法 所 建 構 出 的 LDPC code 之 位 元 錯 誤 率 的 確 是 具 有 較 低 的 錯 誤 率 可 以 縮 小 平 緩 之 現 象 34

參 考 文 獻 [1] R. G. Gallager, Low-Density Parity Check Codes. Cambridge, MA: MIT Press, 1963. [2] R. M. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory, vol. IT-27, no. 5, pp. 533 547, Sep. 1981. [3] F. R. Kschischang, B. J. Frey, and H. A. Loeliger, Factor graphs and the sum product algorithm IEEE Trans. Inf. Theory, vol. 47, no. 2, pp.498 519, Feb.2001. [4] Y. Kou, S. Lin, and M. P. C. Fossorier, Low-density parity-check codes based on finite geometries: A rediscovery and new results, IEEE Trans. Inf. Theory, vol. 47, no. 7, pp. 2711 2736, Nov. 2001. [5] B. Vasic, Structured iteratively decodable codes based on Steiner systems and their application in magnetic recording, Proc. IEEE Globecom 2001, vol. 5, pp. 2954 2960, Nov. 2001. [6] H. Tang, J. Xu, Y. Kou, S. Lin, and K. A. S. Abdel-Ghaffar, On algebraic construction of Gallager and circulant low-density parity-check codes, IEEE Trans. Inf. Theory, vol. 50, no. 6, pp. 1269 1279, Jun. 2004. [7] M. P. C. Fossorier, Quasicyclic low-density parity-check codes from circulant permutation matrices, IEEE Trans. Inf. Theory, vol. 50, no. 8, pp. 1788 1793, Aug. 2004. [8] B. Vasic and O. Milenkovic, Combinatorial constructions of low-density parity-check codes for iterative decoding, IEEE Trans. Inf. Theory, vol. 50, no. 6, pp. 1156 1176, Jun. 2004. [9] J. M. F. Moura, J. Lu, and H. Zhang, Structured LDPC codes with large girth, IEEE Signal Process. Mag., vol.21, no. 1, pp. 42 55, Jan. 2004. 35

[10] J. Lu and J. M. F. Moura, Structured LDPC codes for High-Density Recording: Large Girth and Low Error Floor, IEEE Trans. Inf. Theory, vol. 42, no. 2, pp. 208 213, Feb. 2006. [11] X. Y. Hu, E. Eleftheriou, and D. M. Arnold, Regular and irregular progressive edge-growth Tanner graphs, IEEE Trans. Inform. Theory, submitted for publication. [12] D. J. C. Mackay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inf. Theory, vol. 45, no. 2, pp. 399 431, Mar. 1999. [13] J. M. F. Moura, J. Lu, and H. Zhang, Structured LDPC codes with large girth, IEEE Signal Processing Magazine, vol. 21, no. 1, Jan. 2004. [14] J. Lu, J. M. F. Moura, and U. Niesen, Grouping-and-shifting designs for structured LDPC codes with large girth, in Proc. ISIT 2004, Chicago, IL, Jun. 27 July 2 2004. [15] B. Vasic and O. Milenkovic, Combinatorial constructions of low-density parity-check codes for iterative decoding, IEEE Trans. Inf. Theory, vol. 50, no. 6, Jun. 2004. [16] Sae-Young Chung, G. David Forney Jr., Thomas J. Richardson and Rudiger Urbande, On the design of low-density parity-check codes within 0.0045 db of the Shannon limit, IEEE Communications Letters, vol. 5, no. 2, pp. 58-60, Feb.2001. 36