循环码和BCH码.

Slides:



Advertisements
Similar presentations
1 主动保健,走健康之路 中国人体健康促进会 常务理事 上海瑞金医院集团瑞美医疗保健中心 中心主任 张乃和.
Advertisements

“ 我不能 上学了,我 每天还要帮 家里拾柴火 呢。 ” 给远方的小学生写一封信 书信的基本格式: 开头顶格写称呼,打上冒号; 换行空两格写问候语; 接下来换行空两格写正文部分; 正文结束后,换行写祝颂语; 最后在右下方写上寄信人姓名和 写信日期。
第二章 函数微分学 §2.3 函数的微分 本节内容 一.微分的定义 二.微分的几何意义 三.微分公式与运算法则.
目录 上页 下页 返回 结束 Zhengzhou Institute of Science & Technology 二、微分运算法则 三、微分在近似计算中的应用 * 四、微分在估计误差中的应用 第五节 一、微分的概念 函数的微分 第二章.
精品课程 二、微分运算法则 三、微分在近似计算中的应用 四、微分在估计误差中的应用 第二节 一、微分的概念 函数的微分.
电话: XXXXX 主讲: XXXXX 任务五 组织旅游线路. 本节任务:设计一条旅游线路 休闲度假天堂游 早烟台集合,乘车赴蓬莱,游览人间仙境 — 蓬莱阁风景区 ( 1.5 小时)、水城、古船馆、八仙群雕。 第一天 然后自由活动或自费游览:八仙渡海口风景区( 60 元自 理)海洋极地世界( 120.
中醫藥就醫用藥 - 婦女篇 中醫藥安全衛生教育資源中心 中醫藥就醫用藥百分百、就是藥做到: 停、看、聽、選、用專業.
下背痛 林口長庚醫院內科 住院醫師 毛畯台. 下背痛常見原因 軟組織受傷/背部筋膜發炎 椎間盤突出症 脊椎退化性關節炎 壓迫性骨折 椎間盤滑脫 惡性腫瘤 泌尿道疾患 姿勢不良.
華德學校上午校 「協助小學中國語文科教師建立專業學習型社群」計劃 (2008) 總結分享會 二零零九年一月十日.
1.3 二项式定理. [ 题后感悟 ] 方法二较为简单,在展开二项式之前根据二项 式的结构特征进行适当变形,可使展开多项式的过程简化.记 准、记熟二项式 (a + b) n 的展开式,是解答好与二项式定理有关 问题的前提,对较复杂的二项式,有时可先化简再展开,会更 简便.
第二讲 台湾地区政府架构 一、三民主义:台湾地区政府施政精神 二、五权分立的政治框架 三、无处不在的总统: 总统在政治体系中的角色与地位 四、地方自治与地方政治生态.
園藝二乙 1 號 丁楷儒 32 號 孫子恩. 1. 福山萵苣 ( 大陸妹 ) : 福山萵苣,萵苣家族成員之一,鮮甜脆綠又帶有萵苣類的 特殊苦味,用來代替生菜搭配烤肉也別具風味。極少病蟲 害,只需定時澆水施肥就能健康長大,是相當容易種植又 能有大收穫的蔬菜 。 感想: 雖然大陸妹好吃又好種,但種了太多而吃不完.
第七讲 人机工程学课程设计.
第五单元 口语交际和作文.
第八章 負債 8-1 負債之意義及內容 8-2 流動負債 8-3 長期負債 8-4 其他負債.
工业财务状况表 财务部分培训 (2010年年报).
无锡商业职业技术学院 机电工程学院党总支孙蓓雄
2016年全国中级会计资格考试 经济法 主讲老师:葛江静.
定海区渔农村集体资产 股份合作制改革工作 档案管理培训班
述 职 报 告 ——报告人:xxxxx.
北京市工作居住证办理讲解.
南京市国税局国际税务管理处 二00九年二月二十四日
全面了解入党程序 认真履行入党手续 第一讲 主讲人:陈亭而.
中共湖北大学知行学院委员会党校 入党材料规范填写指导 学工处 李华琼 二〇一三年十二月.
云南财经大学2010年党员发展培训—— 党员发展工作培训 校党委组织部 2010年9月17日.
成品成本计算 鞠传英.
机电设备概论 安全管理概述 XXXXX.
评估报告的撰写 二手车评估报告是评估机构或评估师在完成鉴 定评估工作后,向委托方提供鉴定评估工作的 总结。
祝贺您获得国家留学基金资助 请您登陆“国家留学网”查看《出国留学人员须知》,您在出国前及在外学习期间所需要办理的手续及具体流程,以及可能遇到的政策上疑问均在此《须知》上有所列明。
实际问题与一元二次方程(一).
22.3 实际问题与一元二次方程(1).
医师变更执业注册申请审核表 填写说明 医务部.
审题与立意 夏邑高中高四语文组.
專題研究計畫經費使用重點說明 會計室 中華民國101年11月21日
述职报告 ( 二○○七年度 ) 述职人: xxx 部 门: 计划财务部 岗 位: 部门经理.
转正述职报告 电商文案策划 XXX.
經濟部工業局 產業升級創新平台輔導計畫 (創新優化計畫)
基层违纪违法案件 查办的基本程序 基本要求和案例解析 学 思 践 悟 基层违纪违法案件 查办的基本程序 基本要求和案例解析 内蒙古纪委案件审理室 方瑛 2015年5月24日.
努力做好新常态下 反映社情民意信息工作 省政协研究室 欧阳东 2016年5月31日.
拉丝工艺理论知识培训 欢迎大家参加此次培训! 一、拉丝工艺工序流程图 二、拉丝工艺理论知识(四大部分) 1、铜材 2、模具 3、拉丝油
几种常见应用文体示例.
2014年工作总结 暨2015年工作展望.
植物的繁殖方式与育种 第2章.
我 自我介绍 我爱看的 书 名片 格言.
第八章 诉讼法 第一节 诉讼法概述 第二节 民事诉讼法 第三节 行政诉讼法 第四节 刑事诉讼法.
§2 无穷积分的性质与收敛判别.
普及纳米知识 推动科技进步.
通 知 通知是批转下级机关的公文,转发上级机关和不相隶属机关的公文,传达要求下级机关办理和需要有关单位周知或执行的事项,任免人员时使用的公文。
歷史作業 黃朝琴 藍郁涵.
拉丝工艺理论知识培训 欢迎大家参加此次培训! 一、拉丝工艺工序流程图 二、拉丝工艺理论知识(四大部分) 1、铜材 2、模具 3、拉丝油
赴澳修学旅行 签证材料讲解(学生) 清单一览 重点详解 特别说明
你眼中的 日本是怎 样的? 分享. 你眼中的 日本是怎 样的? 分享 文明安静有秩序 做事做到极致 治愈系 二次元 东野圭吾 村上村树
Sssss.
循 环 码 (II).
集中保管有價證券 提存帳簿劃撥作業介紹 (代庫銀行版)
第二部分 免疫系统与免疫活性分子 第二章 免疫系统 第三章 免疫球蛋白 第二 部分 第五章 细胞因子 第四章 补体系统.
計畫成果說明(範本) 成果說明:請依輔導成效另訂標題(slogan) 診斷重點 輔導成效 成果照片1 成果照片2
第十章 差错控制编码 10.1 差错控制编码的基本原理 10.2常用的简单编码 10.3 线性分组码 10.4循环码 10.5卷积码.
淑明女子大學 在哪裡?. 淑明女子大學 在哪裡? 學校週遭 第一次 剛到淑大時?
認識多項式 1 多項式的加法 2 多項式的減法
7 5. 分離係數法: 將直式運算中的係數和文字符號分離, 只寫出係數的記錄方式。 在寫出係數時,遇到缺項,一定要補 0 。
判別下列何者是 x 的多項式。以「○」表示是x的多項式,「×」表示不是 x的多項式 :
四川农业大学 第二十二期团校课程 第四讲:校团委日常公文与写作 主讲人:刘瀛锴.
寶 貝 班 教 學 分 享 (103下) 為了搭配主題,所以除了平日在校園中探索外,我們每周也會帶孩子出去一次,進行社區巡禮,讓孩子探索不同的人事物,欣賞不同的美,每次出門孩子總有新的發現,所以我們從孩子的發現為出發點,來延續課程內容,像是觀察植物的顏色及形狀;認識各種水果…等,除此之外,我們也針對孩子喜愛的車子進行討論,從中除了帶入形狀、顏色外,也能認識各種行業的人喔!
第二章 数控车削加工常用指令及应用 1.常用辅助功能指令 2.直线车削指令——G01/G00 3.圆弧车削指令——G02/G03
工业行业工作总结 PPT宝藏_www.pptbz.com_提供下载.
8的乘法口诀 导入 新授 练习.
循环码和BCH码.
‘人因罪與神隔絕’ 左邊代表每一個人像你和我。 黑暗代表我們的罪。 聖經說: 世人都犯了罪,虧缺了神的榮耀。 (羅3:23)
PPT中条条框框的使用 秋记 提供下载 秋记与好看簿.
Presentation transcript:

循环码和BCH码

简述 1957年开始研究 循环码的优点: 编码和校正子的计算容易实现 具有固定的代数结构,能找到很多实用的方法来译码

循环码定义 对一个n维码字向量v=(v0,v1,…,vn-1)做一次向右循环移位,得到v(1)=(vn-1,v0,…,vn-2),类似,向右做i次移位,得到v(i)=(vn-i,vn-i+1,…,vn-i-1),等价于向左移位n-i次 循环码:一个(n,k)线性码C,若每个码字的循环移位仍然是C的码字,则称其为循环码 为研究循环码的代数结构,将码字v的分量看做多项式的系数:v(x)=v0+v1X+v2X2+…+vn-1Xn-1 每个码字对应于一个次数等于或小于n-1的多项式 码字和多项式是一一对应的, v(x)叫做码多项式

码多项式 若v的码多项式为v(x)=v0+v1X+v2X2+…+vn-1Xn-1 则v(i)的码多项式为vn-i+vn-i+1X+…+vn-i-1Xn-1 计算xiv(x)-v(i)得到: (1) 也就是说v(i)就是xiv(x)除Xn+1后的余式

循环码的性质 循环码中非零次数最低的多项式是唯一的 循环码中非零次数最低多项式常数项为1 证明:(反证法)假设有两个最低次数一样的多项式,这这两个多项式之和的次数更低,而且应该是码多项式(线性,封闭性),矛盾。 循环码中非零次数最低多项式常数项为1 证明: (反证法)假设常数项为0,则码多项式可提取公因子X,另一个因子是次数更低的码多项式(循环左移1次),矛盾。 设g(X)=1+g1X+…+Xr是(n,k)循环码非零次数最低的多项式,次数小于或等于n-1的二进制多项式是码多项式当且仅当它是g(X)的整倍数。

循环码的性质 证明:1)若v(X)是g(X)的整倍数,即 v(X)=(1+u1X+...+uiXi)g(X),Xig(X)是g(X)向左循环移位i次的码多项式,故v(X)是码的线性组合;2)设v(X)是码多项式,有v(X)= a(X)g(X)+ b(X), b(X)次数小于g(X), b(X)可以写成b(X)= a(X)g(X)+v(X),故b(X)是码多项式或0,因g(X)是次数最低的非零多项式,故b(X)=0,即v(X)是g(X)的整倍数

