<4D6963726F736F667420576F7264202D20B373CEEBB5BEAABABDD7A4E55FADD7A5BF5F2E646F63>

國 立 交 通 大 學 電 機 與 控 制 工 程 學 系 碩 士 論 文 以 優 先 權 為 基 礎 之 消 去 迴 圈 演 算 法 建 構 低 密 度 同 位 元 檢 查 碼 Constructing Low-Density Parity-Check Codes by Priority Based Cycle Elimination Algorithm 研 究 生 : 連 昶 翔 指 導 教 授 : 董 蘭 榮 博 士 中 華 民 國 九 十 八 年 十 月

以 優 先 權 為 基 礎 之 消 去 迴 圈 演 算 法 建 構 低 密 度 同 位 元 檢 查 碼 Constructing Low-Density Parity-Check Codes by Priority Based Cycle Elimination Algorithm 研 究 生 : 連 昶 翔 指 導 教 授 : 董 蘭 榮 博 士 Student:Chang-Hsiang Lien Advisor:Lan-Rong Dung 國 立 交 通 大 學 電 機 與 控 制 工 程 學 系 碩 士 論 文 A Thesis Submitted to Department of Electrical and Control Engineering College of Electrical Engineering and Computer Science National Chaio-Tung University in Partial Fulfillment of the Requirements for the Degree of Master in Electrical and Control Engineering October 2009 Hsinchu, Taiwan, Republic of China 中 華 民 國 九 十 八 年 十 月 i

以 優 先 權 為 基 礎 之 消 去 迴 圈 演 算 法 建 構 低 密 度 同 位 元 檢 查 碼 研 究 生 : 連 昶 翔 指 導 教 授 : 董 蘭 榮 博 士 國 立 交 通 大 學 電 機 與 控 制 工 程 學 系 中 文 摘 要 低 密 度 同 位 元 檢 查 碼 具 有 優 異 的 解 碼 能 力 及 硬 體 實 現 的 低 複 雜 度, 近 年 來 受 到 廣 大 討 論 與 研 究, 其 中 一 部 分 研 究 為 設 計 具 有 較 大 周 長 或 是 消 除 更 多 的 短 迴 圈 的 同 位 檢 查 矩 陣 以 得 到 更 好 的 解 碼 效 能 本 論 文 提 出 以 優 先 權 為 基 礎 的 消 去 迴 圈 演 算 法, 統 計 每 個 元 素 包 含 的 迴 圈 數 量 高 低 排 列 優 先 順 序, 如 此 可 有 效 率 打 斷 迴 圈 的 連 結, 故 本 改 良 式 演 算 法 能 大 幅 降 低 建 構 矩 陣 的 運 算 量 此 外 設 計 低 編 碼 長 度 的 位 元 檢 查 矩 陣 時 因 為 優 先 權 的 機 制 能 更 有 效 率 打 斷 迴 圈, 因 此 相 較 其 它 兩 者 類 似 架 構 的 演 算 法 能 消 除 更 多 的 迴 圈, 得 到 效 能 上 的 增 進, 尤 其 是 在 較 高 訊 號 雜 訊 比 的 情 況 下 差 異 較 為 明 顯, 適 用 於 低 功 耗 或 低 運 算 量 等 通 訊 系 統 ii

Constructing Low-Density Parity-Check Codes by Priority Based Cycle Elimination Algorithm Student:Lien Chang-Hsiang Advisor:Lan-Rong Dung Institute of Electrical and Control Engineering National Chiao-Tung University Abstract In recent years, Low-Density Parity-Check Codes have attracted a lot of attention and discussion due to great decoding ability and low complexity of hardware implementation. Some research focuses on performance improvement by designing high performance coding with large girth. In this thesis, we propose a priority based cycle elimination algorithm. It is efficient to eliminate cycle by setting the priority based on the number of dependent cycles. As shown in the results, the proposed algorithm can significantly reduce the complexity in operation. It can also construct high-performance codes and eliminate more cycles than traditional approaches for short code-length applications. Comparing with the other algorithms, the proposed algorithm can have better decoding performance, especially in high SNR environment; hence, our algorithm can satisfy the requirement of low-power communication systems. iii

誌 謝 這 篇 論 文 的 完 成 要 感 謝 許 多 人, 首 先 感 謝 老 師 兩 年 多 來 的 細 心 指 導 與 督 促, 讓 我 確 定 研 究 的 方 向, 多 方 面 意 見 的 交 流 使 我 改 進 不 足 的 地 方, 給 我 許 多 寶 貴 的 意 見 而 能 繼 續 研 究 下 去 再 來 感 謝 實 驗 室 的 夥 伴, 謝 謝 學 弟 們 幫 忙 我 許 多 事 情, 使 我 更 能 專 心 的 研 究 省 去 一 些 生 活 上 的 不 便, 謝 謝 致 翰 嘉 鴻 以 及 智 勝, 在 課 業 及 生 活 中 給 予 我 許 多 的 幫 助, 並 留 下 許 多 美 好 的 回 憶 最 後 我 要 感 謝 我 的 家 人, 一 直 在 背 後 照 顧 栽 培 我 的 父 親 與 母 親 以 及 可 愛 的 弟 弟, 感 謝 你 們 一 路 支 持 我 使 我 無 後 顧 之 憂 專 心 完 成 學 業, 在 此 獻 上 最 深 的 敬 意 與 感 謝 98 年 10 月 iv

目 錄 中 文 摘 要...ii Abstract...iii 誌 謝...iv 第 一 章 導 論...1 1.1 研 究 背 景 與 動 機...1 1.2 論 文 組 織...3 第 二 章 低 密 度 同 位 檢 查 碼...4 2.1 低 密 度 同 位 檢 查 碼 簡 介...4 2.1-1 基 本 概 念 及 特 性 介 紹...4 2.1-2 Gallager Codes...6 2.1-3 Mackay Codes...7 2.2 LDPC 編 碼 方 式 介 紹...7 2.2-1 傳 統 編 碼 方 式...7 2.2-2 Richardson 編 碼 演 算 法...8 2.3 LDPC 解 碼 方 式 介 紹...11 2.3-1 Sum-Product Algorithm...12 2.3-2 Min-Sum Algorithm...18 2.3-3 Min-Sum Correction-Factor...18 第 三 章 傳 統 消 去 迴 圈 演 算 法 (Cycle Elimination)...20 3.1 基 本 矩 陣 與 擴 展...20 3.2 形 成 迴 圈 之 條 件 與 限 制...21 3.3 傳 統 消 去 迴 圈 演 算 法...26 3.3-1 演 算 法 流 程...26 v

3.3-2 演 算 法 分 析 與 比 較...27 第 四 章 改 良 式 消 去 迴 圈 演 算 法...29 4.1 搜 尋 迴 圈 與 演 算 法 流 程...29 4.1-1 搜 尋 迴 圈 方 法...29 4.1-2 演 算 法 流 程 與 架 構...32 4.2 模 擬 結 果 與 分 析...37 4.3 適 用 於 低 編 碼 長 度 之 說 明 與 效 能 模 擬...42 4.3-1 解 碼 長 度 與 遞 迴 次 數 之 間 的 影 響...42 4.3-2 周 長 與 短 迴 圈 對 解 碼 效 能 之 模 擬...43 4.3-3 傳 統 與 改 良 式 演 算 法 在 低 編 碼 長 度 之 模 擬 比 較...44 第 五 章 結 論...50 參 考 文 獻...51 vi

圖 目 錄 圖 2-1 (7,3,3) 正 規 檢 查 矩 陣...5 圖 2-2 (7,3,3) 正 規 檢 查 矩 陣 之 Tanner Graph...5 圖 2-3 Gallager LDPC Codes H1 的 區 塊 矩 陣...7 圖 2-4 H 矩 陣 的 下 三 角 矩 陣 格 式...9 圖 2-5 Richardson 定 義 之 矩 陣 格 式...9 圖 2-6 式 2-13 之 Tanner Graph...12 圖 3-1 Cycle 表 示 方 法...20 圖 3-2 擴 展 矩 陣 示 意 圖...21 圖 3-3 擴 展 矩 陣 之 後 迴 圈 情 況...22 圖 3-4 計 算 位 移 量 的 方 向 示 意 圖...23 圖 3-5 方 塊 矩 陣 之 元 素 坐 標 ( 節 錄 自 [20] Fig.5)...25 圖 3-6 各 方 塊 矩 陣 迴 圈 連 結 示 意 圖 ( 節 錄 自 [20] Fig.6)...25 圖 3-7 傳 統 消 去 迴 圈 演 算 法 位 移 動 作 之 圖 例...26 圖 4-1 搜 尋 時 之 方 向 示 意 圖...30 圖 4-2 搜 尋 迴 圈 示 意 圖...31 圖 4-3 造 成 同 一 點 搜 尋 兩 次 之 範 例...32 圖 4-4 搜 尋 時 路 徑 超 過 原 點 左 半 邊 之 範 例...32 圖 4-5 若 A B 共 點 則 C D 共 點 將 無 法 找 到 搜 尋 路 徑 之 圖 例...36 圖 4-6 原 點 被 搜 尋 到 兩 次 之 範 例...36 圖 4-7 表 單 處 理 constraint 動 向 之 示 意 圖...37 圖 4-8 Code Rate=1/2 Irregular Matrix...38 圖 4-9 每 次 執 行 位 移 動 作 後 所 有 元 素 最 大 迴 圈 值 之 長 條 圖...39 圖 4-10 每 次 執 行 位 移 動 作 後 所 有 剩 餘 迴 圈 平 均 值 之 長 條 圖...40 vii

圖 4-11 不 同 編 碼 長 度 下 遞 迴 次 數 對 解 碼 效 能 的 影 響...43 圖 4-12 不 同 周 長 的 位 元 檢 查 矩 陣 對 解 碼 效 能 的 影 響...44 圖 4-13 不 同 擴 展 倍 數 下 所 剩 餘 迴 圈 總 量...46 圖 4-14 PCE 與 CE 演 算 法 編 碼 長 度 為 360 之 效 能 圖...46 圖 4-15 PCE 與 CE 演 算 法 編 碼 長 度 為 720 之 效 能 圖...47 圖 4-16 不 同 擴 展 倍 數 下 所 剩 餘 迴 圈 總 量...48 圖 4-17 PCE 與 CE 演 算 法 編 碼 長 度 為 1800 之 效 能 圖...48 圖 4-18 PCE 與 CE 演 算 法 編 碼 長 度 為 1800 之 效 能 圖...49 圖 4-19 PCE 與 CE 演 算 法 編 碼 長 度 為 3600 之 效 能 圖...49 viii

表 目 錄 表 2-1 p 1 複 雜 度 分 析...11 表 2-2 p 2 複 雜 度 分 析...11 表 3-1 估 計 運 算 的 constraint 總 量...27 表 3-2 每 條 constraint 的 加 減 法 總 量...28 表 4-1 每 個 元 素 為 1 之 陣 列...30 表 4-2 非 正 規 基 本 矩 陣 各 種 參 數...38 表 4-3 Code Rate=1/2 矩 陣 中 各 種 迴 圈 總 數 與 平 均...39 表 4-4 兩 種 演 算 法 之 比 較 列 表...41 表 4-5 兩 種 演 算 法 之 乘 法 數 與 加 法 數...41 表 4-6 本 演 算 法 在 1 分 佈 密 集 區 域 執 行 後 剩 餘 的 迴 圈 數 量...42 ix

第 一 章 導 論 節 內 容 本 章 節 介 紹 論 文 主 題 之 相 關 背 景 及 研 究 的 動 機, 並 在 論 文 組 織 中 簡 述 各 章 1.1 研 究 背 景 與 動 機 在 通 訊 技 術 日 益 進 步 的 現 代, 人 們 越 來 越 倚 靠 通 訊 所 帶 給 人 類 的 便 利 性 無 論 是 最 近 熱 門 的 無 線 網 路 系 統 WI-FI WiMAX 新 一 代 手 機 通 訊 系 統 等 技 術 的 發 展 一 日 千 里, 因 為 這 部 分 擁 有 廣 大 的 商 機 及 市 場, 眾 多 研 究 機 構 及 廠 商 投 資 大 量 人 力 及 金 錢 進 行 研 發 工 作, 而 隨 著 傳 輸 速 度 增 加 及 通 訊 品 質 的 要 求, 尤 其 對 於 高 速 無 線 系 統 來 說 環 境 所 造 成 雜 訊 干 擾 甚 大, 有 時 還 會 受 到 頻 率 範 圍 的 限 制 對 整 體 通 訊 品 質 受 到 影 響, 因 此 大 家 都 專 注 在 如 何 讓 無 線 傳 輸 的 品 質 變 好, 主 要 的 解 決 辦 法 就 是 使 用 錯 誤 更 正 碼 提 升 傳 輸 效 率 及 錯 誤 更 正 能 力 在 傳 輸 系 統 中 資 料 傳 輸 速 度 有 其 上 限 值 稱 為 通 道 容 量, 只 要 傳 輸 的 訊 號 強 度 及 速 度 不 超 過 此 值 均 可 以 使 用 適 當 的 編 解 碼 達 到 良 好 的 錯 誤 更 正 能 力 1948 年 夏 農 (Shannon) 發 表 重 要 的 通 道 理 論 [1], 在 傳 輸 過 程 中 如 果 速 率 小 於 通 道 容 量, 就 可 以 達 到 很 小 的 錯 誤 率, 雖 然 未 指 出 哪 種 編 碼 方 式 的 效 能 可 以 達 到 很 小 的 錯 誤 率, 但 此 理 論 成 為 指 標 也 發 展 了 許 多 的 編 碼 方 式 [2], 這 些 編 碼 主 要 分 成 兩 大 類, 一 類 為 線 性 區 塊 碼 [3](Linear Block Codes) 另 一 類 為 迴 旋 碼 [4] (Convolutional Code), 線 性 區 塊 碼 目 前 較 為 熱 門 有 循 環 碼 [5](Cyclic Codes) 里 德 - 所 羅 門 碼 [6](Reed-Solomon Codes) 低 密 度 同 位 檢 查 碼 (Low-Density Parity-Check Codes)[7], 而 迴 旋 碼 中 熱 門 有 渦 輪 碼 [8](Turbo Codes), 其 中 又 以 低 密 度 同 位 檢 查 碼 跟 渦 輪 碼 最 受 重 視 低 密 度 同 位 檢 查 碼 簡 稱 LDPC Codes 早 在 1962 年 就 由 Gallager 提 出, 當 時 因 為 電 腦 與 超 大 型 積 體 電 路 不 發 達, 因 此 無 1

