Алгоритм Берлекэмпа-Месси

НАЦИОНАЛЬНЫЙ исследовательский университет 
информационных технологий, механики и оптики

 

 

 

 

 

 

 

отчет 
по лабораторной работе № 3 
« Алгоритм Берлекэмпа-Месси »

 

 

 

 

 

 

 

 

 

Работу выполнил: 

 

 

 

 

– Санкт-Петербург 2011 –

Описание алгоритма нахождения генератора ПСП

Алгоритм Берлекэмпа-Месси предназначен для нахождения коэффициентов обратной связи генератора псевдослучайной  последовательности и основывается на итеративном алгоритме:

1. Берем очередной элемент последовательности
2. Для текущего шага вычисляем невязку по формуле
3. Если невязка равна нулю, переходим к шагу 1
4. Записываем текущий регистр во временную переменную
5. Складываем полиномы c и b 
   
6. Меняем содержимое полиномов c и b местами.
7. Если это не последний элемент – переходим к шагу 1

Код программы в среде MatLab

function lab3

 

z = [0 1 0 1 1 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1];

c = [1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];

b = [1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];

m = -1;

 

for n = 0:1:(length(z) - 1)

    d = 0;

    for i = 0:1:(n - 1)

        d = d + z(n - i + 1) * c(i + 1);

    end

    d = mod(d, 2);

    if (d ~= 0)

        t = c;

        for i = 0:1:(length(z) + m - n - 1)

            c(n - m + i + 1) = xor(c(n - m + i + 1), b(i + 1));

        end

        m = n;

        b = t;

    end

end

 

clc;

for i = 1:1:length(c)

    fprintf('%d ', c(i));

end

 

fprintf('\n\n1');

for i = 2:1:length(c)

    if (c(i) == 1)

        fprintf(' + x ^ %d', i-1)

        l = i - 1;

    end

end

fprintf(' = 0\n\nl = %d\n\n', l);

end

Найденный полином

1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 + x ^ 1 + x ^ 6 = 0

L = 6

Выводы

В ходе выполнения работы мы изучили  алгоритм Берлекэмпа-Месси и нашли  коэффициенты обратной связи для  генератора ПСП с заданной выходной последовательностью.