Алгоритмы на FPGA: Алгоритм Луна

ПЛИС-культ привет, хабрунити!

Задумывались ли вы когда-нибудь над тем, что может быть общего у банковской карточки, IMEI телефона и вагона РЖД? В этой статье вы найдете ответ на этот вопрос и увидите его реализацию для ПЛИС.

f2e57c18e0b3c6daffc0cbab192e6167.jpg

Казалось бы, обычная пластиковая карта. Мы используем её ежедневно при оплате заказов на разного рода онлайн магазинах, при оплате штрафов в ГИБДД или для отправки донатов. Но задумывались ли вы над тем, как формируется сам номер вашей карты и что он фактически означает?

Честно говоря, я никогда, но до определённого момента … момента, когда алгоритм ютуба выдал мне ролик с канала VitalMath.

Что было интересного в этом пятиминутном ролике о жизненной математике? В видео был ответ на один интересный вопрос: каким образом форма ввода номера банковской карты знает, что он был введён корректно?

С одной стороны, казалось бы, ну что особенного в наш век интернета: вводишь номер, он отправляется на сервер, сравнивается с местной базой данных и выдаёт ответ. Вроде бы логично, но нет. Никакой запрос к базе данных не осуществляется, тогда каким же образом определяется корректность ввода?

А определяется он с помощью достаточно простой, в плане реализации, математики, которую придумал ещё в 1954 году Хансон Питер Лун.

Этот алгоритм проверки корректности определенной последовательности цифр с помощью контрольной цифры получил название по фамилии автора и более широко известен как Алгоритм Луна. Он не требует больших вычислительных затрат и позволяет на лету обнаружить ошибку при вводе данных. Да, алгоритмов проверки подобного рода существует несметное количество, но в этой статье мы разберем реализацию именно Алгоритма Луна на ПЛИС, который, к слову, не лишён недостатков, про которые вы можете узнать подробнее в той же википедии. Алгоритм Луна широко используется в нашей повседневной жизни и послужит нам отправной точкой к серии статей, посвященных реализации математических алгоритмов на ПЛИС.

Алгоритм Луна: краткое руководство

Для начала рассмотрим сам алгоритм.

Сразу отмечу, что существует два вида Алгоритма Луна: обычный и упрощенный, в чем между ними разница я скажу чуть позднее.

Итак предположим, что у нас есть некоторая последовательность цифр, например дата основания комьюнити FPGA-Systems: первое апреля 2017 года, для которой надо определить контрольное число по Алгоритму Луна. Что нам для этого нужно сделать?

Обычный Алгоритм Луна

  1. смотрим сколько цифр в нашей последовательности 01042017. Последовательность содержит четное количество цифр, а именно 8

  2. Если количество цифр чётное, то для всех цифр в четной позиции делаем умножение на два (индексация цифр начинается с 1)

    1 2 3 4 5 6 7 8 --индекс
    0   1      0      4      2     0      1   7 --последовательность
         1×2         4×2         0×2       7×2 
    0 2 0 8 2 0 1 14

  3. Если на втором шаге число после умножения на 2 оказалось больше 9, то заменяем его на сумму цифр этого числа или вычитаем 9

    0 2 0 8 2 0 1 1+4
    0 2 0 8 2 0 1 5

  4. Теперь складываем все полученные числа
    0+2+0+8+2+0+1+5 = 18

  5. Дополняем до ближайшего числа в большую сторону, которое делится на 10.
    В нашем случае мы получили 18, значит ближайшее кратное 10 будет 20.

  6. Вычитаем из 20 нашу сумму 18 и получаем 2. Это и будет контрольная цифра для нашей начальной последовательности 01042017

Теперь приставляя к начальной последовательности 01042017 контрольную цифру 2 получаем последовательность, в которой есть проверка на возможную ошибку при неправильном вводе 010420172

Что же делать если в последовательности количество цифр нечётное? Делается абсолютно тоже самое, но для цифр в нечетной позиции, например:

1    2   3    4    5 --индекс
5    7   3    9    5 --последовательность
5x2  7   3x2  9    5x2
10   7   6    9    10
1+0  7   6    9    1+0
1  + 7 + 6  + 9 +  1 = 24

Ближайшее большее кратное 10 к 24 это 30
30 — 24 = 6 — контрольная цифра для 57395
Проверить можно, например, здесь.

Проверка последовательностей содержащей контрольную цифру выполняется во много также, но в расчёт пока не берется контрольная цифра

Проверка
1 2 3 4 5 6 7 8 --индекс
0   1      0      4      2     0      1   7 2 --последовательность с контрольной цифрой 2
1×2         4×2         0×2       7×2 
0 2 0 8 2 0 1 14
0 2 0 8 2 0 1 1+4
0 2 0 8 2 0 1 5
0 + 2 + 0 + 8 + 2 + 0 + 1 + 5 = 18
К полученной сумме прибавляем контрольную цифру 2
18 + 2 = 20 — если получилось число, кратное 10, то последовательность верна

