NAND 메모리의 bit에 에러가 발생하면 원하는 동작이 안되겠죠. 오류를 검출하고 수정하는 ECC 알고리즘 중 하나인 Hamming Code에 대해 알아보겠습니다.
Hamming Code
Hamming Code는 데이터 전송 중 발생할 수 있는 오류를 검출하고 교정하기 위해 사용하는 에러 검출 및 수정 코드(ECC)입니다.
특징
- Hamming Code는 한 비트의 오류를 검출하고 수정할 수 있습니다.
- 두 비트의 오류는 검출 가능하지만 수정할 수는 없습니다.
원리
Hamming Code는 데이터 비트와 패리티 비트를 사용하여 전송된 데이터의 오류를 검출합니다. 이 과정은 다음과 같이 이루어집니다.
1. 패리티 비트 삽입
- 번째 위치에 패리티 비트를 추가합니다.
- 각 패리티 비트는 특정 데이터 비트를 감시합니다. 아래의 그래프를 참고해주세요.
2. 패리티 비트 계산
- 각 패리티 비트는 자신의 감시 영역에서 비트 값의 합이 짝수(또는 홀수)가 되도록 설정됩니다.
- ex) 짝수 패리티를 사용할 경우, 감시하는 비트의 합이 짝수가 되도록 설정합니다.
3. 오류 검출 및 수정
- 수신된 데이터에서 모든 패리티 비트를 확인하여 오류가 있는지 검출합니다.
- 오류 위치를 계산하여 해당 비트를 반전시켜 수정합니다.
- Encoded data bits에서 p1, p2, p4, p8, p16은 패리티비트입니다. 모두 위치에 있습니다.
- 각 패리티 비트별로 담당하고 있는 데이터 비트들이 있습니다. 아래에 x표시가 해당 데이터 비트들입니다.
- 각 데이터 비트들의 합이 짝수인지, 홀수인지(1의 개수가 홀수인지 짝수인지)를 보고 짝수면 패리티비트는 0, 홀수면 1로 설정합니다. 저는 패리티 비트까지 더해서 짝수가 되도록 만들었습니다.
사용자 마음 - 이제 데이터를 전송하고 받은 쪽에서 패리티비트를 다시 연산해서 기존의 패리티비트와 비교했을 때, 어느 데이터 비트가 다른지 찾을 수 있습니다. 그 비트를 반전시키면 됩니다.
어떻게 비교하고 어디에 문제있는지 어떻게 알아요?
기존의 패리티 비트와 데이터를 전송받은 slave에서 새롭게 계산한 패리티 비트를 비교합니다. 이 비교는 기존의 패리티 비트에 새로운 패리티 비트를 xor하여 달라진 경우에만 1이 되도록 해서 비교합니다. p16, p8, p4, p2, p1을 기준으로, p2, p4가 잘못되었다면, xor한 결과가 00110이 되겠죠. 00110은 10진수로 6입니다. 따라서 bit position이 6인 d3에 오류가 있다는 뜻이고 이를 반전시키면 됩니다. 이것이 가능한 이유는 패리티 비트를 2의 거듭제곱에 해당하는 위치에 배정하기 때문입니다.
코드 설계(Verilog)
인프런 삼코치님의 강의 참고
Module
module encoder(A, B); //hamming code만드는 encoder
input[16:1] A; //원본 data code
output[1:21] B; //parity bit를 포함한 hamming code
buf u2(B[3], A[1]);
buf u3(B[5], A[2]);
buf u4(B[6], A[3]);
buf u5(B[7], A[4]);
buf u6(B[9], A[5]);
buf u7(B[10], A[6]);
buf u8(B[11], A[7]);
buf u9(B[12], A[8]);
buf u10(B[13], A[9]);
buf u11(B[14], A[10]);
buf u12(B[15], A[11]);
buf u13(B[17], A[12]);
buf u14(B[18], A[13]);
buf u15(B[19], A[14]);
buf u16(B[20], A[15]);
buf u17(B[21], A[16]);
// Caluclating Parity Bits, xor로 1의 개수를 체크
xor p1(B[1], B[3], B[5], B[7], B[9], B[11], B[13], B[15], B[17], B[19], B[21]);
xor p2(B[2], B[3], B[6], B[7], B[10], B[11], B[14], B[15], B[18], B[19]);
xor p4(B[4], B[5], B[6], B[7], B[12], B[13], B[14], B[15], B[20], B[21]);
xor p8(B[8], B[9], B[10], B[11], B[12], B[13], B[14], B[15]);
xor p16(B[16], B[17], B[18], B[19], B[20], B[21]);
//Calculation of Parity bits completed
endmodule
module decoder_ham( //새로운 parity비트 기반 new코드(op) 생성
var1, var2, var3, var4, var5, op1, op2, op3, op4, op5, op6, op7,
op8, op9, op10, op11, op12, op13, op14, op15, op16,
op17, op18, op19, op20, op21, op22
);
input var1, var2, var3, var4, var5;
output op1, op2, op3, op4, op5, op6, op7, op8, op9, op10, op11,
op12, op13, op14, op15, op16, op17, op18, op19, op20, op21, op22;
assign op1 = ~var1 & ~var2 & ~var3 & ~var4 & ~var5;
assign op2 = ~var1 & ~var2 & ~var3 & ~var4 & var5;
assign op3 = ~var1 & ~var2 & ~var3 & var4 & ~var5;
assign op4 = ~var1 & ~var2 & ~var3 & var4 & var5;
assign op5 = ~var1 & ~var2 & var3 & ~var4 & ~var5;
assign op6 = ~var1 & ~var2 & var3 & ~var4 & var5;
assign op7 = ~var1 & ~var2 & var3 & var4 & ~var5;
assign op8 = ~var1 & ~var2 & var3 & var4 & var5;
assign op9 = ~var1 & var2 & ~var3 & ~var4 & ~var5;
assign op10 = ~var1 & var2 & ~var3 & ~var4 & var5;
assign op11 = ~var1 & var2 & ~var3 & var4 & ~var5;
assign op12 = ~var1 & var2 & ~var3 & var4 & var5;
assign op13 = ~var1 & var2 & var3 & ~var4 & ~var5;
assign op14 = ~var1 & var2 & var3 & ~var4 & var5;
assign op15 = ~var1 & var2 & var3 & var4 & ~var5;
assign op16 = ~var1 & var2 & var3 & var4 & var5;
assign op17 = var1 & ~var2 & ~var3 & ~var4 & ~var5;
assign op18 = var1 & ~var2 & ~var3 & ~var4 & var5;
assign op19 = var1 & ~var2 & ~var3 & var4 & ~var5;
assign op20 = var1 & ~var2 & ~var3 & var4 & var5;
assign op21 = var1 & ~var2 & var3 & ~var4 & ~var5;
assign op22 = var1 & ~var2 & var3 & ~var4 & var5;
endmodule
module Hamming_decoder(A, B, var1, var2, var3, var4, var5, op1, op2, op3,
op4, op5, op6, op7, op8, op9, op10, op11, op12, op13,
op14, op15, op16, op17, op18, op19, op20, op21, op22);
input[21:1] A;
output[15:0] B;
output var1, var2, var3, var4, var5;
// 새로운 parity bit(var) 생성(even parity property)
xor p1(var1, A[1], A[3], A[5], A[7], A[9], A[11], A[13], A[15], A[17], A[19], A[21]);
xor p2(var2, A[2], A[3], A[6], A[7], A[10], A[11], A[14], A[15], A[18], A[19]);
xor p4(var3, A[4], A[5], A[6], A[7], A[12], A[13], A[14], A[15], A[20], A[21]);
xor p8(var4, A[8], A[9], A[10], A[11], A[12], A[13], A[14], A[15]);
xor p16(var5, A[16], A[17], A[18], A[19], A[20], A[21]);
//생성 끝
output op1, op2, op3, op4, op5, op6, op7, op8, op9, op10, op11,
op12, op13, op14, op15, op16, op17, op18, op19, op20, op21, op22;
// Using utility module to find the error location
// op1 is high when there is no error
decoder_ham d1(var5,var4,var3,var2,var1,op1, op2, op3, op4, op5, op6,
op7, op8, op9, op10, op11, op12, op13, op14, op15, op16,
op17, op18, op19, op20, op21, op22);
// error position calculated
// Copying message bits into the output cable with appropriate xoring to remove error
xor alpha1(B[0], op4, A[3]);
xor alpha2(B[1], op5, A[4]);
xor alpha3(B[2], op7, A[6]);
xor alpha4(B[3], op8, A[7]);
xor alpha5(B[4], op10, A[9]);
xor alpha6(B[5], op11, A[10]);
xor alpha7(B[6], op12, A[11]);
xor alpha8(B[7], op13, A[12]);
xor alpha9(B[8], op14, A[13]);
xor alpha10(B[9], op15, A[14]);
xor alpha11(B[10], op16, A[15]);
xor alpha12(B[11], op18, A[17]);
xor alpha13(B[12], op19, A[18]);
xor alpha14(B[13], op20, A[19]);
xor alpha15(B[14], op21, A[20]);
xor alpha16(B[15], op22, A[21]);
// Output cable completely specified
endmoduleTestBench
module tb_Hamming_decoder;
reg[16:1] input_message; // Input to the encoder module
wire[21:1] encoded_message; // Output from the encoder module, the encoded bit stream
wire[16:1] decoded_message; // Output from the decoder module, the decoded bit stream
reg[21:1] enc_message; // Bit Stream formed after inserting the error by flipping one bit of encoded message
reg[21:1] enc_message_2; // Reverse of enc_message that goes as input to decoder
reg[1:21] error = 21'b000000000000000000001;
wire var1, var2, var3, var4, var5, op1, op2, op3, op4, op5, op6, op7, op8, op9, op10, op11, op12, op13, op14, op15, op16, op17, op18, op19, op20, op21, op22;
encoder enc_mod(input_message, encoded_message);
Hamming_decoder dec_mod(enc_message_2, decoded_message, var1, var2, var3, var4, var5, op1, op2, op3, op4, op5, op6, op7, op8, op9, op10, op11, op12, op13, op14, op15, op16, op17, op18, op19, op20, op21, op22);
always begin
#20 input_message = 16'b1100101000111011; // Initialising the input message ==Change this for different Messages==
#20 assign enc_message = encoded_message ^ error; // Error 생성하기
// Reversing enc_message and saving it in enc_message_2
enc_message_2[1]=enc_message[21];
enc_message_2[2]=enc_message[20];
enc_message_2[3]=enc_message[19];
enc_message_2[4]=enc_message[18];
enc_message_2[5]=enc_message[17];
enc_message_2[6]=enc_message[16];
enc_message_2[7]=enc_message[15];
enc_message_2[8]=enc_message[14];
enc_message_2[9]=enc_message[13];
enc_message_2[10]=enc_message[12];
enc_message_2[11]=enc_message[11];
enc_message_2[12]=enc_message[10];
enc_message_2[13]=enc_message[9];
enc_message_2[14]=enc_message[8];
enc_message_2[15]=enc_message[7];
enc_message_2[16]=enc_message[6];
enc_message_2[17]=enc_message[5];
enc_message_2[18]=enc_message[4];
enc_message_2[19]=enc_message[3];
enc_message_2[20]=enc_message[2];
enc_message_2[21]=enc_message[1];
//reversing completed
#10 error = error<<1;
end
initial #1200 $finish;
endmoduleWaveform
Reference
https://medium.com/@jrandazz/explore-hamming-codes-2c241a29a726
반도체, HW ,SW 탐구생활