法 負 擔 複 雜 運 算 量 高 的 LDPC Codes, 直 到 近 年 來 電 腦 運 算 發 達 的 現 代 才 逐 漸 被 重 視, 並 發 現 他 擁 有 優 異 的 錯 誤 更 正 能 力 [9][10], 開 始 有 許 多 人 踏 入 研 究 LDPC Codes 的 領 域 LDPC Codes 解 碼 方 式 類 似 Turbo Codes, 以 重 覆 遞 迴 更 新 每 一 位 元 的 機 率 資 訊 來 找 出 最 正 確 的 codes, 具 有 高 錯 誤 更 正 率 硬 體 實 現 度 高 且 可 平 行 化 Low error-floor 等 特 性, 同 時 LDPC 屬 於 線 性 區 塊 碼, 一 次 能 處 理 幾 千 甚 至 上 萬 個 位 元 數, 再 利 用 解 碼 平 行 化 的 實 現 [11], 所 以 能 達 到 很 高 的 吞 吐 量 [12], 但 缺 點 為 編 碼 的 複 雜 度 高, 現 在 有 幾 篇 已 發 表 的 論 文 如 [13] 使 編 碼 的 複 雜 度 變 低, 加 速 編 碼 的 速 度 構 成 一 個 好 的 LDPC 有 兩 條 重 要 的 因 素, 一 為 矩 陣 中 元 素 1 的 分 佈 [14], 另 一 為 短 迴 圈 (short cycle) 的 影 響, 因 為 LDPC 解 碼 方 式 為 重 覆 遞 迴 去 逼 近 於 正 確 的 碼 字, 解 碼 的 過 程 與 訊 息 傳 遞 之 間 的 獨 立 性 有 很 大 的 關 係, 在 已 有 的 文 獻 指 出 LDPC 要 有 良 好 的 更 正 能 力 必 須 讓 訊 息 傳 送 盡 可 能 的 獨 立 不 受 干 擾, 所 以 研 究 為 如 何 設 計 一 個 具 有 高 周 長 (Girth) 的 位 元 檢 查 矩 陣 為 本 論 文 研 究 的 動 機 之 一, 另 外 BLOCK-LDPC 的 架 構 在 硬 體 實 現 上 較 為 容 易 且 能 平 行 化 增 加 產 出, 結 合 這 兩 項 因 素 形 成 消 去 迴 圈 演 算 法 的 主 要 理 論 與 架 構 本 篇 論 文 主 要 探 討 建 構 LDPC Codes 的 演 算 法 設 計, 改 良 原 有 消 去 迴 圈 演 算 法 (Cycle Elimination Algorithm), 由 於 CE 演 算 法 本 身 為 近 似 暴 力 法 的 方 式 實 現, 故 運 算 量 及 複 雜 度 高, 且 演 算 法 運 作 特 性 使 然 在 低 擴 展 倍 數 下 打 斷 迴 圈 的 效 果 有 限, 因 此 我 們 提 出 以 CE 演 算 法 為 基 礎 加 入 優 先 權 的 概 念 而 改 良 的 演 算 法, 找 尋 該 元 素 擁 有 最 大 關 聯 性 也 就 是 包 含 最 多 迴 圈 優 先 動 作, 如 此 可 在 每 次 動 作 時 有 效 率 的 打 斷 更 多 迴 圈, 不 僅 大 量 減 低 演 算 法 的 運 算 複 雜 度, 在 設 計 低 編 碼 長 度 小 於 4000 位 元 的 矩 陣 能 消 除 更 多 的 短 迴 圈 進 而 增 加 解 碼 效 能, 模 擬 結 果 也 顯 示 相 較 於 其 它 兩 種 演 算 法 效 能 上 的 改 進, 所 以 適 用 於 行 動 或 無 線 通 訊 系 統 為 了 低 運 算 量 及 省 電 而 採 取 低 編 碼 長 度 的 解 碼 應 用 2

1.2 論 文 組 織 本 篇 論 文 將 以 下 的 章 節 劃 分 為 五 個 章 節, 茲 分 述 如 下 : 第 一 章 簡 述 錯 誤 更 正 碼 的 發 展, 說 明 LDPC 碼 的 特 性 與 研 究 背 景, 最 後 提 出 本 論 文 的 動 機 與 方 向 第 二 章 則 介 紹 本 論 文 之 背 景 知 識 作, 內 容 共 分 為 三 個 部 份 第 一 節 介 紹 LDPC 的 基 本 原 理 與 特 性 ; 第 二 節 介 紹 LDPC 的 兩 種 編 法 方 式, 一 種 為 傳 統 式 編 碼, 複 雜 度 會 隨 著 矩 陣 大 小 而 有 明 顯 的 改 變, 另 一 種 為 低 運 算 量 的 編 碼 方 式, 尤 其 針 對 長 矩 陣 的 編 碼 能 有 效 減 低 運 算 複 雜 度 第 三 章 介 紹 傳 統 式 消 去 迴 圈 演 算 法, 除 了 說 明 演 算 法 流 程 之 外, 並 分 析 演 算 法 的 運 算 複 雜 度 與 優 缺 點 第 四 章 介 紹 改 良 式 消 去 迴 圈 演 算 法, 詳 盡 說 明 演 算 法 的 步 驟 與 要 點, 此 外 以 兩 個 範 例 矩 陣 證 明 具 有 快 速 消 除 迴 圈 的 效 果, 也 簡 化 大 量 的 運 算 複 雜 度, 最 後 提 出 以 較 小 的 編 碼 長 度 的 解 碼 效 能 略 優 於 傳 統 式 的 消 去 迴 圈 演 算 法 第 五 章 為 結 論 與 未 來 研 究 方 向 之 提 議 3

第 二 章 低 密 度 同 位 檢 查 碼 本 章 將 介 紹 LDPC 碼 的 基 本 概 念, 包 含 了 LDPC 的 特 性 建 構 同 位 檢 查 矩 陣 的 種 類 以 及 編 碼 解 碼 的 方 式 2.1 低 密 度 同 位 檢 查 碼 簡 介 構 此 節 敘 述 LDPC 基 本 概 念 及 特 性, 並 介 紹 最 早 所 提 出 的 Gallager Codes 架 2.1-1 基 本 概 念 及 特 性 介 紹 低 密 度 同 位 檢 查 碼 (LDPC Codes) 是 一 種 線 性 區 塊 碼, 因 此 在 編 碼 及 解 碼 時 會 將 一 連 串 的 來 源 訊 息 分 段 處 理, 每 一 段 的 位 元 長 度 為 K 編 碼 時 將 此 K bits 與 生 成 矩 陣 G K N 位 元, 我 們 可 以 表 示 為 : 相 乘 後 得 到 長 度 為 K+M 的 碼 字 (Code word), 其 中 M bit 為 檢 查 v s G = (1) 1 N 1 K K N 編 碼 後 的 資 料 v 經 由 通 道 傳 輸 到 接 收 端, 再 利 用 同 位 檢 查 矩 陣 H (Parity-Check matrix) 檢 查 收 到 的 碼 是 否 正 確 並 加 以 修 正 H 矩 陣 分 成 正 規 矩 陣 與 非 正 規 矩 陣 (regular codes), 所 謂 正 規 矩 陣 指 H 矩 陣 中 每 一 行 及 每 一 列 中 1 的 個 數 相 同, 若 一 個 m x n 大 小 H 矩 陣 中 每 列 含 有 k 個 1 每 行 含 有 j 個 1 則 定 義 為 (n,j,k)-regular LDPC Codes, 其 中 j k 稱 為 行 權 重 (column weight) 及 列 權 重 (row weight), 並 不 是 每 個 H 矩 陣 都 有 相 同 的 權 重, 而 這 些 矩 陣 為 非 正 規 矩 陣 (irregular codes) 為 了 方 便 我 們 了 解 LDPC 運 作 的 情 形,Tanner[15] 提 出 了 Tanner Graph 也 稱 為 Bipartite Graph, 以 圖 2-1 的 (7,3,3) 正 規 檢 查 矩 陣 為 例, 它 的 Tanner 4

Graph 表 示 為 圖 2-2, 每 一 列 均 可 用 一 個 節 點 代 表 稱 做 檢 查 節 點 (check node), 每 一 行 均 可 用 一 個 節 點 代 表 稱 做 位 元 節 點 (check node), 而 檢 查 節 點 與 位 元 節 點 中 間 的 連 線 稱 做 edge, 這 些 edge 將 各 節 點 的 訊 息 互 相 傳 輸 H 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 = 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 M N 圖 2-1 (7,3,3) 正 規 檢 查 矩 陣 C1 C2 C3 C4 C5 C6 C7 Check nodes Edge V1 V2 V3 V4 V5 V6 V7 Bit nodes 圖 2-2 (7,3,3) 正 規 檢 查 矩 陣 之 Tanner Graph 迴 圈 (Cycle) 指 從 一 個 節 點 出 發, 經 過 幾 條 edge 之 後 再 回 到 同 一 個 節 點, 而 這 個 路 徑 是 封 閉 的 且 同 一 節 點 不 能 通 過 兩 次 以 上, 如 圖 2-2 中 虛 線 所 示, 從 V1 節 點 出 發 經 由 edge 通 過 C1 V2 C2 V3 C7 共 六 點 及 六 條 edge 回 到 C1, 這 是 一 條 封 閉 的 Cycle 且 因 為 通 過 六 個 點 我 們 稱 為 Cycle-6, 一 個 矩 陣 所 有 的 Cycle 中 最 小 Cycle length 稱 作 Girth 5

LDPC 的 同 位 檢 查 矩 陣 除 了 影 響 編 碼 的 複 雜 度 之 外, 對 解 碼 效 能 的 影 響 更 是 巨 大, 所 以 我 們 一 般 說 建 構 LDPC Codes 就 是 指 設 計 它 的 H 矩 陣 通 常 H 矩 陣 設 計 上 有 兩 個 重 點, 一 為 矩 陣 的 大 小, 因 為 矩 陣 的 大 小 行 數 等 於 Code length, 在 Gallager[7] 文 獻 中 提 到, 一 個 亂 數 產 生 的 (n,j,k) 矩 陣 最 小 距 離 (minimum distance) d min Nσ ( j, k) 其 中 σ ( j, k) >0, 所 以 當 code length N 越 長 時 最 小 距 離 也 跟 著 變 大, 也 就 是 有 較 好 的 效 能 ; 另 一 為 Cycle length 的 大 小,Tanner 在 [14] 文 獻 中 指 出, 如 果 LDPC Codes 有 越 大 的 Girth 時 代 表 解 碼 時 能 有 更 多 獨 立 的 遞 迴 運 算 使 錯 誤 更 正 能 力 增 加 因 此 H 矩 陣 中 短 Cycle 是 盡 量 避 免 的, 這 部 分 也 是 本 論 文 的 重 點, 利 用 改 良 的 演 算 法 使 短 Cycle 消 除 2.1-2 Gallager Codes 前 文 曾 提 到 LDPC Codes 共 分 為 regular 及 irregular 兩 種,Gallager LDPC 則 是 屬 於 regular 隨 機 分 配 的 矩 陣, 具 有 以 下 定 義 及 特 性 一 個 (n,j,k)-regular 的 矩 陣 含 有 nj / k 個 列, 矩 陣 大 小 為 M x N, 而 它 的 檢 查 位 元 (parity bit) 長 度 為 k=m-n, 此 矩 陣 的 排 列 架 構 如 式 (2) 表 示 : H H1 H 2 = H j (2) 對 於 每 一 個 子 矩 陣 H, i = 1,2,..., j 大 小 為 p x (p x k) 列 權 重 為 k 及 行 i 權 重 為 1 第 一 個 子 矩 陣 H 1 的 分 佈 似 階 梯 狀, 如 圖 2-3 所 示 在 第 一 列 中 有 連 續 3 個 1 排 列, 因 此 1 的 排 列 範 圍 為 ( i 1) k + 1 to ik, for i = 1,2,..., p, 此 處 k=3, 其 它 部 分 的 子 矩 陣 是 配 合 第 一 列 所 做 的 隨 機 排 列 矩 陣 6