Все до банального просто. Еще раз отмечу, что Алгоритм Луна имеет свои недостатки и не способен обнаружить некоторые ошибки.

Упрощенный Алгоритм Луна

В варианте упрощенного алгоритма всегда следует двигаться справа-налево, то есть с последней цифры последовательности через одну. При выполнении проверки не берется контрольная цифра, только цифры проверяемой последовательности. Контрольная цифра всегда используется только на последнем шаге для сложения с результатом промежуточной суммы.

Это позволяет избавиться от необходимости определять из скольких цифр состоит последовательность (из четного или нечетного), но с другой стороны требует передавать/принимать последовательность начиная с последней цифры. Но в целом это не является какой-либо проблемой.

Переходим к реализации

Делать мы будем проверятор последовательностей по обычному Алгоритму Луна, то есть на вход нам будет поступать последовательность с контрольной цифрой, на языке VHDL. Приведу примеры нескольких вариантов реализации.

PS: реализацию упрощенного алгоритма и реализации на Verilog/SystemVerilog оставляю вам в качестве домашнего задания.

Вариант 1

 Для начала определим внешний вид и порты ввода вывода нашего модуля. Модуль будет принимать цифры последовательно и проверять последовательность мы будем на лету, это значит, что цифры нужно будет подавать последовательно. Одну за одной начиная с первой.

4d46ab6863c8387c8496f8b71c37146b.png

Входы
iclk   - Входной порт тактовой частоты
ireset - Вход сброса
istart - Порт начала последовательности, он же послужит сигналом запуска начала вычислений
idigit[3:0]  - Входной порт передаваемой цифры. Поскольку цифры подаются последовательно, то их значение будет от 0 до 9, что эквивалентно 4-м разрядам
idigit_valid - Сигнал валидности. Позволит обрабатывать паузы при передаче последовательности
inum_of_digits[10:0] - Количество цифр в последовательности, мы сделаем относительно универсальный модуль. Количество цифр без контрольного числа – это важно!

Выходы
odone    - Порт окончания расчетов
ocorrect - Порт корректности последовательности
oerror   - Порт ошибки в последовательности
oready   - Порт готовности к приему следующей цифры или последовательности

Быстренько опишем входные и выходные порты, а также подключим необходимые стандартные библиотеки

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.std_logic_unsigned.all;

entity luhn_checker_v1 is
    port (
        iclk   : in std_logic;
        ireset : in std_logic;
        inum_of_digits: std_logic_vector(10 downto 0); --how much digits in checking number !!!whitout control digit
        istart : in std_logic; --set pulse, like write enable, for current checking sequence
                               --used as start signal
        idigit : in std_logic_vector(3 downto 0); --current digit in sequence
        idigit_valid: in std_logic; --valid signal for new digit
        
        oready  : out std_logic; --ready to receive next digit
        ocorrect: out std_logic; --checked sequence is correct ('1' - correct)
        oerror  : out std_logic; --checked sequence is incorrect ('1' - incorrect)
        odone   : out std_logic  --complete computation
    );
end luhn_checker_v1;

Чтобы сэкономить немного ресурсов мы пойдем на небольшую хитрость. Как вы помните, если число больше 9, после умножения на 2, то нужно сложить две цифры этого числа. Но мы знаем, что число будет в диапазоне 10 — 18, это от 5×2 до 9×2. Других вариантов нет, поэтому мы заранее вычислим умножение на 2, просуммируем цифры и сохраним значения в массив, то есть в память, которая за малым числом элементов скорее всего будет распределенной, то есть реализованной на LUTах.

type rom is array (0 to 9) of natural range 0 to 9;
    --Luhn algorith requires double the value of digits, if result more then 9 => add digits
    --example 
    -- 2   3   4   5   6
    -- 2x2 3x2 4x2 5x2 6x2
    -- 4   6   8   10  12
    -- 4   6   8   1+0 1+2
    -- 4   6   8   1   3  -> this result
    -- To skip arithmetic computation we place result in table,
    --0x2 = 0              
    --1x2 = 2              
    --2x2 = 4              
    --3x2 = 6              
    --4x2 = 8              
    --5x2 = 10 => 1 + 0 = 1
    --6x2 = 12 => 1 + 2 = 3
    --7x2 = 14 => 1 + 4 = 5
    --8x2 = 16 => 1 + 6 = 7
    --9x2 = 18 => 1 + 8 = 9
    constant luhn_rom: rom := (0, 2, 4, 6, 8, 1, 3, 5, 7, 9 );

 Для сохранения промежуточного результата суммирования удвоенных и обычных значений мы будем использовать переменную tmp. Я позже поясню, почему максимальное значение промежуточной суммы не может быть больше 18.

--save temporaly result of sums
signal tmp: natural range 0 to 31;

Определим переменную для хранения номера текущей цифры в последовательности

signal k: natural range 0 to 2**inum_of_digits'left - 1 := 0; --current index of checking digit

 И в конце определим конечный автомат, который и будет управлять всеми вычислениями.

