Здравствуйте!
Я перерыл весь этот форум, нашел даже две битые ссылки на книжки на тему LDPC (так и не скачал и не увидел), но в основном встречаются лишь вопросы от уже понимающих суть этого кодирования. В интернете тоже как-то слабо ищется, есть статьи где описывается вскользь, но может есть реально хорошая статья, подскажите.
Где увидеть максимально простейший пример на основе минимально возможного размера блока данных, где бы была пояснена сама суть.
P.S.
С другими помехоустойчивыми кодами работал, а этот как-то не приходилось, но хотелось бы понять его суть и программно реализовать простейший пример, протестировать его.
Полная версия этой страницы: LDPC на примере
Форум разработчиков электроники ELECTRONIX.ru > Цифровая обработка сигналов - ЦОС (DSP) > Алгоритмы ЦОС (DSP)
Цитата(AVR @ Aug 29 2016, 18:27) 
Здравствуйте!
Я перерыл весь этот форум, нашел даже две битые ссылки на книжки на тему LDPC (так и не скачал и не увидел), но в основном встречаются лишь вопросы от уже понимающих суть этого кодирования. В интернете тоже как-то слабо ищется, есть статьи где описывается вскользь, но может есть реально хорошая статья, подскажите.
Где увидеть максимально простейший пример на основе минимально возможного размера блока данных, где бы была пояснена сама суть.
P.S.
С другими помехоустойчивыми кодами работал, а этот как-то не приходилось, но хотелось бы понять его суть и программно реализовать простейший пример, протестировать его.
Я перерыл весь этот форум, нашел даже две битые ссылки на книжки на тему LDPC (так и не скачал и не увидел), но в основном встречаются лишь вопросы от уже понимающих суть этого кодирования. В интернете тоже как-то слабо ищется, есть статьи где описывается вскользь, но может есть реально хорошая статья, подскажите.
Где увидеть максимально простейший пример на основе минимально возможного размера блока данных, где бы была пояснена сама суть.
P.S.
С другими помехоустойчивыми кодами работал, а этот как-то не приходилось, но хотелось бы понять его суть и программно реализовать простейший пример, протестировать его.
Раз работали с другими кодами, значит должны понимать, что разницы, принципиально, никакой.
Todd K. Moon. Error Correction Coding: Mathematical Methods and Algorithms.
Example 15.6. Подробный разбор. Если нужно, то на старой машине поищу сами исходники, которые шли вмести с книгой. Вроде бы таковые имелись.
И example 15.7. Там уже разбирается Message Passing Algorithm (MPA), что ближе к практике.
Example 15.6. Подробный разбор. Если нужно, то на старой машине поищу сами исходники, которые шли вмести с книгой. Вроде бы таковые имелись.
И example 15.7. Там уже разбирается Message Passing Algorithm (MPA), что ближе к практике.
Можно начать с оригинальной статьи Gallager (именно статьи, а не дисера 1968 года, который чаще всего попадается при поиске):
http://coding.yonsei.ac.kr/gallager-ldpc.pdf
Там всего несколько страничек не очень сложного текста. Можно быстро понять о чем речь.
Затем можно перейти к чтению любимой и более-менее современной книжки по кодированию. У меня это второе издание Lin-Costello - там есть про графы Таннера и это все. В параллель можно изучить многочисленные буквари из интернета.
Дисер, кстати, тоже достаточно полезен - там, как и в статье, все на пальцах расписано, хотя и больше букв, чем в статье.
http://coding.yonsei.ac.kr/gallager-ldpc.pdf
Там всего несколько страничек не очень сложного текста. Можно быстро понять о чем речь.
Затем можно перейти к чтению любимой и более-менее современной книжки по кодированию. У меня это второе издание Lin-Costello - там есть про графы Таннера и это все. В параллель можно изучить многочисленные буквари из интернета.
Дисер, кстати, тоже достаточно полезен - там, как и в статье, все на пальцах расписано, хотя и больше букв, чем в статье.
посмотрите вложение - презентация
+
мой матлаб скрипт по презентации, которая во вложении
+
мой матлаб скрипт по презентации, которая во вложении
Код
H = [0 0 1 1 0 0 0 1 0 1 0 0;
1 0 0 0 1 0 0 0 1 0 1 0;
0 1 0 0 0 1 1 0 0 0 1 0;
0 0 1 0 1 0 1 0 0 0 0 1;
1 0 0 0 0 1 0 1 0 0 0 1;
0 1 0 1 0 0 0 0 1 1 0 0];
% alpha - from check to variable
% For this example:
% every check node have 4 connections to variable node
% beta - from variable to check
% For this example:
% every variable node have 2 connections to check node
% for simplicity make alpha and beta array the same size as H
[rows cols] = size(H);
N = cols; M = rows;
alpha = zeros(rows, cols);
beta = zeros(rows, cols);
is_syndrome_zero = false; % is received data ok?
iter_count = 10; % number of iterations
% original recieved information from the channel
received_word = [-9.1 4.9 -3.2 3.6 -1.4 3.1 0.3 1.6 -6.1 -2.5 -7.8 -6.8];
z = received_word;
% find estimated bits
v = zeros(1, length(z));
for i = 1:length(z)
if (z(i) > 0)
v(i) = 0;
else
v(i) = 1;
end
end
% make check for the recived vector
parity_check = mod(H * v', 2);
ones_in_parity = find(parity_check);
if (isempty(ones_in_parity))
is_syndrome_zero = true;
end
% if errors present in parity_check
% go to main loop
cur_iter = 0;
% init beta values with received information
for i = 1:N
ones_in_col = find(H(:, i));
for j = 1:length(ones_in_col)
beta(ones_in_col(j), i) = z(i);
end
end
while (~is_syndrome_zero && cur_iter < iter_count)
fprintf('Iteration: %d\n', cur_iter);
% horizontal step (alpha calculation)
for i = 1:M
% find indices of connected v-nodes
ones_in_row = find(H(i, :));
% find abs min value and its sign
for j = 1:length(ones_in_row)
min_value = realmax;
sign = 1;
% find min value among values with indices in
% ones_in_row except current index
for k = 1:length(ones_in_row)
if ones_in_row(k) ~= ones_in_row(j)
% value section
if (abs(beta(i, ones_in_row(k))) < min_value)
min_value = abs(beta(i, ones_in_row(k)));
end
% sign section
if beta(i, ones_in_row(k)) >= 0
sign = sign * 1;
else
sign = sign * (-1);
end
end
end
% assign min-sum value to the alpha
alpha(i, ones_in_row(j)) = min_value * sign;
end
end
% vertical step (calculate beta)
for i = 1:N
ones_in_col = find(H(:, i));
for j = 1:length(ones_in_col)
% sum with all connected alpha values except current
for k = 1:length(ones_in_col)
if ones_in_col(j) ~= ones_in_col(k)
beta(ones_in_col(k),i) = beta(ones_in_col(k), i) + alpha(ones_in_col(k), i);
end
end
end
end
% update z value
for i = 1:N
ones_in_col = find(H(:, i));
for j = 1:length(ones_in_col)
z(i) = z(i) + alpha(ones_in_col(j), i);
end
end
% check results of correction
for i = 1:length(z)
if (z(i) > 0)
v(i) = 0;
else
v(i) = 1;
end
end
disp('Z value:');
disp(z);
disp('V value:');
disp(v);
% make check for the recived vector
parity_check = mod(H * v', 2);
ones_in_parity = find(parity_check);
if (isempty(ones_in_parity))
is_syndrome_zero = true;
end
cur_iter = cur_iter + 1;
end
1 0 0 0 1 0 0 0 1 0 1 0;
0 1 0 0 0 1 1 0 0 0 1 0;
0 0 1 0 1 0 1 0 0 0 0 1;
1 0 0 0 0 1 0 1 0 0 0 1;
0 1 0 1 0 0 0 0 1 1 0 0];
% alpha - from check to variable
% For this example:
% every check node have 4 connections to variable node
% beta - from variable to check
% For this example:
% every variable node have 2 connections to check node
% for simplicity make alpha and beta array the same size as H
[rows cols] = size(H);
N = cols; M = rows;
alpha = zeros(rows, cols);
beta = zeros(rows, cols);
is_syndrome_zero = false; % is received data ok?
iter_count = 10; % number of iterations
% original recieved information from the channel
received_word = [-9.1 4.9 -3.2 3.6 -1.4 3.1 0.3 1.6 -6.1 -2.5 -7.8 -6.8];
z = received_word;
% find estimated bits
v = zeros(1, length(z));
for i = 1:length(z)
if (z(i) > 0)
v(i) = 0;
else
v(i) = 1;
end
end
% make check for the recived vector
parity_check = mod(H * v', 2);
ones_in_parity = find(parity_check);
if (isempty(ones_in_parity))
is_syndrome_zero = true;
end
% if errors present in parity_check
% go to main loop
cur_iter = 0;
% init beta values with received information
for i = 1:N
ones_in_col = find(H(:, i));
for j = 1:length(ones_in_col)
beta(ones_in_col(j), i) = z(i);
end
end
while (~is_syndrome_zero && cur_iter < iter_count)
fprintf('Iteration: %d\n', cur_iter);
% horizontal step (alpha calculation)
for i = 1:M
% find indices of connected v-nodes
ones_in_row = find(H(i, :));
% find abs min value and its sign
for j = 1:length(ones_in_row)
min_value = realmax;
sign = 1;
% find min value among values with indices in
% ones_in_row except current index
for k = 1:length(ones_in_row)
if ones_in_row(k) ~= ones_in_row(j)
% value section
if (abs(beta(i, ones_in_row(k))) < min_value)
min_value = abs(beta(i, ones_in_row(k)));
end
% sign section
if beta(i, ones_in_row(k)) >= 0
sign = sign * 1;
else
sign = sign * (-1);
end
end
end
% assign min-sum value to the alpha
alpha(i, ones_in_row(j)) = min_value * sign;
end
end
% vertical step (calculate beta)
for i = 1:N
ones_in_col = find(H(:, i));
for j = 1:length(ones_in_col)
% sum with all connected alpha values except current
for k = 1:length(ones_in_col)
if ones_in_col(j) ~= ones_in_col(k)
beta(ones_in_col(k),i) = beta(ones_in_col(k), i) + alpha(ones_in_col(k), i);
end
end
end
end
% update z value
for i = 1:N
ones_in_col = find(H(:, i));
for j = 1:length(ones_in_col)
z(i) = z(i) + alpha(ones_in_col(j), i);
end
end
% check results of correction
for i = 1:length(z)
if (z(i) > 0)
v(i) = 0;
else
v(i) = 1;
end
end
disp('Z value:');
disp(z);
disp('V value:');
disp(v);
% make check for the recived vector
parity_check = mod(H * v', 2);
ones_in_parity = find(parity_check);
if (isempty(ones_in_parity))
is_syndrome_zero = true;
end
cur_iter = cur_iter + 1;
end
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.