Hamming Code

ディジタル・エラー訂正技術入門という本を使って、誤り訂正符号を勉強しています。この本は「何をどこまで理解したら、誤り訂正符号を回路に実装できるか」という極めて実用的な観点から書かれています。とても分かりやすいです。ただ、数学的には、ちょっと説明不足かな？？？と思う箇所が多々あります。

ハミング符号の章を読み終わったので、Matlabでハミング符号のencoderとdecoderを記述してみました。このDSP blogというサイトとかも参考にしています。

clear all;

rand('state', 123);
M=5;
numData=40;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Define Generate Polynomial
switch M
   case 2
       % Hamming Code [3, 1]
       % Generate Polynomial X^2+X+1 
       %                   = X^2*GenPol(3) + X*GenPol(2) + GenPol(1)
       GenPol = [1, 1, 1];
   case 3
       % Hamming Code [7, 4]
       % Generate Polynomial X^3+X+1 
       %                   = X^3*GenPol(4) + X^2*GenPol(3) + X*GenPol(2) + GenPol(1)
       GenPol = [1, 1, 0, 1];
   case 4
       % Hamming Code [15, 11]
       % Generate Polynomial X^4+X+1 
       %                   = X^4*GenPol(5) + X^3*GenPol(4) + X^2*GenPol(3) + X*GenPol(2) + GenPol(1)
       GenPol = [1, 1, 0, 0, 1];
   case 5
       % Hamming Code [31, 26]
       % Generate Polynomial X^5+X^2+1 
       GenPol = [1, 0, 1, 0, 0, 1];
   case 6
       % Hamming Code [63, 57]
       % Generate Polynomial X^6+X+1 
       GenPol = [1, 1, 0, 0, 0, 0, 1];
end
N=2^M-1;
K=N-M;


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Gneration Matrix, 
%   in case of Hamming Code [7, 4]
%    parity_matrix = [a^6;   =  [1, 0, 1; 
%                     a^5;   =   1, 1, 1; 
%                     a^4;   =   1, 1, 0; 
%                     a^3;]; =   0, 1, 1;];
%    G = [eye(4), parity_matrix];
%    ShiftReg = [1, a^1, a^2]

% Calculate all elements of GF(2^M)
ShiftReg=zeros(1, M);
ShiftReg(1)=1;

% a{i} is a^(i-1), element of GF(2^M)
% a{1} is a^0
a{1} = ShiftReg;
% Shift (M-1) times
for i=1:(N-1)
   ShiftReg_next(1)=xor(0, GenPol(1)*ShiftReg(M));
   for j=2:M
      ShiftReg_next(j) = xor(ShiftReg(j-1), GenPol(j)*ShiftReg(M));
   end
   ShiftReg = ShiftReg_next;
   % a{i+1} is a^i
   a{i+1} = ShiftReg;
end

% Create Parity Matrix 
%   in case of [7,4], parity_matrix = [a^6; a^5; a^4; a^3; a^2; a^1; a^0;];
for i=M:N-1
   parity_matrix(N-i,:)=fliplr(a{i+1});
end

% Crate Gneration Matrix
G = [eye(K), parity_matrix];


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Parity Check Matrix, 
%   in case of Hamming Code [7, 4]
%     H=[1, 1, 1, 0, 1, 0, 0; 
%        0, 1, 1, 1, 0, 1, 0; 
%        1, 1, 0, 1, 0, 0, 1;];

% Create Parity Check Matrix 
%   in case of [7,4], H = [a^6; a^5; a^4; a^3;];
for i=1:N
   H(:, N-i+1)=fliplr(a{i});
end


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Coding and Decoding

numError=0;

for i=[1:numData]
   msg = gen_dat(K);
   coded_msg = mod(msg*G, 2);

   % Add error to only 80% of trials
   err = zeros(1, N);
   add_err = rand > 0.2;
   if (add_err)
      % add 1bit error to randomly chosen location
      err( fix(rand*N)+1 ) =1;
   end

   rcv_msg = mod(coded_msg + err, 2);

   % Error syndrome
   err_syndrome = mod(rcv_msg*H', 2);

   % Find error location
   ShiftReg=zeros(1, M);
   ShiftReg=fliplr(err_syndrome);
   % Shift N times
   for i=1:N
      ShiftReg_next(1)=xor(0, GenPol(1)*ShiftReg(M));
      for j=2:M
         ShiftReg_next(j) = xor(ShiftReg(j-1), GenPol(j)*ShiftReg(M));
      end
      ShiftReg = ShiftReg_next;
      err_location(i)=ShiftReg(1)&(~any(ShiftReg(2:end)));
   end

   % Add correction
   fixed_msg = rcv_msg;
   fixed_msg(err_location) = ~fixed_msg(err_location);

   % Check if error is corrected properly. Compare msg and fixed_msg(1:K)
   if (~any(msg - fixed_msg(1:K)))
      if (add_err) 
         disp('error corrected');
      else 
         disp('error NOT added');
      end
   else 
      numError=numError+1;
      disp('NOT CORRECTED');
   end
end

if (~numError) 
   disp('Test Completed Successfully');
end