二维码三信息码的生成（手工制作）
采用的bch编码
一、BCH码基本原理
BCH码是一种有限域中的线性分组码，具有纠正多个随机错误的能力，通常用于通信和存储领域中的纠错编码。BCH码定义如下：给定任意一个有限域GF(q)及其扩展域GF(q^m)，其中q是素数或素数的幂，m为正整数。对于任意一个码元取自扩展域GF(q^m)的循环码(n,k)，其中n=2^m-1，其生成多项式g(x)具有2t个连续的根{a^1,a^2,a^,...,a^(2t-1),a^(2t)}，则由生成多项式g(x)编码产生的循环码称为q进制的BCH码，记为(n,k,t)。当码长n=2^m-1，称为本原BCH码，否则称为非本原BCH码。
最常用的BCH码是二进制的BCH码。二进制BCH码的所有码元都是由0和1构成，便于硬件电路的实现。如无说明，本文以下讨论的BCH码都是二进制BCH码。二进制本原BCH码具有以下重要参数：
码长：n=2^m-1校验位长度：n-k<=m*t
BCH码的生成多项式是由GF(q^m)的2t个最小多项式最小公倍式的乘积，纠错能力为t的BCH码生成多项式为g(x)=LCM{m1(x),m2(x),...,m2t-1(x),m2t(x)}，其中LCM表示最小公倍式，m(x)为最小多项式。
由多项式理论知道，如果有限域GF(2^m)中的元素a^i是m次即约多项式mi(x)的根，则(a^i)^2,(a^i)^4,(a^i)^8,...也是mi(x)的根，(a^i)^2,(a^i)^4,(a^i)^8,...称为共轭根系。如果两个根共轭，则它们具有相同的最小多项式。因此生成多项式g(x)=LCM{m1(x),m2(x),...,m2t-1(x),m2t(x)}=m1(x)*m3(x)*...*m2t-1(x)通过以上步骤就可以求出BCH码的生成多项式。得到生成多项式就可以对信息进行编码 [2] 。
其中mi（x）生成原理：
上述时定义以及m1（x），因此通过上面的讲述我们可以 得到
mi（x）=（x+a(i))(x+a(i*2)(x+a(i*2*2))....
注意：当i*2n如果此值大于2的15次方就需要将次 即对其15去摸 然后在对其刚才的约数 看是否有重复 如果有重复就 终止 并
移除此项
这是m1(x)的值 我们采用a4+a+1=0 来进行简化得 （注意：这里采用an+a+1它是an+1的一个因式，也可以采用an+1的其他因式，最好是采用最高次为n次的项，其他是否可以我没有测试）
注意：十进制的加法、减法在二进制中都是抑或，只有0 或者1
因此十进制相加后位偶数就位0 奇数就是1
m1(x)=x4+x+1？
a4=a+1
a5=a*a4=a*(a+1)=a2+a
a6=a*a5=a3+a2
a7=a*a6=a4+a3=a3+a+1
a8=a*a7=a*(a3+a+1)=a4+a2+a=a2+1
a9=a*a8=a(a2+1)=a3+a
a10=a*a9=a*(a3+a)=a4+a2=a2+a+1
a11=a*a10=a*(a2+a+1)=a3+a2+a
a12=a*a11=a*(a3+a2+a)=a4+a3+a2=a3+a2+a+1
a13=a*a12=a*(a3+a2+a+1)=a4+a3+a2+a=a3+a2+1
a14=a*a13=a*a3=a*(a3+a2+1)=a4+a3+a=a3+1
a15=a*a14=a*(a3+1)=a4+a=1=a0
Gf(16)中只有这十六个数
因此对应的数只有(0,a0,.....,a14)
然后我们将所得的结果带入刚才的公式m1（x）中
a+a2+a4+a8=(a+a4)+a2+a2+1=1+a2+a2+1=0
a3+a5+a9+a6+a10+a12=a3+(a2+a)+(a3+a)+(a3+a2)+
(a2+a+1)+(a3+a2+a+1)=0
a14+a13+a11+a7=(a3+1)+(a3+a2+1)+(a3+a2+a)+(a3+a+1)=1
a15=1；
因此m1（x）=x4+x+1
同理m3（x）等于m3（x）=（x+a3）(x+a6)(x+a12)(x+a24%15)
24%15=9前面几项中没有9因此 还要继续
m3（x）=（x+a3）(x+a6)(x+a12)(x+a9)(x+a(3*16)%15)
(3*16)%15)=3 前面几项中已存在因此 此项移除即
m3（x）=（x+a3）(x+a6)(x+a12)(x+a9)
=x4+(a3+a6+a9+a12)x3+(a9+a15+a12+a18+a15+a21)x2+x(a21+a18+a24+a27)+a30
=x4+(a3+a6+a9+a12)x3+(a9+a12+a18+a21)x2+x(a21+a18+a24+a27)++a30
=x4+(a3+a6+a9+a12)x3+(a9+a12+a3+a6)x2+x(a6+a3+a9+a12)+1
a3+a6+a9+a12=a3+(a3+a2)+(a3+a)+(a3+a2+a+1)=1
m3（x）=x4+x3+x2+x+1
次项关系式任何来的a4+a+1=0
f(x)=x4+x+1 他其实是x15+1的约多项式
因此我们在选择的时候本源多项式的时候 就选择f(x)=xlog2(n+1)+x+1
首先我们通过
若循环码的生成多项式具有如下形式（g(x)为最小公倍数）
g(x)=LCM[m1(x),m2(x),m3(x)..m2t−1(x)]
由于偶数项与前面的奇数项为共轭根系，有相同的最小多项式
因此g(x)=LCM[m1(x),m3(x)..m2t−1(x)]
例如:bch(15,5) n=4 t=3
g(x)=LCM[m1(x),m3(x),m5(x)]=m1(x)*m3(x)*m5(x)=(x4+x+1)*(x4+x3+x2+x+1)*(x2+x+1)=x10+x8+x5+x4+x2+x+1
Bch编码原理：
将未编码的k位数据记为多项式：
m(x)=m0+m1*x^1+m2*x^2+...+mk-1*x^k-1;其中mi属于{0,1}
将生成多项式记为：
g(x)=g0+g1*x1+g2*x^2+...+gr*x^r,其中r=m*t，校验位记为r(x)，则
r(x)=x^r*m(x) mod g(x)
编码后的BCH码字多项式可记为：
C(x)=x^r*m(x)+x^r*m(x) mod g(x)
BCH编码实现的关键是通过除法电路得到校验位多项式。编码的过程可总结为：
1.将m(x)左移r位，得到x^r*m(x)；
2.用生成多项式g(x)除以x^r*m(x)，得到校验位多项式r(x)；
3.得到码元多项式C(x)=x^r*m(x)+x^r*m(x) mod g(x)。
bch的生成多项g(x) 这里只支持bch(n,k);log2(n+1) 为整数，例如:7，15，31等。
多项式模2除法：
10111/11
10101
11000
01101
1100
0001 余数为1
1：
例如：数据码：00101
效验码：0011011100
bch编码：00101 0011011100（即数据码+校验码）
二、将bch编码与101010000010010进行抑或（bch编码为15位，其他的自己去查查就ok了）
xor：101010000010010
信息码：100000011001110
代码：
package com;
import java.util.*;
/**
* bch code码生成工具类
* Created by Administrator on 2020/5/22.
*/
public class makeBchCode {
public int[] bchCsArr;//二维码 bch数组 记录(n,k)
public int zgcNum;//最该此项 方便记录本源多项式 zgcNum=log2(n+1)
public String[] eleelementsArr;//存储元素数组
public LinkedHashMap<Integer, Map<Integer, Integer>> bcdCodeMap=new LinkedHashMap<Integer, Map<Integer, Integer>>();//bchcode集合
public String bchScCode;
public String bchCode;
public String infoCode="";
public String data;
public Map<Integer,String> xorMap=new HashMap<Integer, String>();
//a4+a+1=0;
public makeBchCode(){}
public makeBchCode(int[] bchCsArr,String data){
this.bchCsArr=bchCsArr;
this.zgcNum= (int) (Math.log(bchCsArr[0]+1) / Math.log(2));
this.data=data;
if(stringEjzZhSjz(data)==0){
//bchCode=xorMap.get(bchCsArr[0]);
for(int i=0;i<bchCsArr[0]-bchCsArr[1];i++){
bchCode+="0";
}
infoCode=data+bchCode;
return;
}
makeXorMap();
makeEle();
mkEwmBchCode();
mkBchCode();
}
/*
*xor集合生成
* */
public void makeXorMap(){
xorMap.put(15,"101010000010010");
}
/*
* 生成元素表方法
*采用迭代的方式 如果指数小于zgcNum 其值就是本身 a0=1 a2zgcNum=1
* 如果指数等于zgcNum=a+1 即a zgcNum=a+1;
* 如果指数大于zgcNum 即将指数为zgcNum的转换为zgcNum=a+1 在进行计算 注：需要移除通向项;
* */
public void makeEle(){
eleelementsArr=new String[(int)Math.pow(zgcNum,2)];
for(int i=0;i<eleelementsArr.length;i++){
if(i==0||i==eleelementsArr.length-1){
eleelementsArr[i]="0";
}else if(i<zgcNum){
eleelementsArr[i]=i+"";
}else if(i==zgcNum){
eleelementsArr[i]="10";
}else{
String slast=eleelementsArr[i-1];
String sbf="";
String[] ar=slast.split("");
for(int j=0;j<ar.length;j++){
if(Integer.valueOf(ar[j])+1==zgcNum){
sbf+=("10");
}else{
sbf+=(Integer.valueOf(ar[j])+1)+"";
}
}
ArrayList<String> strInt=new ArrayList<String>();
for(int l=0;l<sbf.length();l++){
String s=sbf.substring(l,l+1);
if(sbf.lastIndexOf(s)>sbf.indexOf(s)&&(strInt.isEmpty()||!strInt.contains(s))){
strInt.add(s);
}
}
if(!strInt.isEmpty()){
for(int l=0;l<strInt.size();l++){
sbf=sbf.replace(strInt.get(l),"");
}
}
eleelementsArr[i]=sbf;
}
}
}
/*
* bchCode生成
* bchcode=数据码/生成多项式 的余数
* infoCode生成 =bchCode 与 xor 掩码前的编码 进行抑或
* */
public void mkBchCode(){
int length=bchScCode.length()-bchScCode.indexOf("1")-1;
int a= stringEjzZhSjz(data)*(int)(Math.pow(2,length));
int b=stringEjzZhSjz(bchScCode);
String str=Integer.toBinaryString(a);
int c=0;
List<Integer> list=new ArrayList<Integer>();
while(true){
if(str==null||str.length()<bchScCode.length()){
break;
}
list.clear();
for(int i=0;i<bchScCode.length();i++){
if(bchScCode.substring(i,i+1).equals("1")){
list.add(str.length()-i-1);
}
}
for(int i=0;i<str.length();i++){
if(str.substring(i,i+1).equals("1")){
list.add(str.length()-i-1);
}
}
c=0;
for(int i=0;i<list.size();i++){
if(list.indexOf(list.get(i))==list.lastIndexOf(list.get(i))){
c+=Math.pow(2,list.get(i));
}
}
str=Integer.toBinaryString(c);
}
int len=bchCsArr[0]-bchCsArr[1]-str.length();
if(len>0){
for(int i=0;i<len;i++){
str="0"+str;
}
}
bchCode=data+str;
for(int i=0;i<bchCsArr[0];i++){
int num1=Integer.valueOf(bchCode.substring(i,i+1));
int num2=Integer.valueOf(xorMap.get(bchCsArr[0]).substring(i,i+1));
if(num1+num2==1){
infoCode+="1";
}else{
infoCode+="0";
}
}
}
/*
* bchScCode生成 由于我们不知道 t的值 因此也不知道 d 的值
* 但是可以得到 生成多项式的最高此项 就为bchCsArr[0]-bchCsArr[1]
* 因此当 指数大于他的时候 就退出循环
* */
public void mkEwmBchCode(){
for(int i=1;i<=7;i+=2){
if(!bcdCodeMap.isEmpty()){
int a=0;
for(int key:bcdCodeMap.keySet()){
int b=0;
for(int key2:bcdCodeMap.get(key).keySet()){
b=Math.max(b,key2);
}
a+=b;
}
if(a>=bchCsArr[0]-bchCsArr[1]){
break;
}
}
makeZxDxs(i);
}
List<Map<Integer,Integer>> listBch=new ArrayList<Map<Integer, Integer>>();
//bcdCodeMap
List<Integer> listBchJgList=new ArrayList<Integer>();
Map<Integer,Integer> map=new HashMap<Integer, Integer>();
Map<Integer,Integer> map2=new HashMap<Integer, Integer>();
for(int key:bcdCodeMap.keySet()){
listBch.add(bcdCodeMap.get(key));
}
for(int i=0;i<listBch.size();i++){
if(i==0){
map=listBch.get(0);
}
if(i<listBch.size()-1){
for(int key:listBch.get(i+1).keySet()){
for(int key1:map.keySet()){
listBchJgList.add(key+key1);
}
}
System.out.println("dcMap:"+listBchJgList);
map.clear();
map2.clear();
for(int j=0;j<listBchJgList.size();j++){
if(!map2.isEmpty()&&map2.containsKey(listBchJgList.get(j))){
continue;
}
int count=1;
for(int l=j+1;l<listBchJgList.size();l++){
if(listBchJgList.get(l)==listBchJgList.get(j)){
count++;
}
}
if(count%2==1){
map2.put(listBchJgList.get(j),1);
}else{
map2.put(listBchJgList.get(j),0);
}
}
listBchJgList.clear();
for(int key:map2.keySet()){
if(map2.get(key)!=0){
map.put(key,1);
}
}
}
}
if(!map.isEmpty()){
bchScCode="";
for(int key:map.keySet()){
if(bchScCode.length()<=key){
String str="1";
for(int i=0;i<key-bchScCode.length();i++){
str+="0";
}
bchScCode=str+bchScCode;
}else{
bchScCode=bchScCode.substring(0,key)+"1"+bchScCode.substring(key+1,bchScCode.length());
}
}
}
System.out.println("jhMap:"+map);
}
/*
* 生成最小多项式
* mi（x）=（x+a(i))(x+a(i*2)(x+a(i*2*2))....
*注意：当i*2n如果此值大于2的15次方就需要将次 即对其15去摸 然后在对其刚才的约数 看是否有重复 如果有重复就 终止 并
*移除此项
* */
public void makeZxDxs(int num){
Stack stack=new Stack<Class<bchDxs>>();
bchDxs bch;
LinkedHashMap<Integer,List<Integer>> backDxsZkMap;
List<Integer> listRootXs=new ArrayList<Integer>();
while(true){
if(stack.isEmpty()){
backDxsZkMap=new LinkedHashMap<Integer,List<Integer>>();
listRootXs.add(num);
}else{
int rootXs= (int) (num*Math.pow(2,listRootXs.size()));
rootXs=(rootXs>bchCsArr[0])?(rootXs%bchCsArr[0]):rootXs;
if(listRootXs.contains(rootXs)){
break;
}
listRootXs.add(rootXs);
bch=(bchDxs)stack.peek();
backDxsZkMap=bch.dxsZkMap;
}
bchDxs bds=new bchDxs(listRootXs.size(),num,backDxsZkMap);
stack.add(bds);
}
bch=(bchDxs)stack.peek();
dxsJh(bch.dxsZkMap,num);
}
/*
* 多项式简化（利用元素表）
* 多项式简化的时候 有一个小技巧（如果不会只能自己将多项式系数的元素表的转换来进行抑或运算）
* 例如：a+a2+a4+a8=a+a2+a+1+a2+1 进行抑或运算(a+a)+(1+1)+(a2+a2)=0
* 由于我们最小多项式的系数不是0 就是1 因此只要我们将多项式的系数转换成运算表进行计算
* 只要是偶数 就为0 只要是奇数 就为1 偶数全部抑或掉了 奇数表示有某一项没有抑或掉 就是1
* */
public void dxsJh(LinkedHashMap<Integer,List<Integer>> dxsZkMap,int num){
Map<Integer,Integer> map=new HashMap<Integer, Integer>();
StringBuffer sbf;String str="";
for(int key:dxsZkMap.keySet()){
sbf=new StringBuffer("");
for(int i=0;i<dxsZkMap.get(key).size();i++){
int a=dxsZkMap.get(key).get(i)%15;
sbf.append(eleelementsArr[a]);
}
if(sbf.length()%2==1){
map.put(key,1);
}
}
bcdCodeMap.put(num,map);
System.out.println(num+"map:"+map);
}
/*
* 二进制字符串转换为 十进制
* */
public int stringEjzZhSjz(String str){
int a=0;
if(str!=null&&str.length()>0){
for(int i=0;i<str.length();i++){
if(str.substring(i,i+1).equals("1")){
a+=Math.pow(2,str.length()-i-1);
}
}
}
return a;
}
/*
* 进行多项式展开需要将f(n)x=f(n-1)x*(x+a(n*2*2)%bchCsArr[0])
* 因此采用深度算法
*
* 采用错位相加法 例如：f(n-1)x=b0x(n-1)+b1x(n-2)+...+b(n-1)x0
* f(n)x=(b0x(n-1)+b1x(n-2)+...+b(n-1)x0)(x+c)
* =b0x(n-1+1)+b1x(n-2+1)+...+b(n-1)x0+1
* + cb0x(n-1)+cb1x(n-2)+...+cb(n-2)x1+cb(n-1)x0
* =b0x(n-1+1)+(b1+cb0)x(n-1)+...+(b(n-1)+cb(n-1))x1+cb(n-1)x0
* 下面的集合就是记录每个多项式的系数
* */
class bchDxs{
public int deep;//展开的深度也就是n
public int lcmDeep;//lcm函数的深度
public LinkedHashMap<Integer,List<Integer>> backDxsZkMap;//f(n-1)x的多项式展开集合
public LinkedHashMap<Integer,List<Integer>> dxsZkMap=new LinkedHashMap<Integer, List<Integer>>();//f(n)x的多项式展开集合
public bchDxs(){}
public bchDxs(int deep,int lcmDeep,LinkedHashMap<Integer,List<Integer>> backDxsZkMap){
this.backDxsZkMap=backDxsZkMap;
this.deep=deep;
this.lcmDeep=lcmDeep;
makeBchDxs();
}
public void makeBchDxs(){
if(deep==1){
List<Integer> list1=new ArrayList<Integer>();
List<Integer> list0=new ArrayList<Integer>();
list1.add(0);
list0.add(lcmDeep);
dxsZkMap.put(1, list1);
dxsZkMap.put(0,list0);
return;
}
int a= (int) (lcmDeep*Math.pow(2,deep-1));
for(int key:backDxsZkMap.keySet()){
List<Integer> listKey=new ArrayList<Integer>();
if(key==deep-1){
listKey.add(0);
dxsZkMap.put(deep,listKey);
}else{
for(int i=0;i<backDxsZkMap.get(key).size();i++){
listKey.add(backDxsZkMap.get(key).get(i));
}
if(backDxsZkMap.containsKey(key+1)){
for(int i=0;i<backDxsZkMap.get(key+1).size();i++){
listKey.add(a+backDxsZkMap.get(key+1).get(i));
}
}
dxsZkMap.put(key+1,tcCf(listKey));
if(key==0){
List<Integer> listLast=new ArrayList<Integer>();
listLast.add(a+backDxsZkMap.get(key).get(0));
dxsZkMap.put(key,listLast);
}
}
}
System.out.println(dxsZkMap);
}
/*
* 数组里面剔除重复的 因为重复的抑或后为0
* */
public List<Integer> tcCf(List<Integer> listKey){
List<Integer> list=new ArrayList<Integer>();
for(int i=0;i<listKey.size();i++){
if(listKey.lastIndexOf(listKey.get(i))>listKey.indexOf(listKey.get(i))){
continue;
}
list.add(listKey.get(i));
}
return list;
}
}
public static void main(String[] args) {
int[] arr=new int[]{15,5};
String aa="10010";
String[] aaa=new String[]{"10000","10001","10010","10011","10100","10101","10110","10111"};
for(int i=0;i<8;i++){
makeBchCode m=new makeBchCode(arr,aaa[i]);
System.out.println("aa[i]"+aaa[i]);
System.out.println("infoCode"+m.infoCode);
}
}
}