常见的编码
常见的编码
纠错编码（Error Correction Code, ECC）是一种在数据传输或存储过程中用来检测并纠正错误的技术。它通过添加冗余信息到原始数据中，使得接收端可以检测并纠正传输过程中可能发生的错误。以下是一些常见的纠错编码方法：
汉明码（Hamming Code）：
汉明码是最基本的线性纠错码之一，能够检测并纠正单比特错误。它的原理是通过增加校验位来实现错误检测与纠正。编码过程：
- 首先，将数据分成若干个8位的块，每一块的前8位为数据位，最后一位为校验位。
- 然后，将每一块的前8位进行异或操作，得到校验位。
- 最后，将校验位附加到数据位后面，得到编码后的信息。
解码过程：
- 首先，将编码后的信息分成若干个8位的块，每一块的前8位为数据位，最后一位为校验位。
- 然后，将每一块的前8位进行异或操作，得到校验位。
- 最后，对每一块的校验位进行校验，如果校验失败，则说明该块数据有错误，需要进行纠错。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
// 生成汉明码的主函数
void GetHammingcode();
// 计算汉明码并更新数据
void hamming(char data[], int *len, int paritytype);
// 在指定位置插入字符
void insert(char data[], int index, char c, int *len);
// 更新汉明码中的校验位
void updatecode(char data[], int index, int c);
// 校正汉明码的主函数
void CorrectHammingcode();
// 校正汉明码并恢复原始数据
void correct(char data[], int paritytype, int len);
// 获取校验位的计算
int GetP_i(char data[], int i, int len);
// 判断一个数字是否是2的幂
int isPowerof2(int num);
int main(){
while(1){
printf("\n\nPlease choose function: \n");
printf("(1. generate hamming code from given binary data 2. generate original data from given hamming code)\n");
int func;
scanf("%d", &func);
getchar();
switch (func){
case 1:
GetHammingcode();
break;
case 2:
CorrectHammingcode();
break;
}
printf("\n\nContinue? (Y: yes, continue N: no, quit)\n");
char c;
getchar();
scanf("%c", &c);
getchar();
if(c=='N') break;
}
}
// 获取输入数据并生成汉明码
void GetHammingcode(){
printf("Please input original data(e.g. 1010): \n");
char data[MAX_LEN]="";
scanf("%s", &data);
int *len=malloc(sizeof(int));
*len=strlen(data);
printf("Please input type of parity bit(s): \n(1. even perity bit(s) 2. odd parity bit(s)):\n");
int paritytype;
scanf("%d", &paritytype);
hamming(data, len, paritytype);
printf("\n\nResult: \n%s\n", data);
}
// 计算汉明码的具体实现
void hamming(char data[], int *len, int paritytype){
int n=strlen(data);
int k;
// calculate k, which is the total number of parity bit(s)
for(k=0; pow(2, k)<n+k+1; k++) ;
int i;
// insert blank positions of parity bit(s)
for(i=0; pow(2, i)<=n+k; i++){
insert(data, (int)pow(2, i)-1, 0, len);
}
// calculate actual value of parity bit(s)
for(i=0; i<n+k; i++){
if(data[i]!=0 && data[i]!=1){
updatecode(data, i, data[i]-'0');
}
}
// get final output
for(i=0; i<n+k; i++){
if(data[i]==0 || data[i]==1){
if(paritytype == 2) data[i]=data[i] ^ 1;
data[i]+='0';
}
}
}
// 在数据中指定位置插入字符
void insert(char data[], int index, char c, int *len){
// index: counts from 0
int i=*len;
while(i+1!=index){
char ch=data[i];
data[i+1]=ch;
i--;
}
i++;
data[i]=c;
(*len)++;
return;
}
// 更新汉明码中的校验位
void updatecode(char data[], int index, int c){
index++;
int rem, counter=0;
while(index!=0){
rem = index%2;
if(rem) {
int chindex=(int)(pow(2, counter)-1);
char ch=data[chindex] ^ c;
data[chindex]=ch;
}
index /= 2;
counter++;
}
}
// 打印数据
void infuncprint(char data[], int len){
int i=0;
while(i!=len) {
printf("%c", (data[i] == 0 || data[i] == 1) ? data[i]+'0' : data[i]);
i++;
}
printf("\n");
}
// 从汉明码中校正原始数据的主函数
void CorrectHammingcode(){
printf("Please input the hamming code(e.g. 11101001101): \n");
char data[MAX_LEN]="";
scanf("%s", &data);
printf("Please input type of parity bit(s): \n(1. even perity bit(s) 2. odd parity bit(s)):\n");
int paritytype;
scanf("%d", &paritytype);
int len=strlen(data);
correct(data, paritytype, len);
// printf("Original data is: \n");
}
// 校正汉明码并输出原始数据
void correct(char data[], int paritytype, int len){
int count=0;
int i;
int to_be_corrected=0;
for(i=0; pow(2, i)<=len; i++){
int pi=GetP_i(data, i, len);
if(paritytype == 2) pi=pi^1;
to_be_corrected += pi << i;
}
if(to_be_corrected){
if(data[to_be_corrected-1]=='0') data[to_be_corrected-1]='1';
else data[to_be_corrected-1]='0';
}
printf("\n\nOriginal data: \n");
for(i=0;i<len;i++){
if(!isPowerof2(i+1)) printf("%c", data[i]);
}
printf("\n");
}
// 获取指定校验位的值
int GetP_i(char data[], int i, int len){
int j;
int pi=0;
int power=(int)pow(2, i);
for(j=0; j<len; j++){
int condition=((j+1) == power) || (((j+1)>>i)%2 == 1);
if(!condition) continue;
pi ^= data[j]-'0';
}
return pi;
}
// 判断一个数字是否是2的幂
int isPowerof2(int num){
int i;
for(i=0; pow(2, i)<=num; i++){
if(pow(2, i)==num) return 1;
}
return 0;
}
评论