循环码的性质 (n,k)循环码有且仅有一个n-k次的码多项式g(X)=1+…+Xn-k,这就是次数最小的码多项式,也称为码的生成多项式

循环码的性质 (n,k)循环码的生成多项式g(X)是Xn+1的一个因子 证明:由公式(1)显然。 若g(X)是次数为n-k,且是Xn+1的一个因子,则g(X)是生成多项式,生成一个(n,k)循环码 证明:略。 性质6说明Xn+1任何一个n-k次多项式都可以生成一个(n,k)循环码,当n很大时,可以构造很多的(n,k)循环码,有好有坏,如何选择?

例子: X7+1 X7+1=(1+ X)(1+X+X3)(1+X2+X3) 故有两个(7,4)循环码

循环码的系统形式 码字前n-k分量为校验位,后k分量是信息位 编码步骤: 用Xn-k乘信息序列u(X) 用生成多项式g(X)除Xn-ku(X),得余式b(X)为校验位 得到码多项式Xn-ku(X)+b(X)

循环码的生成矩阵 设g(x)=g0+…+gn-kXn-k,则有生成矩阵如下: 若不是系统形式,可通过行变换变成系统形式

校验矩阵H 令h(X)满足, Xn+1=g(X)h(X),则h(X)的k个系数张成矩阵,h(X)称为校验多项式

