| |
 Сравнить (через сжатие) два 512разядных(и более)сущности, Прошу совета по минимуму аппаратного рессурса |
|
|
|
|
  Mar 10 2011, 08:47
|
Знающий
Группа: Свой
Сообщений: 815
Регистрация: 7-06-06
Из: Харьков
Пользователь №: 17 847
|
Уважаемые форумчане! Обращаюсь к вашему опыту, ибо боюсь при такой разрядности съесть рессурс уже готового проекта. Время не жмёт, его достаточно. ...Пугает здоровенный мультиплексор, если прогонять по CRC32 всю последовательность(64байта) через автомат. Может нечто древовидное организовать? Может и не CRC, а сигнатуры какие породить?... Итог,- убедиться в одинаковости сигнатур приходящей извне(в последовательном коде) со сгенерированной у себя. Кто что подобное ваял? Интуитивно, чтобы не создавать проблемы основному проекту, просится что-то разнесённое, древовидное, т.к. сами сущности размазаны по ПЛИС. Я пока готовлюсь к простому автомату CRC ...в лоб. Но неуютно в перспективе! Спасибо! Рад любым идеям и заделам... 
|
|
|
|
|
|
|
|
Mar 10 2011, 09:23
|
Гуру
Группа: Модераторы
Сообщений: 4 011
Регистрация: 8-09-05
Из: спб
Пользователь №: 8 369
|
Цитата(Мур @ Mar 10 2011, 11:47)  Время не жмёт, его достаточно. ...Итог,- убедиться в одинаковости приходящей извне(в последовательном коде) со сгенерированной у себя. Так вот прямо при приеме побитно и проверять. Всего-то нужен дополнительно сдвиговый регистр (СР), для загрузки шаблона, схема сравнения на 1 бит и триггер совпадения. В СР заносите шаблон и при приеме данных его сдвигаете. И сравниваете приходящий бит с битом шаблона. Если есть несовпадение хотя бы в одном бите - сбрасываете триггер... Я так делал проверку МАС-адреса... Собственно и все. Удачи!
--------------------
www.iosifk.narod.ru
|
|
|
|
|
|
|
|
Mar 10 2011, 09:26
|
Знающий
Группа: Свой
Сообщений: 815
Регистрация: 7-06-06
Из: Харьков
Пользователь №: 17 847
|
Цитата(Oldring @ Mar 10 2011, 12:14) Зачем "через сжатие"?
Любые сигнатуры чреваты ложными совпадениями. Особенно, просто считаемые. Вот-вот!... Тут надо покруче. В общем, я плаваю в материале. Признаю! ...А есть гибрид CRC с сигнатурным сжимателем? По сути,-сигнатурный анализатор-частный случай CRC, который имеет массу вариантов. -------------- Всего хотелось минимума проблем при ещё большей разрядности в перспективе. Сжатие, как способ сэкономить рессурс. Цитата(iosifk @ Mar 10 2011, 12:23) Так вот прямо при приеме побитно и проверять. Всего-то нужен дополнительно сдвиговый регистр (СР), для загрузки шаблона, схема сравнения на 1 бит и триггер совпадения. В СР заносите шаблон и при приеме данных его сдвигаете. И сравниваете приходящий бит с битом шаблона. Если есть несовпадение хотя бы в одном бите - сбрасываете триггер...
Я так делал проверку МАС-адреса...
Собственно и все.
Удачи! Супер! Спасибо Мэтру! Шаблон-то гибкий должен быть. Коды меняются и там и здесь...
Сообщение отредактировал Мур - Mar 10 2011, 11:05
|
|
|
|
|
|
|
|
Mar 10 2011, 12:18
|
Знающий
Группа: Свой
Сообщений: 815
Регистрация: 7-06-06
Из: Харьков
Пользователь №: 17 847
|
Цитата(yes @ Mar 10 2011, 14:11) что-то я не понял
если есть 512 бит "сущность" и ее сжимаете/получаете сигнатуру/црц самым прогрессивным методом, известным человечеству. ну, например до 8 бит, то в среднем каждая 256 "сущность" будет иметь одинаковую сигнатуру
то есть нельзя посадить 11 кроликов в 10 клеток так, чтобы в каждой клетке сидело не больше 1 кролика
то есть с сигнатурами можно либо дать ответ: 100% не совпадает, а если сигнатуры равны - то равны ли сущности - достоверно не известно
и если в контексте црц/сигнатур сдвиговый регистр LFSR - то непонятно нафига это надо - сравнивайте побитно сущности.
с LFSR наверно можно уменьшить вероятность если считать несколько сигнатур, но это имеет смысл только при каких-то знаниях о структуре "сущности" - в общем случае - см. про кроликов У меня на стапеле CRC32. Говорить о неравенстве при истинном равенстве(или наоборот) можно с вероятностью 10 в минус 1х степени. Это обговаривалось выше. Кстати, пускать весь поток извне для сравнения в лоб,-тоже подвергать систему лишнему сбою. Вопрос требует изучения.
|
|
|
|
|
|
|
|
Mar 10 2011, 14:56
|
Частый гость
Группа: Свой
Сообщений: 197
Регистрация: 17-06-10
Из: Киев
Пользователь №: 57 986
|
Для CRC16 привожу анализ помехоустойчивости различных полиномов. Проводились испытания для различной длины пакетов данных (64...512 бит). Для удобства ошибки считались относительно помехоустойчивости полинома 8005h (1500 пропусков). В общем случае метод CRC16 ловит все 1х, 2х, 3х ошибки. Здесь рассматриваются только ошибки 4х, которые CRC16 не ловит одну из 30 000 вариантов (в среднем). Анализ ошибок более высокого порядка не привожу, чтобы не засорять основную идею. Интересный факт: пересечение помехоустойчивости полиномов на длине пакета 256 бит.
Сообщение отредактировал i-mir - Mar 10 2011, 14:57
Эскизы прикрепленных изображений
|
|
|
|
|
|
|
|
Mar 11 2011, 07:53
|
Знающий
Группа: Свой
Сообщений: 815
Регистрация: 7-06-06
Из: Харьков
Пользователь №: 17 847
|
Цитата(i-mir @ Mar 10 2011, 18:56) Для CRC16 привожу анализ помехоустойчивости различных полиномов.
Проводились испытания для различной длины пакетов данных (64...512 бит).
Для удобства ошибки считались относительно помехоустойчивости полинома 8005h (1500 пропусков).
В общем случае метод CRC16 ловит все 1х, 2х, 3х ошибки.
Здесь рассматриваются только ошибки 4х, которые CRC16 не ловит одну из 30 000 вариантов (в среднем).
Анализ ошибок более высокого порядка не привожу, чтобы не засорять основную идею.
Интересный факт: пересечение помехоустойчивости полиномов на длине пакета 256 бит. Огромное спасибо! Интересная инфа!.... Вот интересная реализация CRC8, говорящая о единой природе расчёта CRC и получения сигнатуры. Тут ,при определённом умении, легко реализовать любой полином. От CRC4 до CRC100 Код --
-- Description : X8+X7+X2+1
--
-------------------------------------------------------------------------------
library IEEE;
use IEEE.STD_LOGIC_1164.all;
entity signature is
port(
CLK : in STD_LOGIC;
Reset : in STD_LOGIC;
ind : in STD_LOGIC;
dat : out STD_LOGIC_VECTOR(7 downto 0)
);
end signature;
architecture signature_body of signature is
signal rg_baza : STD_LOGIC_VECTOR(7 downto 0);
signal rg_bz : STD_LOGIC_VECTOR(7 downto 0);
begin
process (CLK)
begin
if CLK'event and CLK = '1' then
if Reset = '1' then
rg_baza <= "00000000";
else
rg_baza <= rg_bz;
end if;
end if;
end process;
rg_bz(0) <= rg_baza(7)xor ind;
rg_bz(1) <= rg_baza(0);
rg_bz(2) <= rg_baza(1) xor (rg_baza(7) xor ind);
rg_bz(3) <= rg_baza(2);
rg_bz(4) <= rg_baza(3);
rg_bz(5) <= rg_baza(4);
rg_bz(6) <= rg_baza(5);
rg_bz(7) <= rg_baza(6) xor (rg_baza(7) xor ind);
dat<= rg_baza;
end signature_body; Я проверил по таблице из текста Цитата Контрольная сумма. В качестве алгоритма вычисления контрольной суммы используется CRC-8, с начальным значением 0x00 и полиномом x8+x7+x2+1. Таблица и функция для вычисления контрольной суммы, определенные в форме языка С, приведены ниже:
unsigned char crc8TableA[256] =
{
0x00, 0x85, 0x8F, 0x0A, 0x9B, 0x1E, 0x14, 0x91, 0xB3, 0x36,
0x3C, 0xB9, 0x28, 0xAD, 0xA7, 0x22, 0xE3, 0x66, 0x6C, 0xE9,
0x78, 0xFD, 0xF7, 0x72, 0x50, 0xD5, 0xDF, 0x5A, 0xCB, 0x4E,
0x44, 0xC1, 0x43, 0xC6, 0xCC, 0x49, 0xD8, 0x5D, 0x57, 0xD2,
0xF0, 0x75, 0x7F, 0xFA, 0x6B, 0xEE, 0xE4, 0x61, 0xA0, 0x25,
0x2F, 0xAA, 0x3B, 0xBE, 0xB4, 0x31, 0x13, 0x96, 0x9C, 0x19,
0x88, 0x0D, 0x07, 0x82, 0x86, 0x03, 0x09, 0x8C, 0x1D, 0x98,
0x92, 0x17, 0x35, 0xB0, 0xBA, 0x3F, 0xAE, 0x2B, 0x21, 0xA4,
0x65, 0xE0, 0xEA, 0x6F, 0xFE, 0x7B, 0x71, 0xF4, 0xD6, 0x53,
0x59, 0xDC, 0x4D, 0xC8, 0xC2, 0x47, 0xC5, 0x40, 0x4A, 0xCF,
0x5E, 0xDB, 0xD1, 0x54, 0x76, 0xF3, 0xF9, 0x7C, 0xED, 0x68,
0x62, 0xE7, 0x26, 0xA3, 0xA9, 0x2C, 0xBD, 0x38, 0x32, 0xB7,
0x95, 0x10, 0x1A, 0x9F, 0x0E, 0x8B, 0x81, 0x04, 0x89, 0x0C,
0x06, 0x83, 0x12, 0x97, 0x9D, 0x18, 0x3A, 0xBF, 0xB5, 0x30,
0xA1, 0x24, 0x2E, 0xAB, 0x6A, 0xEF, 0xE5, 0x60, 0xF1, 0x74,
0x7E, 0xFB, 0xD9, 0x5C, 0x56, 0xD3, 0x42, 0xC7, 0xCD, 0x48,
0xCA, 0x4F, 0x45, 0xC0, 0x51, 0xD4, 0xDE, 0x5B, 0x79, 0xFC,
0xF6, 0x73, 0xE2, 0x67, 0x6D, 0xE8, 0x29, 0xAC, 0xA6, 0x23,
0xB2, 0x37, 0x3D, 0xB8, 0x9A, 0x1F, 0x15, 0x90, 0x01, 0x84,
0x8E, 0x0B, 0x0F, 0x8A, 0x80, 0x05, 0x94, 0x11, 0x1B, 0x9E,
0xBC, 0x39, 0x33, 0xB6, 0x27, 0xA2, 0xA8, 0x2D, 0xEC, 0x69,
0x63, 0xE6, 0x77, 0xF2, 0xF8, 0x7D, 0x5F, 0xDA, 0xD0, 0x55,
0xC4, 0x41, 0x4B, 0xCE, 0x4C, 0xC9, 0xC3, 0x46, 0xD7, 0x52,
0x58, 0xDD, 0xFF, 0x7A, 0x70, 0xF5, 0x64, 0xE1, 0xEB, 0x6E,
0xAF, 0x2A, 0x20, 0xA5, 0x34, 0xB1, 0xBB, 0x3E, 0x1C, 0x99,
0x93, 0x16, 0x87, 0x02, 0x08, 0x8D};
|
|
|
|
|
|
|
|
Mar 11 2011, 08:05
|
Частый гость
Группа: Участник
Сообщений: 161
Регистрация: 9-09-08
Из: РФ
Пользователь №: 40 076
|
Цитата(Мур @ Mar 11 2011, 10:53) Тут, при определённом умении, легко реализовать любой полином. От CRC4 до CRC100 А оно надо, умение? CSC Tool.
|
|
|
|
|
|
|
|
Mar 11 2011, 08:39
|
Знающий
Группа: Свой
Сообщений: 815
Регистрация: 7-06-06
Из: Харьков
Пользователь №: 17 847
|
Для простоты восприятия рисуночек в приложении. Для повышения помехозащищенности при обмене с внешней средой очень симпатично применять в дополнение к CRC инверсный код(так и набирать в гугле!) Цитата(=SSN= @ Mar 11 2011, 12:05) А оно надо, умение? CSC Tool.Мне это известно. Ловушка в том, что в этом тулзе разрядность выхода не 1,- а это уход от сдвигового регистра! Это куча мультиплексоров. Тут предлагается однобитовый поток(гигантский сдвиговый регистр). Затраты минимальны. Эффект максимальный.
Сообщение отредактировал Мур - Mar 11 2011, 09:28
Прикрепленные файлы
CRC8.bmp ( 13.61 килобайт )
Кол-во скачиваний: 27
|
|
|
|
|
|
|
|
Mar 14 2011, 06:48
|
Знающий
Группа: Свой
Сообщений: 815
Регистрация: 7-06-06
Из: Харьков
Пользователь №: 17 847
|
Цитата(dvladim @ Mar 12 2011, 21:40) Нормально там все. Пишешь: crc <= newCRC(crc, data); и получается нормальный сдвиговый регистр с xor-ми в нужных местах. Не думаю... Вызов функции происходит по каждому тику клока. Так что подача данных порциями по 8 точно есть! Я это применял в побайтном темпе. Вот оттуда ваш код(с указанного сайта) мною применяемый Цитата library ieee;
use ieee.std_logic_1164.all;
package PCK_CRC8_D8 is
-- polynomial: (0 2 7 8)
-- data width: 8
-- convention: the first serial bit is D[7]
function nextCRC8_D8
(Data: std_logic_vector(7 downto 0);
crc: std_logic_vector(7 downto 0))
return std_logic_vector;
end PCK_CRC8_D8;
package body PCK_CRC8_D8 is
-- polynomial: (0 2 7 8)
-- data width: 8
-- convention: the first serial bit is D[7]
function nextCRC8_D8
(Data: std_logic_vector(7 downto 0);
crc: std_logic_vector(7 downto 0))
return std_logic_vector is
variable d: std_logic_vector(7 downto 0);
variable c: std_logic_vector(7 downto 0);
variable newcrc: std_logic_vector(7 downto 0);
begin
d := Data;
c := crc;
newcrc(0) := d(7) xor d(5) xor d(4) xor d(3) xor d(2) xor d(1) xor d(0) xor c(0) xor c(1) xor c(2) xor c(3) xor c(4) xor c(5) xor c(7);
newcrc(1) := d(6) xor d(5) xor d(4) xor d(3) xor d(2) xor d(1) xor c(1) xor c(2) xor c(3) xor c(4) xor c(5) xor c(6);
newcrc(2) := d(6) xor d(1) xor d(0) xor c(0) xor c(1) xor c(6);
newcrc(3) := d(7) xor d(2) xor d(1) xor c(1) xor c(2) xor c(7);
newcrc(4) := d(3) xor d(2) xor c(2) xor c(3);
newcrc(5) := d(4) xor d(3) xor c(3) xor c(4);
newcrc(6) := d(5) xor d(4) xor c(4) xor c(5);
newcrc(7) := d(7) xor d(6) xor d(4) xor d(3) xor d(2) xor d(1) xor d(0) xor c(0) xor c(1) xor c(2) xor c(3) xor c(4) xor c(6) xor c(7);
return newcrc;
end nextCRC8_D8;
end PCK_CRC8_D8;
|
|
|
|
|
|
3 чел. читают эту тему (гостей: 3, скрытых пользователей: 0)
Пользователей: 0
|
|
|
