論文封面格式

Transcription

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

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

3 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

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

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

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

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

8 一 簡 介 隨 著 無 線 或 有 線 的 通 訊 系 統 資 料 儲 存 的 應 用 蓬 勃 發 展, 在 資 料 傳 輸 上, 訊 息 的 流 通 量 急 速 增 加, 造 成 高 傳 輸 率 高 可 靠 度 的 通 訊 系 統 是 必 頇 的 但 資 料 傳 輸 過 程 中, 常 常 會 因 為 外 在 的 因 素 導 致 資 料 受 到 破 壞, 為 了 達 到 高 可 靠 度 及 高 效 率 的 傳 輸 品 質, 錯 誤 更 正 碼 (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 重 新 提 出 研 究 後 而 發 展 的 解 碼 演 算 法, 卻 可 以 逼 近 通 道 容 量 至 db[16], 且 相 較 於 渦 輪 碼 亦 有 較 低 的 計 算 複 雜 度 才 開 始 被 廣 泛 的 討 論 應 用, 所 以 在 最 新 的 無 線 通 訊 標 準 IEEE e 標 準 中, 已 經 將 LDPC Code 納 入 其 解 碼 器 的 選 項 之 一 而 且 在 下 一 代 的 衛 星 數 位 視 訊 廣 播 標 準 (DVB-S2) 中, 也 將 低 密 度 同 位 元 檢 查 碼 取 代 了 渦 輪 碼, 拜 現 今 硬 體 製 作 技 術 的 進 步, 高 速 的 平 行 解 碼 製 作 方 式 得 以 實 現, 使 得 LDPC Codes 已 成 為 目 前 相 當 熱 門 的 研 究 領 域 在 通 訊 系 統 中, 資 料 在 傳 輸 時 因 為 有 某 些 外 在 因 素, 使 得 接 收 到 的 資 料 發 生 錯 誤 像 是 受 到 雜 訊 干 擾, 或 者 傳 輸 媒 介 可 靠 度 不 佳 等 等 錯 誤 更 正 碼 藉 由 傳 遞 多 餘 的 1

9 校 正 資 訊, 使 得 解 碼 器 能 在 資 訊 發 生 錯 誤 時, 設 法 於 更 正 回 來 低 密 度 同 位 元 檢 查 碼 (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

10 本 論 文 裡, 採 用 分 割 及 位 移 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

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

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

13 出 現, 相 對 的 非 規 則 性 結 構 的 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 e 標 準 奇 偶 檢 查 矩 陣 格 式 6

14 這 一 個 奇 偶 檢 查 矩 陣 是 在 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

15 圖 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

16 演 算 法 最 小 和 演 算 法 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

17 步 驟 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 所 需 要 的 正 確 的 值 ?=0,so?=0 圖 2-6. Row processing 示 意 圖 10

18 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

19 三 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

20 被 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

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

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

23 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

24 (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

25 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

26 以 下 為 藉 由 結 論 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

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

28 演 算 法 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

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

30 下 圖 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

31 四 針 對 分 割 及 位 移 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

32 找 能 夠 在 矩 陣 中 找 到 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

33 步 驟 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

34 基 於 S, 可 以 建 構 出 一 個 最 小 周 長 為 6 碼 率 為 0.25 的 同 位 元 檢 查 矩 陣 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

35 圖 4-4. 最 小 周 長 為 16 的 S 矩 陣 表 4-1. 達 到 最 小 周 長 為 g 所 需 的 最 小 p 值 g p min 從 實 驗 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 的 H 當 作 初 始 矩 陣, 實 驗 的 結 果 為 下 表

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

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

38 五 錯 誤 率 之 模 擬 與 分 析 模 擬 環 境 : 利 用 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( ) 比 較 的 對 象 為 Random LDPC code, 行 權 重 為 4 列 權 重 為 3 最 小 周 長 為 6, 長 度 一 樣 為 如 下 圖 5-1, 為 我 們 的 模 擬 1 圖 5-1. 模 擬 1 在 模 擬 1 中, 因 為 我 們 選 擇 碼 率 較 低 的 矩 陣, 矩 陣 中 也 許 會 有 比 較 多 的 小 迴 圈, 導 致 在 模 擬 的 進 行 上 需 要 花 比 較 久 的 時 間 由 於 模 擬 的 環 境 是 用 軟 體 模 擬, 效 率 沒 有 用 硬 體 模 擬 來 的 好, 如 果 是 用 硬 體 來 執 行 模 擬 的 話, 也 許 模 擬 執 行 上 速 度 就 會 比 用 軟 31

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

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

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

42 參 考 文 獻 [1] R. G. Gallager, Low-Density Parity Check Codes. Cambridge, MA: MIT Press, [2] R. M. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory, vol. IT-27, no. 5, pp , Sep [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 , Feb [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 , Nov [5] B. Vasic, Structured iteratively decodable codes based on Steiner systems and their application in magnetic recording, Proc. IEEE Globecom 2001, vol. 5, pp , Nov [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 , Jun [7] M. P. C. Fossorier, Quasicyclic low-density parity-check codes from circulant permutation matrices, IEEE Trans. Inf. Theory, vol. 50, no. 8, pp , Aug [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 , Jun [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 , Jan

43 [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 , Feb [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 , Mar [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 [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 [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 [16] Sae-Young Chung, G. David Forney Jr., Thomas J. Richardson and Rudiger Urbande, On the design of low-density parity-check codes within db of the Shannon limit, IEEE Communications Letters, vol. 5, no. 2, pp , Feb