循环码的对偶码 设码C的生成多项式为g(X),校验多项式为h(X) 其对偶码的生成多项式为Xkh(X-1),也是一个循环码 一个循环码被其校验矩阵唯一确定

例子 (7,4)循环码C,生成多项式g(X)=1+X+X3 其校验多项式为h(X)=(Xn+1)/g(X) =1+X+X2+X4 X4h(X-1)=1+X2+X3+X4

循环码的编码 编码步骤: 用Xn-k乘信息序列u(X) 用生成多项式g(X)除Xn-ku(X),得余式b(X)为校验位 得到码多项式b(X) +Xn-ku(X)

循环码的译码 同线性码 计算校正子 求错误模式 纠错或计算码字

查错 令v(X)表示输入码字,e(X)为错误模式,则接受向量r(X)=v(X)+e(X)=a(X)g(X)+e(X),故有:e(X)=a(X)g(X)+b(X)g(X)+s(X)=c(X)g(X)+s(X),即校正子是错误模式除以生成多项式的余式 从接受向量r(X)可以计算校正子s(X),错误模式e是未知的,故需要从s(X)去求e(X)。若e(X)是标准阵的陪集首,则可用查表译码,由校正子获得错误模式。 若e(X)是0,则s(X)=0;若e(X)是码多项式,则e(X)是漏检错误模式。

