Я пытаюсь придумать алгоритм для реализации этого для данного n битового двоичного числа. Я попробовал много примеров, но не смог найти какой-либо шаблон. Итак, как я буду действовать?Алгоритм в аппаратном обеспечении, чтобы узнать, делится ли число на пять
Как об этом:
Преобразование числа к основанию 4 (это тривиально, просто комбинируя пары битов). 5 в основании 4 равно 11. Значения 4, которые делятся на 11, несколько знакомы: 11, 22, 33, 110, 121, 132, 203, ...
Правило делимости на 11 - это то, что вы добавьте все нечетные цифры и все четные цифры и вычтите один из другого. Если результат делится на 11 (который помнит 5), то он делится на 11 (который помнит 5).
Например:
123456d = 1 1110 0010 0100 0000b = 132021000_4
The even digits are 1 2 2 0 0 : sum = 5d
The odd digits are 3 0 1 0 : sum = 4d
Difference is 1, which is not divisble by 5
Или еще один:
123455d = 1 1110 0010 0011 1111b = 132020333_4
The even digits are 1 2 2 3 3 : sum = 11d
The odd digits are 3 0 0 3 : sum = 6d
Difference is 5, which is a 5 or a 0
Это должно иметь достаточно эффективную реализацию HW, потому что это в основном немного Квантование, а затем N/2 сумматоров, где N- количество бит в интересующем вас номере.
Обратите внимание, что после добавления цифр и вычитания максимальное значение равно 3/4 * N, поэтому, если у вас есть 16-разрядные номера max, вы можете получить не более 12 в результате, поэтому вам нужно только проверить на 0, & plusmn; 5 и & plusmn; 10 явно. Если вы используете 32-битные номера, тогда вы можете получить не более 24, поэтому вам нужно также проверить, есть ли результат: плюс + 15 или & plusmn; 20.
Вам не нужно также проверить наличие -5 и -10? –
Да, также проверьте наличие -5 и -10 – JoshG79
Сделать окончательный конечный автомат (DFA) для реализации проверки на делимость и реализовать DFA в оборудовании.
Создание DFA для делимости на 5 легко. Вам просто нужно заметить остатки и проверить, к чему относятся 2r (mod 5) и 2r + 1 (mod 5). Есть много сайтов, которые обсуждают это. Например, this one.
Известные примеры преобразования DFA в аппаратное представление.
Я думаю, вы имеете в виду «детерминированный конечный автомат». –
Да, прошло некоторое время с тех пор, как я расширил акроним :) Спасибо – user1952500
Ну, я только что понял ... номер mod 5 = a0 * 2^0 mod 5 + a1 * 2^1 mod 5 + a2 * 2^2 mod 5 + a3 * 2^3 mod 5 + a4 * 2^4 mod 5 + .... = a0 (1) + a1 (2) + a2 (-1) + a3 (-2) + a4 (1) повторяет ...
Следовательно, разница нечетных цифр + 2 раза разность четных цифр = делится на 5
, например ... рассмотреть 110010
нечетных цифр differnce = 0-0 + 1 = 1 или 01 даже цифры разница = 1-0 + 1 = 2 или 10
Разница нечетных цифр + 2 раза разность четных цифр = 01 + 2 * (10) = 01 + 100 = 101 делится на 5.
Вклад каждого бита в разряд делится на пять - это четырехбитовый шаблон 3421. Вы можете сдвинуть любое двоичное число 4 бита за раз, добавив соответствующее значение для положительных бит.
Пример:
принять 0011 применить шаблон 0021 сумму 3
Следующие четыре бита 0010 применить шаблон 0020 сумму = 5
В любом назначении этого был бы ответом, потому что он должен быть просрочен через год:
в двоичное представление естественного делимого на пять соотношений бит 4n и 4n + 2, равно как и битов 4n + 1 и 4n + 3.
(Это полностью эквивалентно ответам JoshG79, notsogeek или james: 4≡-1 (mod 5), 3≡-2 (mod 5) (с уменьшенным размахом руки по рекурсии в аргументации и без возможности обработки
[Это] (http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA547555) может пригодиться вам. –
Пять в двоичном формате - 101. Вам может быть проще сначала подумать об алгоритме для проверки десятичного числа для делимости на десятичный 101. –
конвертирующий материал будет добавлять во времени ... – notsogeek