--main manager 
type state_type is (s0, s1, s2, s3, s4, s5, s6);
signal state : state_type := s0;

Подготовительная часть закончена, переходим к функциональной

Нам будет достаточно всего одного синхронного процесса. По сигналу сброса переводим все компоненты в начальное состояние. Затем следует сам конечный автомат:

Состояние s0 является состоянием ожидания сигнала начала последовательности и в этом состоянии мы переводим все сигналы и порты в начальное значение. 

Состояние s1 используется для вычисления суммы с удвоенным числом 

Состояние s2 используется для простой суммы

Состояние s3 используется для проверки кратности 10 полученного результата


process(iclk) begin
    if rising_edge(iclk) then
        if ireset = '1' then
            state <= s0;
            tmp <= 0;
            k <= 0;
            oready <= '1';
            oerror <= '0';
            ocorrect <= '0';
            odone    <= '0';
        else 
           case (state) is
             when s0 => ;--idle
             when s1 => ;--x2
             when s2 => ;--sum
             when s3 => ;--mod10
             when others => state <= s0;
           end case;
        end if;
     end if;
  end process;

Так стоп!

Как проверить кратность 10 в двоичной системе? Я никогда не слышал о таком алгоритме, находил алгоритмы кратности другим значениям, но не 10. Мое первое очень зашкварное решение на стриме было просто создать массив из чисел, кратных 10 и проверять полученный результат со значениями в таблице. Но такой вариант подходил только для простых тестов.

Но на стриме во время появился Евгений и предложил следующий вариант:

ea70c9008706f5a2d8d5f156dd2c0c23.png

Еще раз спасибо Евгению за идею! Если промежуточная сумма, которую мы храним в переменной tmp будет больше 10, то мы сразу же будем вычитать 10, в противном случае просто складывать с простой цифрой или со значением из таблицы (это действие описано в s1 и s2). По этой причине диапазон значений переменной tmp задан как 0 to 31, ведь ее значение не может быть больше 18 (9+9).

После короткого лирического отступления продолжаем наполнять конечный автомат смыслом.

Одновременно с сигналом старт, следует передать количество цифр в проверяемой последовательности, за исключением контрольного числа.

 Здесь же определяем четность количества цифр в последовательности. Как мы знаем в двоичном коде все четные числа имеют в младшем разряде 0, а не четные 1.

0 0000    1 0001
2 0010    3 0011
4 0100    5 0101
6 0110    7 0111
8 1000    9 1001
.         .
.         .
.         .

Здесь же в зависимости от четности не четности проверяем есть ли на входе одновременно с сигналом istart данные и выполняем присвоение промежуточной сумме значение из таблицы если последовательность из нечетного количества цифр и просто цифру если последовательность из четного количества цифр. И не забываем про увеличение переменной k, отвечающей за общее количество принятых цифр последовательности.

when s0 =>
                        
    oready <= '1';
    oerror <= '0';
    ocorrect <= '0';
    k <= 0;
    tmp <= 0;
    odone    <= '0';
    
    if istart = '1' then
      
        --check even or odd digits in sequence !!!whitout control digit
        if inum_of_digits(0) = '0' then -- even
            if idigit_valid = '1' then
                tmp <= to_integer(unsigned(idigit));
                k <= k + 1;
                state <= s1;
            else
                state <= s2;
            end if;      
        else
            if idigit_valid = '1' then
                tmp <= luhn_rom(to_integer(unsigned(idigit)));
                k <= k + 1;
                state <= s2;
            else
                state <= s1;
            end if;
        end if;
    end if;

В состоянии s1 ждем появления сигнала валидности данных и складываем предыдущий результат суммы с удвоенным из таблицы.

Сразу проверяем является число последним в последовательности, сравнивая переменную к со значением длины последовательности. Если последовательность не окончена, то, переходим в следующее состояние s2, противном случае переходим в s3 и смотрим на кратность.

when s1 => 
    if idigit_valid = '1' then
        if tmp > 10 then
            tmp <= tmp + luhn_rom(to_integer(unsigned(idigit))) - 10;
        else
            tmp <= tmp + luhn_rom(to_integer(unsigned(idigit)));
        end if;
        
        k <= k + 1;
        
        if k = to_integer(unsigned(inum_of_digits)) then
            oready <= '0';                                    
            state <= s3;
        else
            state <= s2;                                
        end if;
    end if;

В состоянии s2 мы просто складываем цифру с предыдущим результатом и опять проверяем является ли число последним.

when s2 => --add digit
    if idigit_valid = '1' then
        k <= k + 1;
        
        if tmp > 10 then
            tmp <= tmp + to_integer(unsigned(idigit)) - 10;
        else
            tmp <= tmp + to_integer(unsigned(idigit));
        end if;
            
        if k = to_integer(unsigned(inum_of_digits)) then
            oready <= '0';
            state <= s3;
        else
            state <= s1;                                
        end if;       
    end if;