计算校正子 设接受序列为r(X),则有: r(X)=a(X) g(X)+s(X),当且仅当r(X)是码多项式时,s(X)是0,s(X)就是校正子 性质:r(1)(X)的校正子s(1)(X)是s(X)的一次循环移动。 也就是说码字循环位移得到新码字的校验子是原校验子循环位移后除以生成多项式的余式,即: s(i)(X) =Xis(X)-b(X)g(X)=ri(X)-c(X)g(X), s(i)(X) 的次数低于g(X)

译码 串行译码 每次只译一个接收比特,然后循环移位,继续译下一个接受比特 若校正子s(X)与Xn-1有错所对应的错误模式对应,则接受比特vn-1有错 得到修正接收多项式r1(X)=r0+r1X+…+rn-2Xn-2 +(rn-1+en-1)Xn-1,循环位移得到r1(1)(X)=(rn-1+en-1) +r0X+r1X2+…+rn-2Xn-1,且s1(1)(X)=s(1)(X)+1 Meggitt译码器(算法)

循环码的差错检测能力 假设错误是突发错误,即错误模式e包含连续若干个1,(n,k)循环码能检测长度小于等于n-k的突发错误 证明:e(X)=XjB(X),B(X)的次数小于等于n-k-1,小于g(X)的次数,又因为g(X)和Xj互素,因此e(X)不是g(x)的倍式,故s(X)不为0。检测出错误。 长度为n-k+1的突发错误中,不能被检测的数目占2-(n-k-1);长度>n-k+1,不能被检测的2-(n-k) 证明:共有2 (n-k-1)种突发错误,不能被检测的只有当e(X)是g(x)的倍式;共有2 (n-k)种突发错误,不能被检测的2l-(n-k)-2种。 差错检测能力强!

(23,12)格雷码 生成多项式: 若g1(X)=1+X2+X4+X5+X6+X10+X11, g2(X)=1+X+X5+X6+X7+X9+X11 X23+1=(1+X)g1(X)g2(X)

(23,12)格雷码的系统搜索译码 通过循环位移,不大于3个错误的错误模式在特定11个连续位(校验位)之外至多有1个错误 步骤: 计算校正子 接收向量和校正子循环位移23次,检查校正子重量是否小于等于3,若满足则可纠错 若否,则对第一个信息位取反,重复上一步,检查是否有重量小于2的校正子,若有则第1位错,校正子指出其他两个错,完成译码 若上一步判断是否定的,则第1位正确,恢复第1位,类似检查第二个信息位,第三个…,直到第12个信息位 每种错误数目不大于3个错误模式,至少1个错误,一旦纠正了,会令其他的错误在连续的11位中,可用普通方式来纠正(通过逐一取反12个信息位,假设检验)。

准循环码 每次循环移动n0位, 若n0=1,就是循环码,否则就是准循环码 N0叫做移位约束 准循环码的对偶码也是准循环码