H 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 = 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 圖 2-3 Gallager LDPC Codes H1 的 區 塊 矩 陣 2.1-3 Mackay Codes [16] Mackay 提 出 一 個 隨 機 產 生 位 元 檢 查 矩 陣 的 方 法, 建 構 矩 陣 時 為 一 行 一 行 疊 上 去, 如 第 一 行 元 素 1 的 位 置 是 隨 機 的, 但 第 二 行 開 始 元 素 1 的 位 置 不 能 與 第 一 行 相 同 以 免 造 成 cycle-4 的 迴 圈 產 生, 而 之 後 的 行 數 每 疊 上 去 都 會 檢 查 之 前 行 數 1 的 位 置 避 免 在 同 一 列, 因 此 所 建 構 而 成 的 矩 陣 完 全 沒 有 cycle-4 的 迴 圈 存 在, 可 在 解 碼 時 增 加 錯 誤 更 正 能 力 以 提 升 效 能 2.2 LDPC 編 碼 方 式 介 紹 LDPC 為 線 性 區 塊 碼, 因 此 可 利 用 高 斯 消 去 法 產 生 G, 但 因 為 此 種 方 式 隨 著 code length 增 加 而 需 要 大 量 的 運 算 及 複 雜 度, 所 以 部 分 研 究 針 對 LDPC 編 碼 提 出 有 效 率 的 編 碼 方 法, 以 下 的 內 容 也 會 一 併 介 紹 2.2-1 傳 統 編 碼 方 式 令 原 始 訊 息 為 u= [ u0, u1,..., uk 1], 經 由 生 成 矩 陣 G 得 到 碼 字 c= [ c0, c1,..., cn 1], 可 表 示 為 : c=u.g (3) 7

其 中 G 的 大 小 為 k x n 因 為 H 矩 陣 與 G 矩 陣 維 度 互 相 正 交 使 相 乘 之 後 為 零, 故 T H 的 大 小 為 (n-k) x n, 所 以 可 由 以 下 公 式 推 導 出 c H = 0 T G H = 0 T ug H = 0 ( u 0) (4) T c H = 0 如 果 H 矩 陣 為 列 滿 秩 則 由 高 斯 消 去 法 得 到 H H = I P (5) M N sys ( M N) N ( M N) N T 其 中 I 為 單 位 矩 陣, 因 為 G H = 0, 故 G sys T H = 0 sys I ( M N) N Gsys 0 T = P ( M N) N G P I T sys = ( M N ) N ( M N ) N (6) 在 剛 剛 的 高 斯 消 去 法 中 得 到 矩 陣 不 一 定 是 標 準 的 [ I P ] 格 式, 還 需 要 經 過 行 與 行 之 間 的 置 換, 所 以 產 生 的 G sys G 轉 換 成 正 確 的 G 也 要 重 做 行 之 間 的 置 換 2.2-2 Richardson 編 碼 演 算 法 [13] H 矩 陣 經 高 斯 消 去 法 可 得 到 如 圖 2-4 的 矩 陣 分 配, 但 不 是 任 意 矩 陣 均 可 由 高 斯 消 去 法 加 上 行 轉 換 形 成 此 種 矩 陣, 因 此 Richardson 提 出 一 種 有 效 率 的 編 碼 適 用 於 任 何 矩 陣, 且 減 少 矩 陣 運 算 的 複 雜 度 及 運 算 量 8

n-m m m 1 1 1 1 1 1 1 11 1 n 圖 2-4 H 矩 陣 的 下 三 角 矩 陣 格 式 首 先 將 H 矩 陣 經 過 行 與 列 的 排 列 之 後 形 成 圖 2-5 的 形 式, 此 形 式 表 示 為 H A B T = C D E (7) n-m g m-g m A B T C D E m-g g n 圖 2-5 Richardson 定 義 之 矩 陣 格 式 矩 陣 中 各 子 矩 陣 的 大 小 上 圖 所 標 示, 其 中 T 為 下 三 角 矩 陣, 將 此 矩 陣 的 左 邊 乘 以 下 述 的 子 矩 陣 9

I 0 A B T 1 ET I C D E (8) 得 到 A B T 1 1 ET A + C ET B + D 0 (9) 令 編 碼 完 的 碼 字 分 成 三 部 分 c= (, s p1, p2),s 為 長 度 (m-n) 資 訊 位 元 T p1 及 p2 分 別 為 長 度 g 與 (m-g) 的 檢 查 位 元, 因 為 c H = 0, 所 以 將 c 與 式 (9) 相 乘 得 到 兩 條 式 子 T T T As + Bp1 + Tp2 = 0 + + + = 1 T 1 T ( ET A C) s ( ET B D) p1 0 (10) 設 1 r ET B D = + 為 非 奇 異 矩 陣 可 逆, 代 入 式 (10) 運 算 得 p = r ET A+ C s (11) T 1 1 T 1 ( ) T p 1 得 到 後 再 代 回 式 (10) 得 p = T ( As + Bp ) (12) T 1 T T 2 1 有 了 p1, p 2就 可 代 回 原 來 分 段 的 碼 字 中 得 到 c, 即 為 編 碼 後 的 結 果, 整 體 的 運 算 複 雜 度 列 於 表 2-1 與 表 2-2 算 式 內 容 複 雜 度 T As 1 T T [ As ] ET As 1 T [ ] 稀 疏 矩 陣 相 乘 T 1 [ As ] = y [ As ] = Ty T T T T 稀 疏 矩 陣 相 乘 On ( ) On ( ) On ( ) 10

T Cs T ET As +[ Cs ] 1 T [ ] 1 1 T T r ET As Cs [ + ] 稀 疏 矩 陣 相 乘 相 加 密 集 矩 陣 相 乘 On ( ) On ( ) 2 Og ( ) 表 2-1 p 1 複 雜 度 分 析 算 式 內 容 複 雜 度 T As T Bp 1 T T [ As ]+[ Bp 1 ] [ + ] 1 T T T As Bp1 稀 疏 矩 陣 相 乘 稀 疏 矩 陣 相 乘 相 加 + = + = 1 T T T T T T T [ As Bp1 ] y [ As Bp1 ] Ty On ( ) On ( ) On ( ) On ( ) 表 2-2 p 2 複 雜 度 分 析 2.3 LDPC 解 碼 方 式 介 紹 LDPC 的 解 碼 方 式 採 用 遞 迴 運 算 (Iterative Decoding), 利 用 多 次 重 覆 傳 送 位 元 節 點 與 檢 查 節 點 之 間 的 訊 息 使 解 碼 結 果 逼 近 原 始 資 料, 通 常 遞 迴 的 次 數 越 多 則 解 碼 值 越 正 確, 此 外 為 了 方 便 硬 體 實 現 及 簡 化 運 算 複 雜 度, 解 碼 時 大 多 採 用 LLR 的 形 式 [17] 本 節 將 介 紹 常 用 的 三 種 解 碼 演 算 法, 這 些 演 算 法 均 屬 於 軟 性 決 策 (Soft decision) 解 碼 而 有 優 秀 的 錯 誤 更 正 能 力 11

2.3-1 Sum-Product Algorithm [18] Tanner Graph 的 圖 形 解 碼 使 我 們 容 易 了 解 LDPC 解 碼 的 過 程, 在 說 明 整 體 演 算 法 流 程 之 前, 先 舉 簡 單 的 例 子 表 達 訊 息 傳 遞 及 推 導 機 率 公 式 的 過 程, 其 中 部 分 過 程 參 考 [19] 這 邊 有 一 個 2x4 的 位 元 檢 查 矩 陣 : 1 0 0 1 H = 1 1 1 0 (13) 設 收 到 的 碼 字 code word 為 c=(c1,c2,c3,c4), 要 判 斷 是 否 為 正 確 的 碼 字 則 使 之 與 位 元 檢 查 矩 陣 相 乘 得 到 T c H = 0 1 0 0 1 (1, c c2, c3, c4) 0 1 1 1 0 = c1 c4 = 0 ( equation S1) c1 c2 c3 = 0 ( equation S2) (14) 其 中 符 號 代 表 modulo-2 加 法 運 算, 所 得 到 的 兩 條 方 程 式 稱 為 位 元 檢 查 方 程 式 (parity check equation), 而 方 程 式 的 數 量 與 列 的 數 量 相 同 位 元 檢 查 矩 陣 由 Tanner Graph 表 示 如 下 S1 S2 Check nodes c1 c2 c3 c4 Bit nodes 圖 2-6 式 2-13 之 Tanner Graph 12

S1 跟 S2 分 別 代 表 兩 條 位 元 檢 查 方 程 式,c1~c4 代 表 code word 中 4 個 位 元 的 點, 首 先 我 們 對 c1 做 單 一 位 元 的 解 碼 : 位 元 c4 的 priori-probability 為 0 與 1 的 機 率 是 p0 與 p1, 其 中 p0+p1=0 因 為 透 過 S1 的 傳 遞 給 c1 訊 息 的 位 元 節 點 有 c4, 所 以 經 由 S1 方 程 式 c1 c4= 0 可 以 得 到 S1 c1 c4 (p0,p1) Pc ( 1 = 0) = Pc ( 4 = 0) = p Pc (1= 1) = Pc (4= 1) = p1 0 (15) 同 理 透 過 S2 的 位 元 節 點 有 c3 c4, 經 由 S2 方 程 式 c1 c2 c3= 0 得 到 S2 c1 c3 c4 (q0,q1) (r0,r1) Pc (1= 0) = Pc (2 c3= 0) = Pc ( 2 = 0) Pc ( 3 = 0) + Pc ( 2 = 1) Pc ( 3 = 1) = qr 0 0 + qr 1 1 Pc (1= 1) = Pc (2 c3= 1) = Pc ( 2= 1) Pc ( 3= 0) + Pc ( 2= 0) Pc ( 3= 1) = qr 10+ qr 01 (16) 因 為 S1 及 S2 都 有 傳 遞 機 率 訊 息 給 c1, 因 此 c1 要 整 合 這 兩 組 資 訊, 我 們 由 式 (17) 表 示 : 13

