Алгоритмы на FPGA: Алгоритм Луна
ПЛИС-культ привет, хабрунити!
Задумывались ли вы когда-нибудь над тем, что может быть общего у банковской карточки, IMEI телефона и вагона РЖД? В этой статье вы найдете ответ на этот вопрос и увидите его реализацию для ПЛИС.
Казалось бы, обычная пластиковая карта. Мы используем её ежедневно при оплате заказов на разного рода онлайн магазинах, при оплате штрафов в ГИБДД или для отправки донатов. Но задумывались ли вы над тем, как формируется сам номер вашей карты и что он фактически означает?
Честно говоря, я никогда, но до определённого момента … момента, когда алгоритм ютуба выдал мне ролик с канала VitalMath.
Что было интересного в этом пятиминутном ролике о жизненной математике? В видео был ответ на один интересный вопрос: каким образом форма ввода номера банковской карты знает, что он был введён корректно?
С одной стороны, казалось бы, ну что особенного в наш век интернета: вводишь номер, он отправляется на сервер, сравнивается с местной базой данных и выдаёт ответ. Вроде бы логично, но нет. Никакой запрос к базе данных не осуществляется, тогда каким же образом определяется корректность ввода?
А определяется он с помощью достаточно простой, в плане реализации, математики, которую придумал ещё в 1954 году Хансон Питер Лун.
Этот алгоритм проверки корректности определенной последовательности цифр с помощью контрольной цифры получил название по фамилии автора и более широко известен как Алгоритм Луна. Он не требует больших вычислительных затрат и позволяет на лету обнаружить ошибку при вводе данных. Да, алгоритмов проверки подобного рода существует несметное количество, но в этой статье мы разберем реализацию именно Алгоритма Луна на ПЛИС, который, к слову, не лишён недостатков, про которые вы можете узнать подробнее в той же википедии. Алгоритм Луна широко используется в нашей повседневной жизни и послужит нам отправной точкой к серии статей, посвященных реализации математических алгоритмов на ПЛИС.
Алгоритм Луна: краткое руководство
Для начала рассмотрим сам алгоритм.
Сразу отмечу, что существует два вида Алгоритма Луна: обычный и упрощенный, в чем между ними разница я скажу чуть позднее.
Итак предположим, что у нас есть некоторая последовательность цифр, например дата основания комьюнити FPGA-Systems: первое апреля 2017 года, для которой надо определить контрольное число по Алгоритму Луна. Что нам для этого нужно сделать?
Обычный Алгоритм Луна
смотрим сколько цифр в нашей последовательности 01042017. Последовательность содержит четное количество цифр, а именно 8
Если количество цифр чётное, то для всех цифр в четной позиции делаем умножение на два (индексация цифр начинается с 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Если на втором шаге число после умножения на 2 оказалось больше 9, то заменяем его на сумму цифр этого числа или вычитаем 9
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Дополняем до ближайшего числа в большую сторону, которое делится на 10.
В нашем случае мы получили 18, значит ближайшее кратное 10 будет 20.Вычитаем из 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
Для начала определим внешний вид и порты ввода вывода нашего модуля. Модуль будет принимать цифры последовательно и проверять последовательность мы будем на лету, это значит, что цифры нужно будет подавать последовательно. Одну за одной начиная с первой.
Входы
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 и проверять полученный результат со значениями в таблице. Но такой вариант подходил только для простых тестов.
Но на стриме во время появился Евгений и предложил следующий вариант:
Еще раз спасибо Евгению за идею! Если промежуточная сумма, которую мы храним в переменной 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
Во втором варианте реализации я решил избавиться от необходимости передавать количество цифр в последовательности и заменил этот порт на два других
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 стриме.
Ссылки
Алгоритм Луна wiki
Исходники на git
Видео про реализацию на ПЛИС
Стрим, на котором я делал Алгоритм Луна
Онлайн проверятор последовательностей