В состоянии s3 ждем проверяем проверку на кратность 10 полученной суммы. Благодаря тому, что мы вычитали 10 каждый раз как только переменная tmp была больше 10, нам нужно сравнить полученный результат только с 0 и 10.

when s3 =>
    oready <= '0';
    odone <= '1';
     if tmp = 0 or tmp = 10 then
        ocorrect <= '1';
     else
        oerror <= '1';
     end if;
     state <= s0;

Полный код в первой реализации будет следующим


library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.std_logic_unsigned.all;

entity luhn_checker_v1 is
    port (
        iclk : in std_logic;
        ireset : in std_logic;
        inum_of_digits: std_logic_vector(10 downto 0); --how much digits in checking number !!!whitout control digit
        istart : in std_logic; --set pulse, like write enable, for current checking sequence
                                           --used as start signal
        idigit: in std_logic_vector(3 downto 0); --current digit in sequence
        idigit_valid: in std_logic; --valid signal for new digit
        
        oready  : out std_logic; --ready to receive next digit
        ocorrect: out std_logic; --checked sequence is correct ('1' - correct)
        oerror  : out std_logic; --checked sequence is incorrect ('1' - incorrect)
        odone   : out std_logic  --complete computation
    );
end luhn_checker_v1;

architecture rtl of luhn_checker_v1 is
    
    type rom is array (0 to 9) of natural range 0 to 9;
    --Luhn algorith requires double the value of digits, if result more then 9 => add digits
    --example 
    -- 2   3   4   5   6
    -- 2x2 3x2 4x2 5x2 6x2
    -- 4   6   8   10  12
    -- 4   6   8   1+0 1+2
    -- 4   6   8   1   3  -> this result
    -- To skip arithmetic computation we place result in table,
    --0x2 = 0              
    --1x2 = 2              
    --2x2 = 4              
    --3x2 = 6              
    --4x2 = 8              
    --5x2 = 10 => 1 + 0 = 1
    --6x2 = 12 => 1 + 2 = 3
    --7x2 = 14 => 1 + 4 = 5
    --8x2 = 16 => 1 + 6 = 7
    --9x2 = 18 => 1 + 8 = 9
    constant luhn_rom: rom := (0, 2, 4, 6, 8, 1, 3, 5, 7, 9 );
    
    --save temporaly result of sums
    signal tmp: natural range 0 to 31;--need to set correct tmp width to exclude overflow
    
    --main manager 
    type state_type is (s0, s1, s2, s3, s4, s5, s6);
    signal state : state_type := s0;
    
    signal k: natural range 0 to 2**inum_of_digits'left - 1 := 0; --current index of checking digit
    
begin
    
    --
    --Important notice
    --Instead of finding mod10 of result after computation
    --we will substract 10 every time when tmp is more then 10
    --Thanks Evgeny Sidelnikov for this genious solution!
    --
    
    process(iclk) begin
        if rising_edge(iclk) then
            if ireset = '1' then
                state <= s0;
                tmp <= 0;
                k <= 0;
                oready <= '1';
                oerror <= '0';
                ocorrect <= '0';
                odone    <= '0';
            else 
               case (state) is
                    when s0 =>
                        
                        oready <= '1';
                        oerror <= '0';
                        ocorrect <= '0';
                        k <= 0;
                        tmp <= 0;
                        odone    <= '0';
                        
                        if istart = '1' then
                        
                            
                        
                            --check even or odd digits in sequence !!!whitout control digit
                            if inum_of_digits(0) = '0' then -- even
                                if idigit_valid = '1' then
                                    tmp <= to_integer(unsigned(idigit));
                                    k <= k + 1;
                                    state <= s1;
                                else
                                    state <= s2;
                                end if;
                                
                                
                            else
                                if idigit_valid = '1' then
                                    tmp <= luhn_rom(to_integer(unsigned(idigit)));
                                    k <= k + 1;
                                    state <= s2;
                                else
                                    state <= s1;
                                end if;
                                
                            end if;
                        end if;
                        
                        when s1 => 
                            if idigit_valid = '1' then
                                if tmp > 10 then
                                    tmp <= tmp + luhn_rom(to_integer(unsigned(idigit))) - 10;
                                else
                                    tmp <= tmp + luhn_rom(to_integer(unsigned(idigit)));
                                end if;
                                
                                k <= k + 1;
                                
                                if k = to_integer(unsigned(inum_of_digits)) then
									oready <= '0';                                    
									state <= s3;
                                else
                                    state <= s2;                                
                                end if;
                                
                                
                            end if;
                            
                        when s2 => --skip digit
                            if idigit_valid = '1' then
                                k <= k + 1;
                                
                                if tmp > 10 then
                                    tmp <= tmp + to_integer(unsigned(idigit)) - 10;
                                else
                                    tmp <= tmp + to_integer(unsigned(idigit));
                                end if;
                                
                                
                                if k = to_integer(unsigned(inum_of_digits)) then
                                    oready <= '0';
                                    state <= s3;
                                else
                                    state <= s1;                                
                                end if;
                                
                                
                            end if;
                            
                        when s3 =>
                        oready <= '0';
                        odone <= '1';
                         if tmp = 0 or tmp = 10 then
                            ocorrect <= '1';
                         else
                            oerror <= '1';
                         end if;
                         state <= s0;
                        
                    when others => state <= s0;
               end case;
            end if;
        end if;
    end process;

