Kodowanie korekcyjne błędów
Autorzy: Andrzej R. Pach, Piotr Chołda
Pliki: rozdzial_21.zip
Zamieszczono jedynie te przykłady z książki, które zawierają opracowane programy w MATLABie. Inne przykłady, mające charakter ilustracji, zostały tutaj pomienięte.
Przykład 21.3
Przykład w języku MATLAB pokazuje, jak oblicza się wartości ciągów kodowych z użyciem funkcji dod_bit_parz (plik dod_bit_parz.m), przy zadanych ciągach informacyjnych, stosując kod z kontrolą parzystości.% Przykład 21.03
function x = dod_bit_parz(u)
% Funkcja dodaje bit parzystości na koniec ciągu zadanego zmienną u
m = length(u); bit = 0; x = 0;
for j=1:m
bit = mod(u(j)+bit,2); % mod - suma bitowa modulo dwa
end
x = [u,bit];
Przykład 21.4
Przykład w języku MATLAB pokazuje z użyciem funkcji prawd_kontr_parz (plik prawd_kontr_patrz.m), w jaki sposób zależność (21.7) podana na stronie 812 zmienia się przy różnych wartościach p oraz n.% Przykład 21.04 function wynik = prawd_kontr_parz(P) % Funkcja rysuje wykres zależności dla zadanej wartości prawdopodobieństwa zadanego zmienną P nmin = 1; krok = 1; nmax = 100; n = nmin:krok:nmax; p1 = ((n-1)*P).*((1-P).^(n-1)); figure(1); plot(n,p1); grid on;
Przykład 21.5
Przykład w języku MATLAB pokazuje z użyciem funkcji gen_kod_lin (plik gen_kod_lin.m), jak na podstawie macierzy G otrzymywać ciągi kodowe.% Przykład 21.05
function [X,dmin] = gen_kod_lin(G)
% Funkcja generuje słowa kodu liniowego o zadanej macierzy generującej zadanej jako zmienna G
% Podaje również odleglość minimalną dla tego kodu oraz znajduje słowa kodowe
% Np. G = [1 0 0 1; 0 1 0 1; 0 0 1 1] dla kodu (3,4) z kontrolą parzystości
[k,n] = size(G);
if(k>n)
disp('Błędna macierz generująca! k>n');
else
dmin=n;
X = [];
for i=0:2^k-1
u=dec2bin(i,k)-'0';
x=mod(u*G,2);
X = [X; x];
fprintf('u = [%s] odpowiada x = [%s]\n', num2str(u), num2str(x));
d=mean(x)*n;
if(i>0 & dmin>d)
dmin=d;
end
end
end
Przykład 21.6
Przyklad w jezyku MATLAB pokazuje z uzyciem funkcji ham_cod_corr (plik ham_cod_corr.m), jak mozna korygowac bledy jednokrotne za pomoca kodu Hamminga.% Przykład 21.06
function x = ham_cod_corr(y)
% Funkcja koryguje słowo zadane zmienną y, otrzymane po przesłaniu poprawnego ciągu kodu
% Hamminga (2^r-1,2^r-1-r) przez kanał
n = length(y); r = log(n+1)/log(2);
if(r~=floor(r) || r~=ceil(r))
disp('To nie jest odpowiednia długość słowa kodowego!');
else
k = n-r;
fprintf('To jest kod (%d,%d) o macierzy testów parzystości:\n',n,k);
H = [zeros(r-1,1);1];
for i=2:2^r-1
H = [H transpose(dec2bin(i,r)-'0')];
end
disp(H);
syndrom = mod(y*transpose(H),2);
fprintf('Syndrom dla y = [%s] to s = [%s], zatem:\n',...
num2str(y),num2str(syndrom));
if(mean(syndrom) == 0)
fprintf('przyjmujemy, ze nie wystąpiło przekłamanie.\n');
else
pozycja = bin2dec(num2str(syndrom));
fprintf('przyjmujemy, ze przekłamanie wystąpiło na pozycji nr %d,\n',...
pozycja);
y(pozycja) = mod(y(pozycja)+1,2);
x=y;
fprintf('a wysłano słowo kodowe [%s].\n',num2str(y));
end
end
Przykład 21.8
Przykład w języku MATLAB pokazuje z użyciem funkcji mnoz_wiel_bin (plik mnoz_wiel_bin.m) dostarczonej z książką T.K. Moona "Error Correction Coding" [2], jak można mnożyć wielomiany.% Przykład 21.08
function w = mnoz_wiel_bin(p,q)
% Funkcja mnoży wielomiany zadane zmiennymi p i q i zwraca w(x)
% Współczynniki wielomianów sś reprezentowane od najwyższej potęgi:
% x^3 + x + 1 = [1 0 1 1]
% Spolszczona wersja programu dostarczonego wraz z książką
% T.K. Moona "Error Correction Coding"
m = 2; % GF(2) - współczynniki binarne
if(all(p==0) | all(q==0))
w = 0;
else
w = mod(conv(p,q),m);
end
Przykład 21.9
Przykład w języku MATLAB pokazuje z użyciem funkcji dziel_wiel_bin (plik dziel_wiel_bin.m) dostarczonej z książką T.K. Moona "Error Correction Coding" [2], jak można dzielić wielomiany.% Przykład 21.09
function [w,r] = dziel_wiel_bin(p,q)
% Funkcja dzieli wielomiany zadane zmiennymi p i q i zwraca wynik w oraz resztę r
% Współczynniki wielomianów są reprezentowane od najwyższej potęgi:
% x^3 + x + 1 = [1 0 1 1]
% Spolszczona wersja programu dostarczonego wraz z książką
% T.K. Moona "Error Correction Coding"
m = length(p); n = length(q); w = 0;
t = 2; % GF(2) - współczynniki binarne
b1inv = mod(q(1)^(t-2),t);
for j=1:m-n+1
w (j) = mod(p(j)*b1inv,t);
for l=2:n
p(l+j-1) = mod(p(l+j-1) - w(j)*q(l),t);
end
end
r = mod(p(m-n+2:m),t);
if(all(r==0))
r = 0;
end
Przykład 21.12
Przykład w języku MATLAB pokazuje z użyciem funkcji gen_mac_wiel(plik gen_mac_wiel.m), jak za pomocą wielomianu generującego wytworzyć macierze generujące.% Przykład 21.12
function [Gniesyst, Gsyst] = gen_mac_wiel(g,n)
% Funkcja wytwarza macierze generujące kodów niesystematycznego i
% systematycznego dla wielomianu generującego zadanego zmienną g
%
% Współczynniki wielomianów sa reprezentowane od najwyzszej potegi:
% x^3 + x + 1 = [1 0 1 1]
r = length(g) - 1; k = n - r;
if(k>n)
disp('Błędne dane, k>n!');
else
fprintf('Parametry kodu (%d,%d)\n',n,k);
Gniesyst = [];
for i=1:k
u = zeros(1,k);
u(i) = 1;
Gniesyst = [Gniesyst; mnoz_wiel_bin(u,g)];
end
fprintf('Macierz kodu niesystematycznego:\n');
disp(Gniesyst);
Gsyst = [];
for i=1:k
u = zeros(1,n);
u(i) = 1;
[w,r] = dziel_wiel_bin(u,g);
Gsyst = [Gsyst; [u(1:k) r]];
end
fprintf('Macierz kodu systematycznego:\n');
disp(Gsyst);
end