BCH码 BCH三个人:Bose, Chaudhuri, Hocquenghem 是一类循环码,是汉明码的推广,可纠正多个错误 定义: 对任意正整数m(m>2)和t(t<2m-1),存在具有如下参数的BCH码 分组长度 n=2m-1 奇偶校验位数目 n-k<=mt 最小距离 dmin>=2t+1 该码能校正小于等于t个错误

g(X)的次数最多为mt,因为每个多项式的次数至多为m,也就是n-k<=mt BCH码的生成多项式(本原BCH码) 设a是GF(2m)的生成元。码长为2m-1,纠正t个或少于t个错误的BCH码的生成多项式 就是以 为根的最低次多项式。 设 的最小多项式为 ,则 任何整数i都可以写成 i=i’2l,其中i’是奇数 ,我们有 ,当l>1时, 是 的共轭元,具有相同的最小多项式 ,故g(X)可写为 g(X)的次数最多为mt,因为每个多项式的次数至多为m,也就是n-k<=mt

非本原BCH码 给定正整数m(m>2)和t(t<2m-1)之后,通过选择FG(2m)中的本原元构建生成多项式获得本原BCH码 若选择的不是本原元,则得到非本原BCH码,n!=2m-1 BCH码就是循环码的生成多项式的根是连续的FG(2m)的元素 ,该码的最小距离至少为2t+1

BCH的码多项式 设码 ,其码多项式为: 故码多项式有生成多项式g(X)的全部根,也就是 及其共轭元,有一个码多项式的定义:当且仅当包含有 为根的多项式 称为码多项式 对1<=i<=2t,码多项式

BCH的码多项式 也就是向量内积: 对任意的1<=i<=2t,上式都成立,即码向量v和下列矩阵H的乘积为0 vHT=0 ,H是该码的校验矩阵

简化的校验矩阵H 码多项式 其共轭元 必然满足 H中偶数行的 是某个奇数行的共轭元,故H可以简化为如下:

BCH码的译码 假设发送码字 ,传输中的错误导致了 令错误模式为 有 译码第一步,计算校正子 假设发送码字 ,传输中的错误导致了 令错误模式为 有 译码第一步,计算校正子 令 的最小多项式为 ,并将接收向量写为: ,故有S的第i个分量 ,即在r(X)除以 的最小多项式的余式 中代入 ,得到 Si

例子:纠2个错误的(15,7)BCH码 α是GF(24)的本原元,且1+ α+ α4=0 α的最小多项式Φ1(X)=1+X+X4 α3的最小多项式Φ3(X)=1+X+X2+X3+X4 α5的最小多项式Φ5(X)=1+X+X2 码长:n=24-1=15, t=2的BCH码的生成多项式为: g(X)=LCM{Φ1(X), Φ2(X), Φ3(X), Φ4(X)}= LCM{Φ1(X), Φ3(X)} Φ1(X), Φ3(X)不可约,g(X)= Φ1(X)Φ3(X) = 1+X4+X6+X7+X8 (15,7)BCH,dmin=5

例子:纠2个错误的(15,7)BCH码 假设接收向量为(100000001000000),对应接收多项式为r(X)=1+X8 校正子有4个分量:S=(S1,S2,S3,S4) α, α2, α4的最小多项式 Φ1(X)=1+X+X4,r(X)/ Φ1(X)的余式 b1(X)=X2 α3的最小多项式 Φ3(X)=1+X+X2+X3+X4 , r(X)/ Φ1(X)的余式 b3(X)=1+X3 S=(α2,α4 , 1+α9 , α8) =(α2,α4 ,α7 , α8)

e(αj) = e0+e1αj+e2α2j+...+en-1α(n-1)j 假设错误模式有v个错误,位置分别为j1,j2,...,jv,那么就有 S1 = αj1+ αj2+...+ αjv S2 = (αj1)2+ (αj2)2+...+ (αjv)2 ... S2t = (αj1)2t+ (αj2)2t+...+ (αjv)2t 上面这些方程组中,校正子已知,要求位置j1,j2,...,jv,我们求αj1, αj2, ...,αjv即可

位置多项式 σ(X) = (1+ αj1X) (1+ αj2X)... (1+ αjvX) = σ0 + σ1X1 +...+ σvXv

BCH码的译码步骤 由接收多项式r(X)计算校正子 由校正子分量确定错误位置多项式 通过求解 的根,确定错误位置,并纠正r(X)中的错误