end rtl;

Тестбенч

Остаётся только сделать небольшой тестбенч для проверки. Я объявил неограниченный массив из натуральных чисел, в которые заносил последовательности для проверки

type sequence_type is array (natural range <>) of natural range 0 to 9;
    constant s0 : sequence_type := (0,1,2,3,4,5,6);--incorrect
    constant s1 : sequence_type := (4,5,6,1,2,6,1,2,1,2,3,4,5,4,6,7);
    constant s2 : sequence_type := (3,0,1,1,8,9,7);
    constant s3 : sequence_type := (4,6,2,1,4,6,2,6,2,6,7,2,6,7,1,6,7,6,4,6,7,4,6,1,7,6,5,2,7,6,1,6,7,2,6,4,2,1,6,7);
    constant s4 : sequence_type := (4,6,2,1,4,6,2,6,2,6,7,2,6,7,1,6,7,6,4,6,7,4,6,1,7,6,5,2,7,6,1,6,7,2,6,4,2,1,6,7,3);
    constant s5 : sequence_type := (7,4,1,2,3,3,1);--correct
    

А саму подачу воздействия на тестируемый модуль решил сделать через процедуру. Такое решение мне показалось более менее универсальным. Я сделал две процедуры: одна для проверки одновременно пришедших с сигналом istart данными и для случая, когда данные приходят после сигнала старт через несколько тактов.

Hidden text

procedure execute  (
     s : in sequence_type;
     signal start: out std_logic;
     signal num_of_digits: out std_logic_vector(10 downto 0);
     signal digit: out std_logic_vector(3 downto 0);
     signal digit_valid: out std_logic
 ) is