p, p S1) ( S 0 S1 S2 c1 ( S 0 q, q S1 ) Pc ( 1= 0) PS ( 1= 0 andc1= 0) PS ( 1= 0 andc1= 0) = p q Pc (1= 1) PS ( 1= 0 andc1= 1) PS ( 1= 0 andc1= 1) = p q S0 S0 S1 S1 (17) 其 中 ps0 = p0, ps1 = p1, qs0 = q0r0 + qr 1 1 and qs1 = qr 1 0 + q0r1 以 S2 檢 查 節 點 來 看, 它 要 整 合 c3 及 c4 的 機 率 資 訊, 所 以 我 用 下 式 代 表 c1 得 到 的 機 率 : ps2( q, q, r, r) = ( qr + qr, qr + qr) (18) 0 1 0 1 0 0 1 1 1 0 0 1 因 為 任 一 點 0 與 1 的 機 率 總 合 為 1 也 就 是 p0 p1 1 LLR(Log-Likelihood Ratio) 的 型 式 + =, 為 了 簡 化 運 算 採 用 L p p = = λ (19) 0 ( 0, p1) ln ln p1 代 入 式 (18) 得 qr 0 0 1+ qr 0 0+ qr 1 1 qr 11 ps2( L1, L2) = ps2( L1 L2) = ln = ln qr r 10+ qr 01 0 q0 + r q 1 1 14

L + L L + L 1 2 1 2 L1 L2 2 2 e e e e 1+ λλ 1+ + = = = e + e L1+ L2 L1 L2 = ln(cosh( )) ln(cosh( )) 2 2 1 L1 L2 = 2 tanh (tanh( ) tanh( )) 2 2 1 2 ln ln ln L1 L2 L L L L λ1+ λ2 e + e 2 2 1 2 1 2 (20) 式 (20) 可 轉 成 另 一 種 型 式 L L ps L L 2 2 = sign( L ) sign( L ) φφ ( ( L ) + φ( L )) 1 1 2 2( 1, 2) = 2 tanh (tanh( ) tanh( )) 1 2 1 2 (21) 其 中 x x e + 1 φ( x) = ln tanh( ) = ln and φ( φ( x))= x x 2 e 1 (22) 以 上 為 S2 檢 查 節 點 搜 集 其 它 位 元 節 點 的 資 訊, 經 由 數 學 運 算 統 計 機 率 後 再 傳 給 該 解 碼 的 位 元 節 點, 然 而 S1 與 S2 都 有 連 線 至 c1, 因 此 c1 會 收 到 這 兩 個 檢 查 節 點 的 訊 息, 與 (18) 類 似 的 概 念 得 到 下 式 p q pc1( ps0, ps1, qs0, qs1), p q S0 S0 S1 S1 = ps0qs0 + ps1qs1 ps0qs0 + ps1qs1 (23) 將 式 (19) 代 入 pc1( L, L ) = ln( λ λ ) = lnλ + lnλ = L + L (24) 1 2 1 2 1 2 1 2 故 將 兩 個 檢 查 節 點 的 機 率 值 相 加 即 是 綜 合 S1 S2 的 機 率 式 (21) 與 式 (24) 均 為 統 計 運 算 兩 個 節 點 的 機 率 值, 將 此 兩 個 公 式 擴 展 成 整 合 多 數 節 點 的 機 率 值, 由 式 (20) 擴 展 得 到 15

ps( L L L ) 1 2 = ps( ps( ps( ps( L L ) L ) ) L ) i i= 1 i= 1 1 2 3 = sign( L1) sign( L2) sign( Ln) φφ ( ( L1 ) + + φ( Ln )) (25) n = sign( L ) φφ ( ( L )) n n n n 此 為 檢 查 節 點 從 n 個 位 元 節 點 統 計 的 機 率 值, 接 著 要 統 計 多 個 檢 查 節 點 至 單 一 位 元 節 點 的 機 率 值, 由 式 (24) 擴 展 得 到 pc( L, L,, L ) = ln( λ λ λ ) 1 2 n 1 2 = ln λ + ln λ + + ln λ = L + L + + L 1 2 2 1 2 n n (26) 此 為 位 元 節 點 從 n 個 檢 查 節 點 統 計 的 機 率 值, 有 了 上 述 的 概 念 之 後, 接 下 來 介 紹 Sum-Product Algorithm 的 解 碼 流 程, 以 編 號 作 為 演 算 法 之 順 序 (1) 初 始 化 (Initialization) 設 L n P( yn xn = 0) 2 = ln = ( 1) 2 P y x = σ n n y n (27) 其 中 P(a b) 表 示 b 位 元 從 傳 送 端 出 發 在 接 收 端 收 到 a 位 元 時 為 0 與 1 的 機 率, 2 σ 代 表 雜 訊 參 數, 所 以 接 收 到 的 codeword 每 個 位 元 機 率 可 表 示 為 1 ~ L L n 當 H 矩 陣 中 H mn, = 1時 設 q, mn = L, 即 對 應 矩 陣 中 元 素 為 1 的 機 率 值 n (2) 計 算 位 元 節 點 至 檢 查 節 點 的 機 率 資 訊 每 個 檢 查 節 點 均 會 收 到 所 連 結 位 元 節 點 的 機 率 資 訊, 設 這 些 機 率 值 為 q mn,, 但 因 為 統 計 這 些 機 率 不 包 括 本 身 的 機 率, 所 以 表 示 為 16

r ps = ( q ) mn, mn, ' n' L( m)\ n (28) = sign( q ) sign( q ) φφ ( ( q ) φ( q )) mn, mn, ' mn, ' mn, n' L( m) n' L( m) x x e + 1 where φ( x) = ln tanh( ) = ln and φ( φ( x))= x x 2 e 1 (3) 計 算 檢 查 節 點 至 位 元 節 點 的 機 率 資 訊 每 個 位 元 節 點 接 收 來 自 所 連 結 檢 查 節 點 的 機 率 資 訊 q = pc( pc ( r ), L ) = L + r (29) mn, m', n n n m', n m' M( n)\ m m' M( n)\ m (4) 計 算 位 元 節 點 本 身 的 機 率 資 訊 與 解 碼 q = pc( pc ( r ), L ) = L + r (30) n m, n n n m, n m M( n) m M( n)\ m 得 到 的 q 進 行 判 斷 : c n n 1 if qn 0 = 0 if qn < 0 (5) 重 複 遞 迴 運 算 T 如 果 解 出 來 的 codeword 滿 足 c H = 0 則 解 碼 結 束, 否 則 重 覆 從 步 驟 (2) 開 始 直 到 解 出 正 確 的 碼 或 達 到 遞 迴 次 數 的 上 限 值 17

2.3-2 Min-Sum Algorithm 由 式 (20) 可 改 寫 成 ps2( L, L ) = ps2( L L ) 1 2 1 2 L + L L L = 2 2 1 2 1 2 ln(cosh( )) ln(cosh( )) L + L L L 1+ e ln 2 2 1+ e 1 2 1 2 = + L + L 1 2 L L 1 2 = sign L sign L L L + ( 1) ( 2) min( 1, 2 ) ln 1 sign( L ) sign( L ) min( L, L ) 1 2 1 2 1+ e + e L + L 1 2 L L 1 2 (31) 此 式 將 複 雜 的 運 算 式 φ 簡 化 成 最 小 值 運 算, 雖 然 有 效 降 低 運 算 量 但 也 失 去 部 份 的 效 能, 因 為 φ ( x) 中 x 值 越 小 時 φ 值 越 大, 若 同 時 有 4 個 最 小 值 大 小 排 列 為 x4>x3>x2>x1, 則 算 式 只 會 選 擇 x1 卻 失 去 x2 x3 x4 帶 來 效 能 偏 差, 所 以 通 常 Min-Sum Algorithm 與 Sum-Product Algorithm 在 code length 越 長 時 效 能 影 響 越 大 2.3-3 Min-Sum Correction-Factor [20] 為 了 改 善 Min-Sum Algorithm 的 效 能 損 失, 在 式 (31) 中 省 略 的 部 分 1+ e 1 2 L1+ L2 L1 L2 ln = ln(1 + e ) ln(1 + e ) L1 L2 1+ e L + L (32) 此 參 數 稱 為 Correction-Factor, 可 經 由 查 表 法 LUT 算 出 加 入 此 項 參 數 後 能 修 正 數 值, 使 解 碼 效 能 更 接 近 Sum-Product Algorithm Min-Sum Algorithm 的 解 碼 流 程 如 下 : 18

(1) 初 始 化 (Initialization) 設 L n P( yn xn = 0) 2 = ln = ( 1) 2 P y x = σ n n y n (33) (2) 計 算 位 元 節 點 至 檢 查 節 點 的 機 率 資 訊 r ps = ( q ) mn, mn, ' n' L( m)\ n min = sign( q ) sign( q ) { q } mn, mn, ' mn, n' L( m) n' L( m) (34) (3) 計 算 檢 查 節 點 至 位 元 節 點 的 機 率 資 訊 q = pc( pc ( r ), L ) = L + r (35) mn, m', n n n m', n m' M( n)\ m m' M( n)\ m (4) 計 算 位 元 節 點 本 身 的 機 率 資 訊 與 解 碼 q = pc( pc ( r ), L ) = L + r (30) n m, n n n m, n m M( n) m M( n)\ m 得 到 的 q 進 行 判 斷 : c n n 1 if qn 0 = 0 if qn < 0 (5) 重 複 遞 迴 運 算 T 如 果 解 出 來 的 codeword 滿 足 c H = 0 則 解 碼 結 束, 否 則 重 覆 從 步 驟 (2) 開 始 直 到 解 出 正 確 的 碼 或 達 到 遞 迴 次 數 的 上 限 值 19

第 三 章 傳 統 消 去 迴 圈 演 算 法 (Cycle Elimination) 一 般 來 說 SPA 演 算 法 具 有 優 異 的 解 碼 能 力, 在 解 碼 的 過 程 中 因 為 訊 息 經 由 edge 互 相 傳 遞 而 造 成 訊 息 的 相 依 關 係, 再 加 上 LDPC 解 碼 屬 於 遞 迴 式 的 演 算 法, 希 望 訊 息 傳 遞 時 盡 可 能 的 獨 立, 如 果 在 位 元 檢 查 矩 陣 中 含 有 許 多 短 迴 圈 (cycle) 會 使 得 收 斂 速 度 變 慢 且 解 碼 效 能 變 低, 因 此 設 計 具 有 長 迴 圈 架 構 的 位 元 檢 查 矩 陣 能 使 訊 息 之 間 相 依 關 係 減 低 進 而 獲 得 效 能 提 升 此 章 將 介 紹 傳 統 消 去 迴 圈 演 算 法 (Cycle Elimination) [21], 採 用 搜 尋 短 迴 圈 並 打 斷 迴 圈 的 機 制 產 生 矩 陣, 並 同 時 擴 展 每 個 元 素 形 成 Block-LDPC 矩 陣 格 式 有 利 於 VLSI 硬 體 上 編 碼 與 解 碼 的 實 現 [22][23] 1 1 1 Cycle-4 Cycle-6 1 1 1 1 1 圖 3-1 Cycle 表 示 方 法 3.1 基 本 矩 陣 與 擴 展 矩 陣 中 最 小 的 cycle 定 義 為 Girth, 一 般 而 言 當 Girth=8 以 上 有 較 好 的 解 碼 效 能, 也 就 是 矩 陣 中 不 會 形 成 如 圖 3-1 所 示 cycle-4 或 6 目 前 有 幾 種 演 算 法 能 增 加 矩 陣 中 Girth 長 度, 如 Progressive Edge-Growth(PEG)[24] Bit-Filling [25] 等 演 算 法, 但 產 生 的 矩 陣 中 非 零 的 元 素 亂 數 排 列, 對 實 現 硬 體 上 較 為 困 難 複 雜 度 也 相 對 增 加 20

為 了 利 於 硬 體 實 現 並 採 用 平 行 化 的 概 念 以 達 到 高 吞 吐 的 輸 出, 產 生 位 元 檢 查 矩 陣 時 採 用 Block-LDPC[26] 架 構, 如 圖 3-2 所 示 先 準 備 Ms x Mn 大 小 的 基 本 矩 陣 (Base matrix), 再 按 照 code length 所 需 的 大 小 展 開 成 p.ms x p.mn, 其 中 每 個 0 展 開 為 p x p 大 小 的 零 矩 陣, 每 個 1 展 開 為 p x p 大 小 的 單 位 矩 陣 擴 展 基 本 矩 陣 除 了 對 硬 體 實 現 有 好 處 外, 同 時 也 能 對 效 能 有 所 助 益, 因 為 擴 展 後 的 矩 陣 Girth 一 定 大 於 或 等 於 基 本 矩 陣 的 Girth, 此 特 性 也 是 支 持 消 去 迴 圈 演 算 法 的 主 要 理 論, 經 由 擴 展 的 過 程 中 位 移 單 位 矩 陣 達 到 打 斷 Cycle 的 效 果 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 Ms x Mn T 0 0 0 T 0 0 T 0 T 0 0 T 0 0 0 0 T p.ms x p.mn 圖 3-2 擴 展 矩 陣 示 意 圖 3.2 形 成 迴 圈 之 條 件 與 限 制 由 上 一 節 得 知 用 位 移 單 位 矩 陣 打 斷 短 迴 圈, 而 形 成 迴 圈 中 每 一 個 元 素 位 移 情 況 以 圖 3-3 舉 例 說 明 21

(1,1) 1 1 1 1 1 1 1 1 (1,2) (2,1) 1 1 1 1 1 1 1 1 (2,2) 圖 3-3 擴 展 矩 陣 之 後 迴 圈 情 況 以 圖 3-3 為 例, 將 基 本 矩 陣 中 每 個 元 素 擴 展 成 4 x 4 的 小 區 塊 矩 陣, 每 個 區 塊 都 是 單 位 矩 陣 位 移 之 後 形 成 的,P 為 向 右 位 移 量, 故 P(1,1)=1 P(1,2)=0 P(2,1)=3 P(2,2)=2, 得 到 上 圖 形 成 4 條 長 度 為 4 的 迴 圈, 此 種 迴 圈 通 稱 為 cycle-4, 同 理 長 度 為 六 的 迴 圈 通 稱 為 cycle-6 以 此 類 推, 而 任 何 矩 陣 中 最 小 的 迴 圈 為 cycle-4, 為 了 探 討 各 元 素 位 移 量 與 形 成 迴 圈 之 間 的 關 係, 用 數 學 公 式 來 推 導 證 明 如 下 將 同 一 行 中 兩 個 元 素 歸 類 一 組, 如 P(1,1) 和 P(2,1) 為 一 組 P(1,2) 和 P(2,2) 為 一 組, 在 [27] 中 定 義 : Δ P = P P (31) i, j > i, m i, j i, m, 則 Δ P1,1 > 2,1 = P1,1 P2,1 = 3 1= 2 (32) Δ P2,2 > 1,2 = P2,2 P1,2 = 0 2= 2 (33) 22

, 最 後 把 式 (32) 和 式 (33) 相 加 得 到 ( Δ P ) = P 1,2 P 2,2 = (2) + ( 2) = 0 V (34), 式 3-5 中 的 V 代 表 vertical shift-value drops 上 述 是 以 cycle length=4 為 例, Δ P 相 減 的 順 序 如 圖 3-4 所 示, 從 左 上 方 的 元 素 點 出 發 順 時 鐘 或 逆 時 鐘 繞 回 原 點, 保 持 方 向 一 致 性, 不 管 是 Cycle 4 6 8 都 相 同 P(1,1)=1 2 P(1,2)=0-2 P(1,1)=0 2 P(1,2)=3-1 P(2,2)=4 P(2,3)=3 P(1,1)=3 P(2,2)=2-1 P(3,1)=2 P(3,3)=4 圖 3-4 計 算 位 移 量 的 方 向 示 意 圖 因 此 我 們 可 以 直 接 用 數 學 計 算 位 移 量 和 形 成 迴 圈 之 間 的 關 係 首 先 如 圖 3-5 所 示 把 展 開 之 後 的 方 塊 矩 陣 切 成 兩 部 份, 每 一 個 1 的 坐 標 都 可 表 示 為 下 式 : ( ii, + P 0 // L), 當 0 i< L P ( 左 上 方 ) ( ii, + P L), 當 L P i L 1 ( 右 下 方 ) (35), 將 式 (35) 合 併 成 (, ii+ P 0// L) (36) 23

, 對 應 圖 3-6 中 表 示 為 ( s, s + P 0// L) (37) i i i,1, 又 得 知 H(1,2) 與 H(2,1) 有 相 同 的 行,H(1,1) 與 H(g,2) 有 相 同 的 行, 以 此 類 推 得 到 下 列 的 式 子 : s + P (0// L) = s + P (0// L) 1 1,2 2 2,1 s + P (0// L) = s + P (0// L) 2 2,2 3 3,1 s + P (0// L) = s + P (0// L) g g,2 1 1,1 (38), 將 上 式 加 總 得 到 ( P P ) + ( P P ) + + ( P P ) = ( y x)( L) (39) 1,2 2,1 2,2 3,1 g,2 1,1, 整 理 得 ( Δ P ) = k L ( k = 0, ± 1, ± 2,, ± g ) V (40) 上 式 為 判 斷 位 移 量 與 迴 圈 的 準 則 稱 做 Cycle constraint, 其 中 g 值 為 cycle 長 度 的 一 半, 例 如 cycle length=6 則 g=3 等 式 成 立 的 話 則 會 形 成 迴 圈, 因 此 以 下 的 內 容 若 稱 滿 足 constraint 則 表 示 等 式 不 成 立, 不 滿 足 constraint 則 表 示 等 式 成 立 24

圖 3-5 方 塊 矩 陣 之 元 素 坐 標 ( 節 錄 自 [21] Fig.5) 圖 3-6 各 方 塊 矩 陣 迴 圈 連 結 示 意 圖 ( 節 錄 自 [21] Fig.6) 25

3.3 傳 統 消 去 迴 圈 演 算 法 這 裡 以 條 列 式 介 紹 傳 統 的 消 去 迴 圈 演 算 法, 並 分 析 該 演 算 法 之 優 缺 點 及 改 進 的 目 標, 並 在 下 一 章 描 述 改 良 的 演 算 法 3.3-1 演 算 法 流 程 首 先 準 備 好 基 本 矩 陣, 矩 陣 中 每 個 1 含 有 一 個 清 單, 清 單 是 用 來 儲 存 式 (40) 的 constraint, 用 來 判 斷 是 否 有 打 斷 或 重 新 回 復 Cycle 接 著 開 始 搜 尋 Cycle length 為 4 6 8 之 迴 圈, 從 最 左 邊 的 行 (column) 開 始 往 右 搜 尋, 並 將 每 一 個 找 到 的 迴 圈 記 錄 在 清 單 中 以 便 之 後 拿 來 判 斷 使 用, 以 程 式 模 擬 結 果 得 知 Cycle length 越 大 其 個 數 增 加 的 越 快 當 找 出 任 何 迴 圈 時, 開 始 對 此 迴 圈 中 每 個 1 做 constraint 的 判 斷 以 打 斷 迴 圈, 因 為 擴 展 成 L X L 的 區 塊 矩 陣 中 位 移 量 限 制 為 [0, L-1], 為 了 使 位 移 增 加 的 速 度 減 緩, 先 將 每 個 1 的 初 始 位 移 值 儲 存, 每 個 1 檢 查 自 己 的 constraint 是 否 符 合, 若 不 符 合 則 位 移 值 加 1 ( P, = P, + 1) 直 到 滿 足 所 有 constraint, 找 出 i j i j 此 迴 圈 中 位 移 總 合 最 小 的 1 保 留 此 值, 其 它 的 1 回 存 原 值 以 圖 3-7 為 例,P 代 表 總 位 移 值 括 弧 內 代 表 此 迴 圈 檢 查 constraint 所 增 加 的 值, 選 擇 最 小 的 總 位 移 量 (36) 並 回 存 其 它 值 P=72(4) 68 P=36(9) P=56(1) P=45(5) 55 40 P=50(2) 48 P=60(0) 60 圖 3-7 傳 統 消 去 迴 圈 演 算 法 位 移 動 作 之 圖 例 26

3.3-2 演 算 法 分 析 與 比 較 傳 統 消 去 迴 圈 演 算 法 是 找 到 一 個 迴 圈 就 會 進 行 位 移 的 動 作, 以 消 去 目 前 找 到 的 迴 圈 再 進 行 下 一 個 迴 圈 消 除, 此 種 作 法 類 似 暴 力 法, 將 所 有 的 迴 圈 跑 過 一 遍 並 檢 查 迴 圈 中 每 個 元 素 的 constraint, 再 做 比 較 位 移 最 小 值 的 工 作, 因 此 運 算 量 非 常 可 觀, 下 表 為 模 擬 圖 4-8 的 矩 陣 的 結 果 Cycle-4 Cycle-6 Cycle-8 執 行 迴 圈 總 量 81 924 17811 平 均 單 一 迴 圈 檢 查 constraint 數 量 5.54 142.14 4262.44 總 合 448.74 131337.36 75918319 表 3-1 估 計 運 算 的 constraint 總 量 表 3-1 為 code rate=1/2 18 x 36 非 正 規 基 本 矩 陣, 其 中 包 含 117 個 1 該 演 算 法 從 最 左 邊 的 行 (column) 開 始 往 右 動 作, 可 避 免 重 覆 的 迴 圈 運 算, 由 上 表 觀 察 出 cycle 8 數 量 比 cycle 4 6 高 出 許 多, 且 因 為 每 執 行 一 次 消 去 迴 圈 位 移 的 動 作, 就 必 須 把 迴 圈 中 每 個 元 素 1 的 constraint 都 計 算 過 一 遍, 所 以 增 加 不 少 運 算 量 例 如 cycle-6 就 要 檢 查 6 個 點, 相 對 增 加 6 倍 constraint 的 運 算, 故 在 cycle-8 中 平 均 每 cycle 需 檢 查 3253 個 constraint 表 3-2 分 別 列 出 在 cycle 4 6 8 中 每 個 constraint 乘 法 與 加 法 的 總 數, 若 分 別 乘 上 表 3-1 constraint 的 數 量 即 為 整 體 演 算 法 的 運 算 量, 因 此 如 果 把 constraint 定 在 cycle-8 將 會 耗 費 相 當 多 的 運 算 雖 然 傳 統 消 去 迴 圈 演 算 法 的 計 算 方 式 需 要 大 量 運 算 量 及 時 間, 但 是 位 移 打 斷 迴 圈 的 效 果 全 面 且 仔 細 27

Cycle-4 Cycle-6 Cycle-8 加 法 數 3 5 7 乘 法 數 5 7 9 表 3-2 每 條 constraint 的 加 減 法 總 量 28

第 四 章 改 良 式 消 去 迴 圈 演 算 法 本 章 節 將 介 紹 改 良 式 演 算 法, 根 據 元 素 包 含 的 迴 圈 數 高 低 取 得 優 先 次 序, 執 行 位 移 打 斷 迴 圈 的 動 作, 並 充 分 利 用 每 次 能 打 斷 Cycle 的 機 會 我 將 以 不 同 的 基 本 矩 陣 做 說 明, 除 了 大 幅 改 善 位 移 消 去 之 運 算 量 及 時 間, 在 低 擴 展 倍 數 時 也 能 有 效 的 將 迴 圈 數 量 減 到 最 低 4.1 搜 尋 迴 圈 與 演 算 法 流 程 此 節 介 紹 搜 尋 迴 圈 的 方 式, 詳 細 說 明 改 良 式 消 去 迴 圈 演 算 法 的 流 程 與 架 構, 並 在 下 一 節 分 析 演 算 法 的 模 擬 結 果 4.1-1 搜 尋 迴 圈 方 法 首 先 準 備 基 本 矩 陣, 先 找 出 所 有 元 素 1 儲 存 各 種 資 訊 於 陣 列 中, 如 表 4-1 這 些 包 含 上 下 左 右 1 的 個 數 坐 標 及 位 移 資 訊, 而 演 算 法 中 不 管 是 搜 尋 迴 圈 或 是 權 重 機 制 都 是 從 左 上 方 的 點 開 始 往 右 搜 尋 到 底 後 換 列, 如 圖 4-1 所 示, 直 到 所 有 的 點 都 被 搜 尋 過, 如 此 一 來 保 持 演 算 法 執 行 的 方 向 統 一 避 免 重 覆, 以 下 用 條 列 式 的 方 式 介 紹 搜 尋 方 法 與 順 序, 並 以 圖 4-2 輔 助 說 明 29

(x,y) 坐 標 上 端 個 數. 坐 標 下 端 個 數. 坐 標 左 端 個 數. 坐 標 右 端 個 數. 坐 標 Cycle 個 數. 坐 標 位 移 量 位 移 旗 標 表 4-1 每 個 元 素 為 1 之 陣 列 1 2 3 4 1 1 1 1 1 1 1 1 1 圖 4-1 搜 尋 時 之 方 向 示 意 圖 1. 從 左 上 方 的 原 點 P(1,1) 出 發, 往 右 及 往 下 搜 尋 找 到 P(1,2) 及 P(4,1) 並 標 記 為 第 一 層, 其 中 P(1,2) 與 原 點 有 相 同 的 列 數 P(4,1) 與 原 點 有 相 同 的 行 數 2. 從 P(1,2) 往 上 或 下 搜 尋 得 到 P(2,2), 而 P(4,1) 往 右 搜 尋 得 到 P(4,4), 將 P(2,2) 及 P(4,4) 標 記 為 第 二 層, 其 中 P(1,2) 與 P(2,2) 有 相 同 的 行 數 P(4,1) 與 P(4,4) 有 相 同 的 列 數 3. 從 P(2,2) 往 右 或 左 搜 尋 得 到 P(2,3), 而 P(4,4) 往 上 或 往 下 搜 尋 得 到 P(3,4), 將 P(2,3) 及 P(3,4) 標 記 為 第 三 層, 其 中 P(2,2) 與 P(2,3) 有 相 同 的 列 數 P(3,4) 與 P(4,4) 有 相 同 的 行 數 4. 最 後 搜 尋 全 部 的 點, 若 有 一 點 P(X,Y) 與 P(1,2) 有 相 同 的 行 數 並 且 與 P(4,1) 有 相 同 的 列 數 則 形 成 Cycle-4; 若 有 一 點 P(X,Y) 與 P(2,2) 有 相 同 的 列 數 並 30

且 與 P(4,4) 有 相 同 的 行 數 則 形 成 Cycle-6; 若 有 一 點 P(X,Y) 與 P(2,3) 有 相 同 的 行 數 並 且 與 P(3,4) 有 相 同 的 列 數 則 形 成 Cycle-8 P(1,1) P(1,2) P(2,2) P(2,3) P(X,Y) P(3,4) P(4,1) P(4,4) 圖 4-2 搜 尋 迴 圈 示 意 圖 搜 尋 迴 圈 時 有 兩 點 需 要 特 別 注 意 : (1) 在 階 層 搜 尋 時, 必 須 避 免 不 同 階 層 搜 尋 到 相 同 的 點, 這 種 現 在 尤 其 在 cycle-8 時 更 容 易 發 生 如 圖 4-3 所 示, 空 心 的 點 為 原 點, 在 往 右 搜 尋 時 會 先 找 到 A 點, 而 同 樣 地 從 原 點 依 序 往 下 往 右 及 往 上 也 會 找 到 A 點, 造 成 同 一 點 搜 尋 兩 次 的 情 況, 因 此 在 搜 尋 過 程 中 設 定 所 有 點 的 坐 標 均 不 相 等 即 可 (2) 搜 尋 的 方 向 不 能 超 過 起 始 點 左 側 的 行 數, 如 圖 4-4 以 空 心 點 當 原 點 時, 搜 尋 到 第 三 層 也 就 是 虛 線 框 起 來 的 部 分, 這 兩 點 行 數 已 小 於 原 點 ; 而 以 B 點 當 原 點 搜 尋 時 也 會 搜 尋 到 一 樣 的 迴 圈, 造 成 同 一 個 迴 圈 被 搜 尋 至 兩 次, 所 以 要 以 原 點 的 行 數 做 標 準, 任 何 搜 尋 的 路 徑 只 能 在 原 點 的 右 半 側 31

A 圖 4-3 造 成 同 一 點 搜 尋 兩 次 之 範 例 此 行 數 為 基 準 時 已 搜 尋 過 B 圖 4-4 搜 尋 時 路 徑 超 過 原 點 左 半 邊 之 範 例 4.1-2 演 算 法 流 程 與 架 構 前 一 章 介 紹 了 傳 統 式 迴 圈 演 算 法, 雖 然 過 程 是 循 序 式 的 將 迴 圈 打 斷, 但 運 算 量 及 複 雜 度 很 高, 所 以 我 們 提 出 改 良 式 消 去 迴 圈 演 算 法, 除 了 有 效 打 斷 消 除 迴 圈 之 外, 依 照 每 一 點 包 含 迴 圈 的 數 量 訂 為 權 重 值, 按 權 重 高 低 消 去 迴 圈 以 簡 化 運 算 量 優 先 權 消 去 迴 圈 演 算 法 流 程 : 32

(1) 找 出 基 本 矩 陣 中 為 1 的 元 素, 並 創 造 一 個 空 陣 列 儲 存 各 種 資 訊 (2) 清 空 元 素 1 中 全 部 參 數 的 初 始 值 (3) 從 最 左 上 角 的 1 開 始, 找 出 所 有 1 的 (x,y) 坐 標 及 上 下 左 右 四 個 方 向 為 1 的 個 數 及 坐 標, 並 儲 存 在 陣 列 中 供 搜 尋 迴 圈 使 用 (4) // 搜 尋 Cycle-4 6 8, 同 時 將 每 條 迴 圈 的 坐 標 及 資 訊 存 入 陣 列 (5) 從 原 點 H(i,j) 往 右 往 下 找 到 兩 點 H(i,k) H(m,j), 若 有 一 點 坐 標 為 H(m,k) 則 此 4 點 形 成 cycle-4 (6) for H(i,k) 上 方 及 下 方 的 1 為 H(p,k) H(m,j) 右 方 的 1 為 H(m,n), 若 有 一 點 坐 標 為 H(p,n) 則 此 6 點 形 成 cycle-6 (7) for H(p,k) 右 方 及 左 方 的 1 為 H(p,r) H(m,n) 上 方 及 下 方 的 1 為 H(s,n), 若 有 一 點 坐 標 為 H(s,r) 則 此 8 點 形 成 cycle-8 (8) end (9) end (10) // 優 先 權 一 次 式 消 去 迴 圈 法 (11) while ( 元 素 1 最 大 迴 圈 數 >0) (12) if (( 某 一 點 元 素 迴 圈 數 == 最 大 迴 圈 數 )&&( 位 移 旗 標 ==0)) (13) for ( 該 元 素 所 有 可 位 移 的 值 P = (1~L-1) ) (14) 檢 查 該 元 素 包 含 的 constraint, 分 別 記 錄 滿 足 constraint 及 不 滿 足 的 數 量 ( 這 邊 定 義 參 數 為 rig 與 wro) (15) if (rig > wro) (16) 比 較 該 元 素 所 有 的 位 移 值 並 取 P 使 (rig-wro) 有 最 大 值 (17) else (18) 該 元 素 位 移 值 P=0 ; (19) end (20) 該 元 素 的 位 移 旗 標 設 為 1; 33

(21) 更 新 基 本 矩 陣 的 最 大 迴 圈 數 ; (22) elseif (( 某 一 點 元 素 迴 圈 數 == 最 大 迴 圈 數 )&&( 位 移 旗 標 ==1)) (23) 跳 過 並 尋 找 下 一 個 含 有 相 同 最 大 迴 圈 數 之 元 素 ; (24) else (25) 最 大 迴 圈 數 = 最 大 迴 圈 數 -1; (26) end (27) end (28) end 演 算 法 流 程 圖 : 附 註 : 準 備 基 本 矩 陣 1 s: 矩 陣 中 元 素 為 1 的 點 P: 元 素 1 的 位 移 值 rig: 滿 足 constraint 總 數 搜 尋 Cycle 與 記 錄 wro: 不 滿 足 constraint 總 數 迴 圈 最 大 值 >0 No 演 算 法 結 束 Yes 搜 尋 1 s 的 迴 圈 數 No 迴 圈 最 大 值 -1 No 是 否 最 大 值? Yes 位 移 旗 標 =0? Yes 代 入 P 檢 查 constraint 設 P=0 位 移 旗 標 =1 更 新 迴 圈 最 大 值 位 移 旗 標 =1 rig > wro Yes 取 P 使 (rig-wro) 有 最 大 值 No 34

演 算 法 分 段 以 行 數 說 明 與 分 析 如 下 : (1)~(3) 行 : 首 先 準 備 一 個 基 本 矩 陣, 所 有 在 矩 陣 中 的 1 均 產 生 如 表 4-1 的 清 單 並 將 初 始 值 歸 零 如 圖 4-1 從 矩 陣 的 左 上 角 開 始 搜 尋 1 的 位 置 記 錄 坐 標, 並 同 時 找 出 上 下 左 右 四 個 方 向 的 1, 將 其 坐 標 與 數 量 儲 存 因 為 每 個 元 素 包 含 許 多 cycle, 每 條 cycle 都 會 轉 成 constraint 存 於 清 單 (4)~(9) 行 : 每 一 點 包 含 4 個 方 向 的 資 訊, 我 們 利 用 此 資 訊 尋 找 迴 圈 在 4.1-1 節 說 明 了 搜 尋 方 法, 但 此 方 法 只 適 用 於 專 門 搜 尋 Cycle-4 6 8 的 情 況, cycle 的 基 本 定 義 為 從 原 點 出 發 繞 過 一 條 封 閉 的 路 徑 回 到 原 點, 且 每 一 個 節 點 不 能 通 過 第 2 次, 所 以 提 出 兩 點 方 法 避 免 找 到 錯 誤 或 重 覆 的 cycle 然 而 這 邊 所 搜 尋 是 未 擴 展 之 前 的 基 本 矩 陣, 經 由 模 擬 結 果 證 明 圖 4-3 的 情 形 在 擴 展 矩 陣 之 後 有 可 能 造 成 新 的 cycle-8, 如 果 我 未 考 慮 及 搜 尋 到 此 種 迴 圈, 即 便 程 式 結 果 指 出 已 打 斷 所 有 迴 圈, 新 的 擴 展 矩 陣 還 會 有 未 打 斷 的 cycle 產 生 為 了 使 程 式 能 完 全 打 斷 所 有 的 迴 圈, 提 出 兩 條 輔 助 方 法 : (1) 以 圖 4-5 當 作 範 例, 若 藍 色 AB 共 點 則 勢 必 造 成 紅 色 CD 共 點, 反 之 亦 然 ; 這 並 不 符 合 構 成 迴 圈 的 形 式, 因 為 當 搜 尋 至 A B 點 時 下 一 步 是 往 水 平 方 向 搜 尋 而 找 到 C D 點, 找 到 C D 點 後 下 一 步 往 垂 直 方 向 搜 尋, 若 C D 共 點 的 話 則 無 法 找 到 搜 尋 的 路 徑, 所 以 除 了 讓 A B 和 C D 不 共 點 之 外 取 消 其 它 避 免 共 點 的 限 制 (2) 在 [13] 文 獻 中 提 到 所 有 搜 尋 的 點 的 行 數 必 須 大 於 原 點 的 行 數 ( d > j ), 但 這 種 說 法 並 不 周 延, 我 的 模 擬 實 驗 出 現 了 一 種 情 況, 以 圖 4-6 所 示 藍 點 為 原 點, 各 點 的 數 字 指 移 位 量, 在 此 種 情 形 下 原 點 被 搜 尋 到 兩 次, 利 用 式 3-11 得 到 Δ P = 0 + (14) + (14) + ( 28) = 0, 代 表 在 擴 展 矩 陣 後 會 形 成 新 的 cycle-8, 並 不 符 合 作 者 演 算 法 中 的 描 述, 因 此 我 修 改 為 所 有 點 的 行 數 必 須 大 於 或 等 於 原 點 的 行 數 35

A C B D 圖 4-5 若 A B 共 點 則 C D 共 點 將 無 法 找 到 搜 尋 路 徑 之 圖 例 0 0 原 點 14 28 0 0 0 圖 4-6 原 點 被 搜 尋 到 兩 次 之 範 例 (10)~(28) 行 : 權 重 指 元 素 1 所 包 含 迴 圈 總 數, 這 也 是 本 演 算 法 主 要 的 精 神, 依 照 每 個 1 不 同 權 重 來 執 行 迴 圈 消 去 的 優 先 次 序 當 初 的 構 想 是 當 該 元 素 擁 有 最 高 權 重 時, 能 一 次 打 斷 迴 圈 的 數 量 必 會 高 於 其 它 元 素 首 先 找 出 具 有 最 高 權 重 的 元 素, 接 著 把 所 有 的 位 移 值 (1~L-1) 代 入 constraint 表, 統 計 各 別 滿 足 及 不 滿 足 constraint 的 總 數, 首 要 條 件 為 滿 足 的 總 量 必 須 大 於 不 滿 足 的 總 量, 再 來 選 擇 讓 兩 者 相 差 最 大 的 位 移 值, 也 就 是 該 位 移 值 能 打 斷 更 多 的 迴 圈 更 少 重 新 連 結 的 迴 圈, 充 份 利 用 每 一 次 打 斷 的 機 會 另 外 再 準 備 1 張 表 單, 把 滿 足 的 constraint 搬 到 此 表 單 不 滿 足 的 維 持 在 原 表 單, 如 圖 4-7 所 示 方 便 處 理 迴 圈 資 訊 與 數 量 若 滿 足 的 總 量 小 於 不 滿 足 的 總 量, 則 該 元 素 位 移 值 設 為 零, 繼 36

續 往 下 一 個 擁 有 高 優 先 權 的 元 素 動 作, 最 後 只 要 有 判 斷 執 行 該 元 素 時 均 拉 起 位 移 旗 標 表 示 已 處 理 過 每 執 行 完 一 次 位 移 動 作 時, 程 式 將 重 新 整 理 取 得 最 新 的 優 先 權 順 序, 再 執 行 位 移 動 作 盡 可 能 打 斷 所 有 的 迴 圈 因 為 整 體 演 算 法 執 行 到 最 後 才 會 將 基 本 矩 陣 擴 展, 不 可 能 每 次 統 計 最 新 優 先 權 時 執 行 搜 尋 迴 圈 的 動 作, 於 是 在 這 邊 使 用 一 個 技 巧, 直 接 讀 取 圖 4-7 中 未 被 打 斷 迴 圈 的 數 量, 就 可 快 速 且 精 準 地 得 到 各 元 素 所 剩 餘 的 迴 圈 數 Cycle_Information Delete_Information 滿 足 即 打 斷 Cycle 未 被 打 斷 的 Cycle 資 訊 及 數 量 已 被 打 斷 的 Cycle 資 訊 及 數 量 不 滿 足 即 回 復 Cycle 圖 4-7 表 單 處 理 constraint 動 向 之 示 意 圖 4.2 模 擬 結 果 與 分 析 以 下 將 以 非 正 規 矩 陣 (irregular matrix) 做 模 擬 與 分 析, 在 [29] [30] 提 出 設 計 良 好 的 非 規 則 矩 陣 解 碼 效 能 比 規 則 矩 陣 好, 而 規 則 矩 陣 的 好 處 為 簡 化 設 計 硬 體 的 複 雜 度, 不 過 隨 著 超 大 型 積 體 電 路 的 進 步, 現 在 的 應 用 大 多 採 用 非 規 則 矩 陣 以 達 到 更 好 的 效 能 模 擬 矩 陣 的 參 數 性 質 列 於 表 4-2, 採 用 [24] 文 獻 中 的 方 法 建 構 而 成 的 基 本 矩 陣, 此 矩 陣 與 表 3-1 所 做 分 析 模 擬 之 矩 陣 相 同, 因 此 稍 後 有 兩 種 演 算 法 模 擬 的 數 據 比 較 37

Code Rate 1/2 Variable node degree 2,3,7 Check node degree 5,6 Base matrix size 18x36 表 4-2 非 正 規 基 本 矩 陣 各 種 參 數 圖 4-8 為 code rate=1/2 之 非 規 則 矩 陣, 大 小 為 18x36, 位 元 節 點 的 權 重 分 別 為 { 2,2,,2,3,,3,7,,7 }, 矩 陣 中 共 有 117 個 1, 可 觀 察 出 矩 陣 的 右 半 段 1 的 分 佈 較 為 密 集, 表 示 這 些 點 含 有 大 量 的 迴 圈, 由 程 式 分 析 顯 示 每 一 個 元 素 1 含 有 cycle-4 6 8 平 均 值 達 到 1268 當 基 本 矩 陣 能 擴 展 的 倍 數 越 大, 即 代 表 有 更 多 的 位 移 值 選 擇 而 打 斷 更 多 的 迴 圈, 模 擬 顯 示 擴 展 倍 數 L 需 要 235 方 能 打 斷 所 有 迴 圈 圖 4-8 Code Rate=1/2 Irregular Matrix 38

迴 圈 類 型 Cycle-4 Cycle-6 Cycle-8 總 數 324 5,544 142,488 每 元 素 平 均 值 2.77 47.38 1217.84 表 4-3 Code Rate=1/2 矩 陣 中 各 種 迴 圈 總 數 與 平 均 為 什 麼 優 先 權 的 機 制 能 更 有 效 率 打 斷 迴 圈? 因 為 當 一 個 元 素 為 1 的 點 具 有 最 高 迴 圈 數 量 時, 代 表 能 一 次 打 斷 迴 圈 的 數 量 越 多, 迴 圈 的 總 數 是 固 定 的, 如 果 能 在 每 次 位 移 動 作 時 能 打 斷 最 多 的 迴 圈, 不 僅 加 快 迴 圈 消 去 的 速 度, 也 能 減 少 執 行 元 素 位 移 動 作 的 次 數 圖 4-9 為 每 次 執 行 完 該 元 素 位 移 動 作 後, 所 有 元 素 之 最 大 迴 圈 值 的 數 據, 開 始 執 行 10 次 之 內 的 最 大 迴 圈 值 有 明 顯 減 少, 故 每 次 動 作 都 能 打 斷 最 多 的 迴 圈 數 量, 即 可 看 出 採 用 權 重 優 先 打 斷 迴 圈 的 方 法 收 到 良 好 的 成 效, 而 超 過 20 次 後 因 為 最 大 迴 圈 值 變 低 而 打 斷 的 迴 圈 數 量 有 限, 因 此 曲 線 較 為 平 緩, 總 共 花 費 53 次 執 行 遞 迴 次 數 將 所 有 Cycle-4 6 8 消 除 所 有 元 素 之 最 大 迴 圈 值 3500 3000 2500 2000 1500 1000 500 0 1 6 11 16 21 26 31 36 41 46 51 元 素 執 行 位 移 動 作 之 次 數 圖 4-9 每 次 執 行 位 移 動 作 後 所 有 元 素 最 大 迴 圈 值 之 長 條 圖 39

圖 4-10 為 每 次 執 行 位 移 動 作 後 每 個 元 素 的 迴 圈 平 均 值, 在 前 十 次 元 素 位 移 消 去 的 動 作 時, 所 有 剩 下 迴 圈 的 平 均 值 已 從 1268 降 至 361, 下 降 的 幅 度 達 71.5%, 再 次 證 明 以 優 先 權 打 斷 的 機 制 獲 得 了 成 效, 除 此 之 外 執 行 元 素 位 移 的 次 數 減 少 後, 運 算 量 相 對 減 低 許 多, 在 表 3-1 已 討 論 過 相 同 矩 陣 利 用 傳 統 迴 圈 消 去 演 算 法 所 花 費 的 運 算 量, 而 這 邊 也 將 確 切 的 運 算 量 列 於 表 4-4, 由 於 表 3-1 是 以 constraint 的 數 量 做 為 基 準, 而 搜 尋 迴 圈 的 方 法 差 不 多, 故 這 邊 也 是 以 constraint 的 數 量 當 作 比 較 的 單 位 原 作 者 的 演 算 法 每 遇 到 迴 圈 就 搜 尋 此 迴 圈 中 所 有 的 1 並 檢 查 constraint 以 減 低 快 速 增 加 的 位 移 量, 但 帶 來 了 大 量 的 運 算 量, 而 以 權 重 優 先 的 方 式 先 找 出 最 大 迴 圈 值 的 元 素 動 作, 僅 動 用 了 53 個 元 素 還 不 到 總 個 數 的 一 半 就 可 打 斷 所 有 的 迴 圈, 相 對 減 低 檢 查 constraint 的 數 量 達 到 72%, 若 再 乘 上 每 個 constraint 的 加 法 數 及 乘 法 數 將 會 更 可 觀, 結 果 列 於 表 4-5 另 外 也 將 電 腦 模 擬 時 間 列 於 表 4-4, 程 式 由 Matlab 撰 寫 實 現, 電 腦 主 機 為 Intel Core2-Quad Q6600, 擴 展 的 倍 數 為 235 倍 所 有 剩 餘 迴 圈 之 平 均 值 1400 1200 1000 800 600 400 200 0 1 6 11 16 21 26 31 36 41 46 51 元 素 執 行 位 移 動 作 之 次 數 圖 4-10 每 次 執 行 位 移 動 作 後 所 有 剩 餘 迴 圈 平 均 值 之 長 條 圖 40

總 constraint 運 算 量 實 際 運 算 時 間 傳 統 式 76,050,105 5575 秒 改 良 式 21,328,164 404 秒 改 進 比 例 (%) 72% 92% 表 4-4 兩 種 演 算 法 之 比 較 列 表 每 條 constraint 傳 統 式 改 良 式 加 法 數 532,068,806 149,297,148 乘 法 數 684,164,027 191,953,476 表 4-5 兩 種 演 算 法 之 乘 法 數 與 加 法 數 前 文 提 到 本 矩 陣 靠 近 右 側 具 有 較 密 集 的 1, 因 此 右 側 將 會 產 生 大 量 的 迴 圈, 如 果 當 基 本 矩 陣 的 擴 展 值 有 一 定 的 限 制 時, 以 原 作 者 的 演 算 法 一 定 從 最 左 側 的 行 開 始 消 去, 消 去 到 一 半 時 可 能 將 所 有 擴 展 值 的 選 擇 用 完, 反 而 最 需 要 打 斷 的 右 側 卻 無 法 進 行 打 斷 迴 圈 的 動 作, 所 以 原 作 者 的 演 算 法 遇 到 右 側 有 密 集 的 1 且 擴 展 範 圍 有 限 時 會 遇 到 這 方 面 的 問 題 反 觀 以 迴 圈 的 總 數 排 定 優 先 次 序, 對 於 越 密 集 的 1 所 形 成 的 迴 圈 優 先 打 斷, 整 體 效 果 會 更 好 表 4-6 為 隨 機 取 右 側 9 個 元 素 在 不 同 擴 展 倍 數 剩 餘 的 迴 圈 數 與 原 始 未 被 打 斷 的 數 據 比 較, 證 明 能 有 效 打 斷 這 些 迴 圈, 因 此 本 演 算 法 適 用 於 低 擴 展 倍 數, 也 就 是 編 碼 長 度 短 的 應 用, 將 在 下 一 節 說 明 與 分 析 坐 標 / 擴 展 倍 數 未 擴 展 50 倍 100 倍 150 倍 (2,32) 2,482 18 4 1 (2,33) 2,114 18 4 2 (4,33) 1,564 14 3 0 41

(6,33) 1,627 15 1 0 (10,32) 1,840 14 0 0 (11,32) 1,783 15 0 0 (11,33) 1,587 10 1 0 (5,12) 2,817 24 6 0 (12,33) 2,450 23 3 1 表 4-6 本 演 算 法 在 1 分 佈 密 集 區 域 執 行 後 剩 餘 的 迴 圈 數 量 4.3 適 用 於 低 編 碼 長 度 之 說 明 與 效 能 模 擬 4.3-1 解 碼 長 度 與 遞 迴 次 數 之 間 的 影 響 LDPC 為 遞 迴 式 (Iterative) 的 解 碼 機 制, 經 由 反 覆 傳 送 機 率 資 訊 將 收 到 的 碼 更 逼 近 於 正 確 的 碼, 然 而 遞 迴 的 次 數 與 解 碼 長 度 有 很 大 的 關 係 [30], 如 圖 4-12 所 示, 模 擬 通 道 為 AWGN, 使 用 的 解 碼 演 算 法 是 SPA,H 矩 陣 為 碼 率 1/2 的 非 正 規 矩 陣, 紅 色 實 線 與 藍 色 虛 線 分 別 代 表 Code length 為 7200bits 與 3600bits 在 長 度 7200 三 種 遞 迴 次 數 均 造 成 明 顯 的 效 能 差 異 ; 而 在 長 度 3600 遞 迴 次 數 為 30 與 50 的 效 能 差 異 減 低, 但 在 遞 迴 次 數 為 10 時 解 碼 效 能 很 差, 因 此 在 越 長 的 解 碼 長 度 時 除 了 帶 來 大 量 的 運 算, 也 需 要 更 多 的 遞 迴 次 數 達 到 解 碼 收 斂 的 效 果, 其 中 遞 迴 次 數 與 耗 電 量 成 正 比, 如 遞 迴 次 數 50 次 比 30 次 多 出 1.6 倍 的 耗 電 量, 因 此 改 良 式 消 去 迴 圈 演 算 法 應 用 於 低 編 碼 長 度 實 現 模 擬 與 分 析 為 主 要 目 標 42

1.0E+00 1.0E-01 1.0E-02 CL=7200,iter=50 CL=7200,iter=30 CL=7200,iter=10 CL=3600,iter=50 CL=3600,iter=30 CL=3600,iter=10 BER 1.0E-03 1.0E-04 1.0E-05 1.0E-06 0.5 1 1.5 2 2.5 3 SNR 圖 4-11 不 同 編 碼 長 度 下 遞 迴 次 數 對 解 碼 效 能 的 影 響 4.3-2 周 長 與 短 迴 圈 對 解 碼 效 能 之 模 擬 在 PEG 演 算 法 [24] 文 獻 中 提 出 如 果 位 元 檢 查 矩 陣 具 有 較 多 的 長 迴 圈, 則 在 解 碼 時 能 使 每 次 遞 迴 動 作 之 間 更 為 獨 立 以 減 低 錯 誤 率 ; 另 外 在 [25] 文 獻 中 提 出 短 迴 圈 數 量 越 少 則 有 較 好 的 錯 誤 更 正 能 力 ; 還 有 在 [31] 文 獻 中 指 出 如 果 在 Tanner Graph 出 現 太 多 短 迴 圈 則 使 MPA 解 碼 的 效 能 變 差 因 此 這 邊 利 用 改 良 式 消 去 迴 圈 演 算 法 產 生 三 種 不 同 周 長 (Girth) 矩 陣, 模 擬 結 果 比 較 於 下 圖 43

1.0E+00 1.0E-01 CL=5400,Girth=10 CL=5400,Girth=8 CL=5400,Girth=6 1.0E-02 BER 1.0E-03 1.0E-04 1.0E-05 1.0E-06 0.5 1 1.5 2 2.5 SNR 圖 4-12 不 同 周 長 的 位 元 檢 查 矩 陣 對 解 碼 效 能 的 影 響 模 擬 採 用 的 基 本 矩 陣 與 圖 4-8 相 同, 矩 陣 擴 展 的 倍 數 為 150 倍, 遞 迴 次 數 為 50 次, 分 別 產 生 消 除 cycle-4 6 8 的 矩 陣, 另 外 註 明 因 為 全 部 消 除 cycle-8 迴 圈 需 要 擴 展 230 倍 使 編 碼 長 度 達 8280, 為 了 減 低 運 算 量 及 對 照 低 編 碼 長 度 的 情 況, 故 此 處 採 用 展 開 150 倍 的 矩 陣 且 cycle-8 幾 乎 全 部 消 除 由 圖 4-13 得 知 消 除 cycle-8 的 矩 陣 效 能 比 其 它 兩 者 優 異, 因 為 cycle-4 與 6 保 留 太 多 cycle-8 的 迴 圈, 經 擴 展 矩 陣 之 後 產 生 更 多 迴 圈 而 使 短 迴 圈 效 果 影 響 更 明 顯 另 外 參 考 [32] 文 獻 中 模 擬 非 正 規 矩 陣 的 效 能 圖, 得 知 Girth-6 8 的 效 能 接 近, 而 Girth-10 的 效 能 與 其 它 兩 者 差 異 大 4.3-3 傳 統 與 改 良 式 演 算 法 在 低 編 碼 長 度 之 模 擬 比 較 綜 合 前 兩 小 節 的 論 述, 產 生 一 個 低 編 碼 長 度 的 同 位 檢 查 矩 陣 以 減 少 需 要 的 遞 迴 次 數 及 運 算 量, 達 到 低 功 耗 的 目 的 此 外 因 為 改 良 式 演 算 法 擁 有 優 先 權 的 特 44

性, 在 低 擴 展 倍 數 仍 然 能 有 效 打 斷 短 迴 圈 進 而 增 進 解 碼 效 能, 所 以 這 邊 將 與 傳 統 式 演 算 法 進 行 分 析 與 模 擬 模 擬 使 用 的 演 算 法 除 了 傳 統 與 改 良 式 消 去 迴 圈 演 算 法 外, 加 入 ZP 演 算 法 [33] 做 為 參 考,ZP 演 算 法 同 為 擴 展 基 本 矩 陣 的 方 式 建 構 位 元 檢 查 矩 陣, 而 每 個 元 素 1 的 位 移 量 是 由 位 移 的 公 式 算 出 : u Pxy, = T ( I), where u = (( x 1) y) mod L ( 式 4-1) 模 擬 的 方 式 分 成 兩 部 分, 因 為 演 算 法 在 擴 展 矩 陣 30 倍 時 能 將 所 有 cycle-4 6 消 除, 所 以 一 類 擴 展 倍 數 低 於 30, 以 不 同 的 倍 數 統 計 剩 下 cycle-4 6 的 總 數, 再 做 效 能 比 較 分 析 ; 另 一 類 擴 展 倍 數 介 於 30 與 200, 以 不 同 的 倍 數 統 計 剩 下 cycle-4 6 8 的 總 數, 最 後 做 效 能 分 析 所 有 的 模 擬 比 較 都 是 建 立 在 相 同 編 碼 長 度 的 基 礎 上, 而 遞 迴 次 數 隨 著 編 碼 長 度 調 整 (1) 編 碼 長 度 小 於 1000 之 模 擬 與 分 析 : 此 擴 展 倍 數 均 小 於 30, 主 要 分 析 兩 者 演 算 法 在 編 碼 長 度 小 於 1000, 針 對 cycle-4 6 消 除 迴 圈 的 情 形 以 及 效 能 結 果 圖 4-14 為 不 同 倍 數 下 剩 餘 短 迴 圈 的 數 量, 得 知 在 擴 展 倍 數 小 的 時 候, 傳 統 演 算 法 尚 未 執 行 至 右 半 邊 矩 陣 的 元 素 就 已 經 達 到 位 移 上 限 值, 因 此 未 打 斷 的 短 迴 圈 數 量 很 多, 而 這 些 短 迴 圈 同 時 對 效 能 造 成 影 響 模 擬 基 本 矩 陣 為 18x36 大 小 的 非 正 規 矩 陣, 擴 展 倍 數 為 10 與 20 次 遞 迴 次 數 設 為 10 與 20 次 圖 4-15 中 兩 者 效 能 差 異 並 不 大, 因 為 打 斷 迴 圈 的 效 果 有 限, 加 上 Girth-6 與 Girth-8 在 非 正 規 矩 陣 中 效 能 差 異 不 明 顯, 只 有 在 SNR=3 也 就 是 低 錯 誤 率 時 效 能 差 距 較 大 45

剩 餘 迴 圈 數 500 400 CE PCE ZP 300 200 100 0 5 10 15 20 25 30 擴 展 倍 數 圖 4-13 不 同 擴 展 倍 數 下 所 剩 餘 迴 圈 總 量 1.0E+00 1.0E-01 CL=360,Iter=10,PCE CL=360,Iter=10,CE CL=360,Iter=10,ZP 1.0E-02 BER 1.0E-03 1.0E-04 1.0E-05 0.5 1 1.5 2 2.5 3 3.5 4 SNR 圖 4-14 PCE 與 CE 演 算 法 編 碼 長 度 為 360 之 效 能 圖 46

1.0E+00 1.0E-01 CL=720,Iter=20,PCE CL=720,Iter=20,CE CL=720,Iter=20,ZP 1.0E-02 BER 1.0E-03 1.0E-04 1.0E-05 0.5 1 1.5 2 2.5 3 3.5 SNR 圖 4-15 PCE 與 CE 演 算 法 編 碼 長 度 為 720 之 效 能 圖 (2) 編 碼 長 度 於 1000 至 4000 之 模 擬 與 分 析 : 圖 4-16 為 不 同 擴 展 倍 數 下 所 剩 餘 短 迴 圈 總 量, 由 於 cycle-8 數 量 非 常 多, 所 以 傳 統 消 去 迴 圈 演 算 法 在 擴 展 60 倍 時 只 能 執 行 左 半 邊 少 許 元 素 的 位 移 動 作 而 留 下 大 量 的 迴 圈, 反 之 改 良 式 演 算 法 直 接 對 最 高 優 先 權 動 作 消 除 許 多 迴 圈, 其 中 擴 展 50 倍 之 內 已 消 除 所 有 cycle-4 6 迴 圈, 因 此 圖 4-16 也 表 示 剩 餘 cycle-8 的 數 量 模 擬 所 使 用 的 基 本 矩 陣 同 上 例, 擴 展 的 矩 陣 倍 數 為 50 與 100, 遞 迴 次 數 為 30 次 在 圖 4-17 中 SNR 大 於 1.5 時, 長 度 1800 的 效 能 曲 線 有 明 顯 差 異, 因 為 擴 展 50 倍 時 傳 統 演 算 法 所 留 下 cycle-8 的 迴 圈 數 比 改 良 式 演 算 法 高 出 許 多, 再 次 驗 證 高 SNR 低 錯 誤 率 時 短 迴 圈 的 影 響 更 大 [34] 此 外 若 為 了 省 電 採 用 低 遞 迴 次 數 解 碼, 在 圖 4-18 所 示 遞 迴 次 數 為 15 次 也 能 得 到 解 碼 效 能 的 改 進 ; 在 擴 展 100 倍 時 兩 者 演 算 法 所 留 下 的 迴 圈 數 較 接 近, 因 此 圖 4-19 反 應 效 能 上 也 比 較 相 近, 但 改 良 式 演 算 法 能 消 除 更 多 的 短 迴 圈 以 增 進 解 碼 效 能 47

Remaining Cycle amount 1500 1200 CE PCE ZP 900 600 300 0 50 75 100 125 150 175 200 Expanded Size 圖 4-16 不 同 擴 展 倍 數 下 所 剩 餘 迴 圈 總 量 1.0E+00 1.0E-01 CL=1800,Iter=30,PCE CL=1800,Iter=30,CE CL=1800,Iter=30,ZP 1.0E-02 BER 1.0E-03 1.0E-04 1.0E-05 1.0E-06 0.5 1 1.5 2 2.5 SNR 圖 4-17 PCE 與 CE 演 算 法 編 碼 長 度 為 1800 之 效 能 圖 48

1.0E+00 1.0E-01 CL=1800,Iter=15,PCE CL=1800,Iter=15,CE CL=1800,Iter=15,ZP 1.0E-02 BER 1.0E-03 1.0E-04 1.0E-05 0.5 1 1.5 2 2.5 SNR 圖 4-18 PCE 與 CE 演 算 法 編 碼 長 度 為 1800 之 效 能 圖 1.0E+00 1.0E-01 CL=3600,Iter=30,PCE CL=3600,Iter=30,CE CL=3600,Iter=30,ZP 1.0E-02 BER 1.0E-03 1.0E-04 1.0E-05 1.0E-06 0.5 1 1.5 2 SNR 圖 4-19 PCE 與 CE 演 算 法 編 碼 長 度 為 3600 之 效 能 圖 49

第 五 章 結 論 本 篇 論 文 探 討 LDPC Codes 設 計 並 適 用 於 低 編 碼 長 度 之 應 用, 所 建 構 的 位 元 檢 查 矩 陣 採 用 Block-LDPC[17] 的 形 式 有 利 於 硬 體 上 實 現, 主 要 針 對 兩 方 面 做 演 算 法 改 良, 一 方 面 改 良 式 演 算 法 比 傳 統 式 演 算 法 節 省 大 量 運 算 及 複 雜 度, 另 一 方 面 在 不 同 的 擴 展 倍 數 均 能 有 效 打 斷 迴 圈 的 連 結 以 增 進 解 碼 效 能 改 良 式 演 算 法 以 每 個 元 素 1 的 迴 圈 總 數 決 定 優 先 順 序, 從 最 高 優 先 權 開 始 消 除 迴 圈 動 作, 充 分 利 用 每 次 打 斷 迴 圈 的 機 會 故 減 低 了 演 算 法 遞 迴 次 數, 尤 其 在 前 幾 次 遞 迴 動 作 時 有 效 減 少 大 量 迴 圈, 所 以 在 消 去 相 同 迴 圈 總 數 時, 運 算 量 相 較 傳 統 演 算 法 減 低 約 70~80%, 以 Matlab 為 模 擬 平 台 之 模 擬 時 間 減 少 約 90%, 均 可 證 明 改 良 式 演 算 法 能 節 省 大 量 運 算 及 複 雜 度 在 移 動 通 訊 或 無 線 通 訊 的 應 用 中 [35], 若 使 用 LDPC 當 作 編 解 碼 的 媒 介 而 採 用 的 矩 陣 大 多 為 短 編 碼 長 度 的 矩 陣, 因 為 長 編 碼 矩 陣 除 了 帶 來 大 量 運 算, 也 需 要 更 多 次 數 的 遞 迴 解 碼 使 效 能 收 斂, 應 用 上 更 為 耗 電 因 此 我 們 著 重 在 產 生 一 個 好 的 LDPC 矩 陣, 再 加 上 優 先 權 為 基 礎 之 特 性, 在 前 幾 次 遞 迴 運 算 時 就 能 打 斷 大 量 迴 圈, 能 越 早 消 除 大 量 迴 圈 則 在 低 擴 展 倍 數 時 越 有 利, 因 為 遞 迴 次 數 的 增 加 讓 位 移 值 的 選 擇 越 來 越 少 所 以 模 擬 編 碼 長 度 在 4000 位 元 以 下 的 矩 陣 作 為 解 碼 矩 陣, 解 碼 的 效 能 上 均 比 其 它 兩 種 相 同 架 構 的 演 算 法 要 來 得 優 異, 尤 其 在 低 錯 誤 率 時 效 能 增 進 更 明 顯, 突 顯 出 低 編 碼 長 度 時 能 夠 有 效 率 消 除 迴 圈, 適 用 於 省 電 或 低 運 算 量 等 通 訊 系 統 50

參 考 文 獻 [1] C. E. Shannon, A Mathematical Theory of Communication, Bell Syst. Tech. J., pp. 379-423 (Part 1); pp. 623-56 (Part 2), July 1948. [2] Shu Lin, D. J. Costello, Error Control Coding 2nd ed., Person-Prentice Hall, 2004. [3] E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968; Rev. ed., Aegean Park Press, Laguna Hills, N. Y., 1984. [4] P. Elias, Coding for Noisy Channels, IRE Conv. Rec., p. 4:37-47, 1955. [5] E. Prange, Cyclic Error-Correcting Codes in Two Symbols, AFCRC-TN-57, 103, Air Force Cambridge Research Center, Cambridge, Mass., September 1957. [6] I. S. Read and G. Solomon, Polynomial Codes over Certain Fields, J. Soc. Ind. App. Math., 8:300-304, June 1960. [7] R. G. Gallager, Low-Density Parity-Check Codes. Cambridge, MA: MIT Press, 1963. [8] C. Berrou, A. Glavieux, and P. Thitimajshima, Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes, IEEE Intl. Conf. Commun., pp. 1064-70, Geneva, Switzerland, May 1993. [9] D.J.C Mackay and R.M Neal, Near Shannon limit performance of low-density parity-check codes, Electron. Lett. vol.32, pp.1645-1646, Aug. 1996. [10] N. Wiberg, Codes and Decoding on General Graphs, IEEE Conf. Inf. Theory, p.468, Sep. 1995. [11] A. Delvarathinam, E. Kim, and G. Choi, Low-Density Parity-Check Decoder Architecture for High Throughput Optical Fiber Channels, IEEE Intl. Conf. Comp. Design, pp. 520 525, 2003. 51

[12] A. J. Blanksby and C. J. Howland, A 690-mW 1-Gb/s 1024-b, rate-1/2 Low-Density Parity-Check Code Decoder, IEEE Trans. Solid-State Circuits, vol. 37, no.3, pp. 404 412, Mar. 2002. [13] T. Richardson and R. Urbanke, Efficient encoding of Low-Density Parity-Check Codes, IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 638 656, Feb. 2001. [14] T. Richardson, A. Shokrollahi, and R. Urbanke, Design of Capacity Approaching Low-Density Parity-Check Codes, IEEE Trans. Inf. Theory, vol.47, no.2, pp. 619-637, Feb. 2001. [15] R. MICHAEL TANNER, A Recursive Approach to Low Complexity Codes, IEEE Trans. Inf. Theory, vol.27, no.2, pp.533-547, Sep. 1981. [16] 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. [17] M. Chiani, A. Conti, and A. Ventura, Evaluation of Low-Density Parity-Check Codes Over Block Fading Channels, IEEE Conf. Commun., vol.3 pp. 1183 1187, June. 2000. [18] F. R. Kschischang, B. J. Frey, and H. A. Loeliger, Factor Graphs and the Sum-Product Algorithm, IEEE Trans. Inf. Theory, vol. 47, pp498-519, Feb 2001. [19] 朱 元 志, 低 密 度 對 偶 檢 查 碼 之 改 進 以 及 其 解 碼 器 之 超 大 型 積 體 電 路 實 現, 國 立 交 通 大 學 論 文, 2005. [20] Xiao-Yu Hu, E. Eleftheriou, D. M. Arnold, A. Dholakia, Efficient Implementations of the Sum-Product Algorithm for Decoding LDPC, IEEE Conf. Globe Telecom, pp. 1036-1036E, Nov. 2001. 52

[21] Lei Yang, Hui Liu, C.-J Richard Shi, Code Construction and FPGA Implementation of a Low-Error-Floor Multi-Rate Low-Density Parity-Check Code Decoder, IEEE Trans. Circuit and Systems, vol. 53, no. 4, Apr. 2006. [22] D. E. Hocevar, LDPC Code Construction with Flexible Hardware Implementation, IEEE Conf. Commun., vol.4, pp. 2708 2712, May 2003. [23] K. Shimizu, T. Ishikawa, N. Togawa, T. Ikenaga, S. Goto, Partially-Parallel LDPC Decoder Based on High-Efficiency Message-Passing Algorithm, IEEE Conf. Com., pp. 503-510, Oct. 2005. [24] X. Y. Hu, E. Eleftheriou, and D. M. Arnold, Progressive Edge-Growth Tanner Graphs, IEEE Conf. Global Telecomm., vol. 2, pp.995 1001, Nov.2001. [25] J. Campello, D. S. Modha, and S. Rajagopalan, Designing LDPC Codes Using Bit-Filling, IEEE Conf. Com., pp. 55 59, June 2001. [26] H. Zhang and T. Zhang, Design of VLSI Implementation-Oriented LDPC Codes, IEEE Conf. Technol., vol. 1, pp. 670 673, Oct. 2003. [27] L.Yang, H. Liu, and C.-J. R. Shi, Cycle Elimination Method to Construct VLSI Oriented LDPC Codes, IEEE Technol. Conf., pp. 522 526, Sep. 2005. [28] D. J. C. Mackay, S. T. Wilson, and M. C. Davey, Comparison of Constructions of Irregular Gallager Codes, IEEE Trans. Comm., vol. 47, pp.1449 1454, Oct. 1999. [29] T. Tian, C. Jones, J. D. Villasenor, and R. D.Wesel, Construction of Irregular LDPC Codes with Low Error Floors, IEEE Conf. Com., vol. 5, pp. 3125 3129, May 2003. [30] T. Richardson, Error Floors of LDPC Codes, IEEE Conf. Commun., pp. 1426 1435, Oct. 2003. [31] H. Zhang and T. Zhang, Block-LDPC: A Practical LDPC Coding System Design Approach, IEEE Trans. Circuits and Systems, vol. 52, no. 4, Apr. 2005. 53

[32] Campello J., Modha D.S., Extended Bit-Filling and LDPC Code Design, IEEE Conf. Global Telecomm., vol. 2, pp. 25-29, Nov. 2001. [33] T. Zhang and K. K. Parhi, VLSI Implementation-Oriented (3,k)-Regular Low-Density Parity-Check Codes, IEEE Conf. Signal Process, pp. 25 36, Sep. 2001. [34] J. M. F. Moura, Jin Lu, Haotian Zhang, Structured Low-Density Parity-Check Codes, IEEE Trans. Signal Process, vol. 21, pp.42-55, Jan. 2004. [35] IEEE 802.16e-2005, IEEE Standard for Local and Metropolitan Area Network - Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems Amendment 2: Physical and Medium Access Control layers for Combined Fixed and Mobile Operation in Licensed Bands, 2005. 54