begin
    
    wait for 10*clk_period;
    start <= '1';
    num_of_digits <= std_logic_vector(to_unsigned(s'length-1, 11));
    --wait for    clk_period; 
    
    for i in s'range loop
        
        digit <= std_logic_vector(to_unsigned(s(i),4));
        digit_valid <= '1';
        wait for clk_period;
        start <= '0';
    end loop;
    
    wait for clk_period;
    digit_valid <= '0';
    digit <= std_logic_vector(to_unsigned(0,4));
end procedure;

Hidden text

procedure execute_delayed_data  (
     s : in sequence_type;
     signal start: out std_logic;
     signal num_of_digits: out std_logic_vector(10 downto 0);
     signal digit: out std_logic_vector(3 downto 0);
     signal digit_valid: out std_logic
 ) is
begin
    
    wait for 10*clk_period;
    start <= '1';
    num_of_digits <= std_logic_vector(to_unsigned(s'length-1, 11)); 
    
    wait for clk_period;
    start <= '0';
    
    wait for 2*clk_period;
       
    for i in s'range loop
        wait for clk_period;
        digit <= std_logic_vector(to_unsigned(s(i),4));
        digit_valid <= '1';
        
    end loop;
    
    wait for clk_period;
    digit_valid <= '0';
    digit <= std_logic_vector(to_unsigned(0,4));
end procedure;

Эти процедуры вызываются в теле процесса и задают входные воздействия на тестовый модуль

process
    begin
        wait for 10*clk_period;
        ireset <= '1';
        wait for 3*clk_period;
        ireset <= '0';
        
        execute(s0, istart, inum_of_digits, idigit, idigit_valid);
        execute_delayed_data(s0, istart, inum_of_digits, idigit, idigit_valid);
        
        execute(s1, istart, inum_of_digits, idigit, idigit_valid);
        execute_delayed_data(s1, istart, inum_of_digits, idigit, idigit_valid);

        execute(s5, istart, inum_of_digits, idigit, idigit_valid);
        execute_delayed_data(s5, istart, inum_of_digits, idigit, idigit_valid);
        wait;
    end process;

Полный код тестбенча для модуля первой версии

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.std_logic_unsigned.all;

library work;
use work.all;

entity tb_luhn_checker_v1 is
end tb_luhn_checker_v1;

architecture tb of tb_luhn_checker_v1 is

    signal iclk : std_logic := '1';
    signal ireset : std_logic := '0';
    signal inum_of_digits: std_logic_vector(10 downto 0);
    signal istart : std_logic := '0';
    signal idigit : std_logic_vector(3 downto 0) := (others => '0');
    signal idigit_valid : std_logic := '0';
    signal oready : std_logic;
    signal ocorrect: std_logic;
    signal oerror : std_logic;
    
    constant clk_period : time := 10ns;
    
    type sequence_type is array (natural range <>) of natural range 0 to 9;
    constant s0 : sequence_type := (0,1,2,3,4,5,6);--incorrect
    constant s1 : sequence_type := (4,5,6,1,2,6,1,2,1,2,3,4,5,4,6,7);
    constant s2 : sequence_type := (3,0,1,1,8,9,7);
    constant s3 : sequence_type := (4,6,2,1,4,6,2,6,2,6,7,2,6,7,1,6,7,6,4,6,7,4,6,1,7,6,5,2,7,6,1,6,7,2,6,4,2,1,6,7);
    constant s4 : sequence_type := (4,6,2,1,4,6,2,6,2,6,7,2,6,7,1,6,7,6,4,6,7,4,6,1,7,6,5,2,7,6,1,6,7,2,6,4,2,1,6,7,3);
    constant s5 : sequence_type := (7,4,1,2,3,3,1);--correct
    
    
    procedure execute  (
         s : in sequence_type;
         signal start: out std_logic;
         signal num_of_digits: out std_logic_vector(10 downto 0);
         signal digit: out std_logic_vector(3 downto 0);
         signal digit_valid: out std_logic
     ) is
    begin
        
        wait for 10*clk_period;
        start <= '1';
        num_of_digits <= std_logic_vector(to_unsigned(s'length-1, 11));
        --wait for    clk_period; 
        
        for i in s'range loop
            
            digit <= std_logic_vector(to_unsigned(s(i),4));
            digit_valid <= '1';
            wait for clk_period;
            start <= '0';
        end loop;
        
        wait for clk_period;
        digit_valid <= '0';
        digit <= std_logic_vector(to_unsigned(0,4));
        
        
    end procedure;
    
    procedure execute_delayed_data  (
         s : in sequence_type;
         signal start: out std_logic;
         signal num_of_digits: out std_logic_vector(10 downto 0);
         signal digit: out std_logic_vector(3 downto 0);
         signal digit_valid: out std_logic
     ) is
    begin
        
        wait for 10*clk_period;
        start <= '1';
        num_of_digits <= std_logic_vector(to_unsigned(s'length-1, 11)); 
        
        wait for clk_period;
        start <= '0';
        
        wait for 2*clk_period;
           
        for i in s'range loop
            wait for clk_period;
            digit <= std_logic_vector(to_unsigned(s(i),4));
            digit_valid <= '1';
            
        end loop;
        
        wait for clk_period;
        digit_valid <= '0';
        digit <= std_logic_vector(to_unsigned(0,4));
        
        
    end procedure;
    
begin
    
    --https://www.dcode.fr/luhn-algorithm
    --test sequence 301189 control digit 7
    --will check 3011897  
    
    iclk <= not iclk after clk_period/2;
    
    
    
    process
    begin
        wait for 10*clk_period;
        ireset <= '1';
        wait for 3*clk_period;
        ireset <= '0';
        
--        execute(s0, istart, inum_of_digits, idigit, idigit_valid);
--        execute(s1, istart, inum_of_digits, idigit, idigit_valid);
--        execute(s2, istart, inum_of_digits, idigit, idigit_valid);
--        execute(s3, istart, inum_of_digits, idigit, idigit_valid);
--        execute(s4, istart, inum_of_digits, idigit, idigit_valid);
        
        execute(s0, istart, inum_of_digits, idigit, idigit_valid);
        execute_delayed_data(s0, istart, inum_of_digits, idigit, idigit_valid);
        
        execute(s1, istart, inum_of_digits, idigit, idigit_valid);
        execute_delayed_data(s1, istart, inum_of_digits, idigit, idigit_valid);

        execute(s5, istart, inum_of_digits, idigit, idigit_valid);
        execute_delayed_data(s5, istart, inum_of_digits, idigit, idigit_valid);
        wait;
    end process;
    
    
    
    dut: entity work.luhn_checker_v1(rtl)
    port map (
        iclk           => iclk          ,
        ireset         => ireset        ,
        inum_of_digits => inum_of_digits,
        istart         => istart        ,
        idigit         => idigit        ,
        idigit_valid   => idigit_valid  ,
        oready         => oready        ,
        ocorrect       => ocorrect      ,
        oerror         => oerror      
    ); 

end architecture tb;

Исходники также доступны на git Проверку написанного на временных диаграммах оставляю на ваше усмотрение.

Вариант 2

Во втором варианте реализации я решил избавиться от необходимости передавать количество цифр в последовательности и заменил этот порт на два других

66ef4a5cf889b5ff387d3c9352fbc5d5.png

iodd_even - чётное или нечётное количество цифр в последовательности
idone - окончание последовательности, в '1' во время передачи последней цифры

Сам код претерпел лишь небольшие косметические изменения, но его функциональность осталось прежней

Hidden text


library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.std_logic_unsigned.all;

entity luhn_checker_v2 is
    port (
        iclk : in std_logic;
        ireset : in std_logic;
        istart : in std_logic; --set pulse, like write enable, for current checking sequence
                                           --used as start signal
        iodd_even: in std_logic; --is it even or odd number of digits in sequence, exclude control number
        idigit: in std_logic_vector(3 downto 0); --current digit in sequence
        idigit_valid: in std_logic; --valid signal for new digit
        idone: in std_logic; --done with number, rise up when all numbers include control uploaded
        
        oready  : out std_logic; --ready to receive next digit
        ocorrect: out std_logic; --checked number is correct ('1' - correct)
        oerror  : out std_logic; --checked number is incorrect ('1' - incorrect)
        odone   : out std_logic  --complete computation
    );
end luhn_checker_v2;

architecture rtl of luhn_checker_v2 is
    
    type rom is array (0 to 9) of natural range 0 to 9;
    --Luhn algorith requires double the value of digits, if result more then 9 => add digits
    --example 
    -- 2   3   4   5   6
    
    -- 2x2 3x2 4x2 5x2 6x2
    -- 4   6   8   10  12
    -- 4   6   8   1+0 1+2
    -- 4   6   8   1   3  -> this result
    -- To skip arithmetic computation we place result in table,
    --0x2 = 0              
    --1x2 = 2              
    --2x2 = 4              
    --3x2 = 6              
    --4x2 = 8              
    --5x2 = 10 => 1 + 0 = 1
    --6x2 = 12 => 1 + 2 = 3
    --7x2 = 14 => 1 + 4 = 5
    --8x2 = 16 => 1 + 6 = 7
    --9x2 = 18 => 1 + 8 = 9
    constant luhn_rom: rom := (0, 2, 4, 6, 8, 1, 3, 5, 7, 9 );
    
    --save temporaly result of sums
    --
    --Important notice
    --Instead of finding mod10 of result after computation
    --we will substract 10 every time when tmp is more then 10
    --Thanks Evgeny Sidelnikov for this genious solution!
    --
    signal tmp: natural range 0 to 20;
    
    --main manager 
    type state_type is (s0, s1, s2, s3, s4, s5, s6);
    signal state : state_type := s0;
    
begin
    
    
    
    process(iclk) begin
        if rising_edge(iclk) then
            if ireset = '1' then
                state <= s0;
                tmp <= 0;
                oready <= '1';
                oerror <= '0';
                ocorrect <= '0';
                odone    <= '0';
            else 
               case (state) is
                    when s0 =>
                        
                        oready <= '1';
                        oerror <= '0';
                        ocorrect <= '0';
                        tmp <= 0;
                        odone    <= '0';
                        
                        if istart = '1' then
                        
                            --check even or odd digits in sequence !!!whitout control digit
                            if iodd_even = '0' then -- even
                                if idigit_valid = '1' then
                                    tmp <= to_integer(unsigned(idigit));
                                    state <= s1;
                                else
                                    state <= s2;
                                end if;
                                
                            else
                                if idigit_valid = '1' then
                                    tmp <= luhn_rom(to_integer(unsigned(idigit)));
                                    state <= s2;
                                else
                                    state <= s1;
                                end if;
                            end if;
                        end if;
                        
                        when s1 => 
                            if idigit_valid = '1' then
                                if tmp > 10 then
                                    tmp <= tmp + luhn_rom(to_integer(unsigned(idigit))) - 10;
                                else
                                    tmp <= tmp + luhn_rom(to_integer(unsigned(idigit)));
                                end if;
                                
                                state <= s2;
                             end if;
                             
                             if idone = '1' then
                               oready <= '0';
                               state <= s3;
                             end if;
                            
                        when s2 => --skip digit
                            if idigit_valid = '1' then
                               
                                if tmp > 10 then
                                    tmp <= tmp + to_integer(unsigned(idigit)) - 10;
                                else
                                    tmp <= tmp + to_integer(unsigned(idigit));
                                end if;
                                state <= s1;
                            end if;
                            
                            if idone = '1' then
                               oready <= '0';
                               state <= s3;
                            end if;
                            
                        when s3 =>
                        oready <= '0';
                        odone <= '1';
                         if tmp = 0 or tmp = 10 then
                            ocorrect <= '1';
                         else
                            oerror <= '1';
                         end if;
                         state <= s0;
                        
                    when others => state <= s0;
               end case;
            end if;
        end if;
    end process;

end rtl;

Также соответствующие изменения я внес в файл тестбенча

Hidden text

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.std_logic_unsigned.all;

library work;
use work.all;

entity tb_luhn_checker_v2 is
end tb_luhn_checker_v2;

architecture tb of tb_luhn_checker_v2 is

    signal iclk : std_logic := '1';
    signal ireset : std_logic := '0';
    signal istart : std_logic := '0';
    signal iodd_even:  std_logic := '0';
    signal idigit : std_logic_vector(3 downto 0) := (others => '0');
    signal idigit_valid : std_logic := '0';
    signal idone: std_logic := '0';
    signal oready : std_logic;
    signal ocorrect: std_logic;
    signal oerror : std_logic;
    
    constant clk_period : time := 10ns;
    
    type sequence_type is array (natural range <>) of natural range 0 to 9;
    constant s0 : sequence_type := (0,1,2,3,4,5,6);--incorrect
    constant s1 : sequence_type := (4,5,6,1,2,6,1,2,1,2,3,4,5,4,6,7);--correct
    constant s2 : sequence_type := (3,0,1,1,8,9,7);--correct
    constant s3 : sequence_type := (4,6,2,1,4,6,2,6,2,6,7,2,6,7,1,6,7,6,4,6,7,4,6,1,7,6,5,2,7,6,1,6,7,2,6,4,2,1,6,7); -- incorrect
    constant s4 : sequence_type := (4,6,2,1,4,6,2,6,2,6,7,2,6,7,1,6,7,6,4,6,7,4,6,1,7,6,5,2,7,6,1,6,7,2,6,4,2,1,6,7,3); -- correct
    constant s5 : sequence_type := (7,4,1,2,3,3,1);--correct
    
    
    procedure execute  (
         s : in sequence_type;
         signal start: out std_logic;
         signal odd_even: out std_logic;
         signal digit: out std_logic_vector(3 downto 0);
         signal digit_valid: out std_logic;
         signal done: out std_logic
     ) is
    begin
        
        wait for 10*clk_period; 
        
        start <= '1';
        if ( (s'length - 1) mod 2 = 0) then
            odd_even <= '0';
        else
            odd_even <= '1';
        end if;
        
        for i in s'range loop
            digit <= std_logic_vector(to_unsigned(s(i),4));
            digit_valid <= '1';
            wait for clk_period; 
            start <= '0';
            odd_even <= '0';
        end loop;
        
        digit_valid <= '0';
        done <= '1';
        digit <= std_logic_vector(to_unsigned(0,4));
        
        wait for clk_period;
        done <= '0';
        
    end procedure;
  
  
      
    procedure execute_data_delayed  (
         s : in sequence_type;
         signal start: out std_logic;
         signal odd_even: out std_logic;
         signal digit: out std_logic_vector(3 downto 0);
         signal digit_valid: out std_logic;
         signal done: out std_logic
     ) is
    begin
        
        wait for 10*clk_period; 
        
        start <= '1';
        if ( (s'length - 1) mod 2 = 0) then
            odd_even <= '0';
        else
            odd_even <= '1';
        end if;
        
        wait for clk_period; 
        start <= '0';
        odd_even <= '0';
        
        wait for 2*clk_period;
        
        for i in s'range loop
            wait for clk_period;
            digit <= std_logic_vector(to_unsigned(s(i),4));
            digit_valid <= '1';
        end loop;
        
        wait for clk_period;
        digit_valid <= '0';
        done <= '1';
        digit <= std_logic_vector(to_unsigned(0,4));
        
        wait for clk_period;
        done <= '0';
        
    end procedure;
    
begin
    
    --https://www.dcode.fr/luhn-algorithm
    --test sequence 301189 control digit 7
    --will check 3011897  
    
    iclk <= not iclk after clk_period/2;
    
    
    
    process
    begin
        wait for 10*clk_period;
        ireset <= '1';
        wait for 3*clk_period;
        ireset <= '0';
        
        execute(s0, istart, iodd_even, idigit, idigit_valid, idone);
        execute_data_delayed(s0, istart, iodd_even, idigit, idigit_valid, idone);
        
        execute(s1, istart, iodd_even, idigit, idigit_valid, idone);
        execute_data_delayed(s1, istart, iodd_even, idigit, idigit_valid, idone);
        
        execute(s5, istart, iodd_even, idigit, idigit_valid, idone);
        execute_data_delayed(s5, istart, iodd_even, idigit, idigit_valid, idone);
        
        
        wait;
    end process;
    
    
    
    dut: entity work.luhn_checker_v2(rtl)
    port map (
        iclk           => iclk          ,
        ireset         => ireset        ,
        iodd_even =>   iodd_even,
        istart         => istart        ,
        idigit         => idigit        ,
        idigit_valid   => idigit_valid  ,
        idone          => idone,
        oready         => oready        ,
        ocorrect       => ocorrect      ,
        oerror         => oerror      
    ); 

end architecture tb;

Исходники также доступны на git Проверку написанного на временных диаграммах оставляю на ваше усмотрение.

И в конце

Я привел пару реализаций Алгоритма Луна на VHDL, которые, разумеется можно и нужно улучшить как стороны поведения самого модуля так и со стороны тестбенча.

За рамками статьи остались реализация упрощенного Алгоритма Луна, реализация на Verilog/SV и многое другое. Но этот алгоритм крайне прост и понятен, поэтому вполне годятся в качестве практики начинающим плисоводам.

На очереди, алгоритм Верхоффа, реализацию которого мы уже запилили на субботнем FPGA стриме.

Ссылки

  1. Алгоритм Луна wiki

  2. Исходники на git

  3. Видео про реализацию на ПЛИС

  4. Стрим, на котором я делал Алгоритм Луна

  5. Онлайн проверятор последовательностей

© Habrahabr.ru