реклама на сайте
подробности

 
 
3 страниц V   1 2 3 >  
Reply to this topicStart new topic
> Сравнить (через сжатие) два 512разядных(и более)сущности, Прошу совета по минимуму аппаратного рессурса
Мур
сообщение Mar 10 2011, 08:47
Сообщение #1


Знающий
****

Группа: Свой
Сообщений: 815
Регистрация: 7-06-06
Из: Харьков
Пользователь №: 17 847



Уважаемые форумчане!
Обращаюсь к вашему опыту, ибо боюсь при такой разрядности съесть рессурс уже готового проекта.
Время не жмёт, его достаточно. ...Пугает здоровенный мультиплексор, если прогонять по CRC32 всю последовательность(64байта) через автомат.
Может нечто древовидное организовать? Может и не CRC, а сигнатуры какие породить?...
Итог,- убедиться в одинаковости сигнатур приходящей извне(в последовательном коде) со сгенерированной у себя.
Кто что подобное ваял?
Интуитивно, чтобы не создавать проблемы основному проекту, просится что-то разнесённое, древовидное, т.к. сами сущности размазаны по ПЛИС.
Я пока готовлюсь к простому автомату CRC ...в лоб. Но неуютно в перспективе!
Спасибо! Рад любым идеям и заделам... tort.gif
Go to the top of the page
 
+Quote Post
des00
сообщение Mar 10 2011, 09:11
Сообщение #2


Вечный ламер
******

Группа: Модераторы
Сообщений: 7 248
Регистрация: 18-03-05
Из: Томск
Пользователь №: 3 453



а чем плох сдвиговый регистр ? или на памяти


--------------------
Go to the top of the page
 
+Quote Post
Oldring
сообщение Mar 10 2011, 09:14
Сообщение #3


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Зачем "через сжатие"?

Любые сигнатуры чреваты ложными совпадениями. Особенно, просто считаемые.


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Мур
сообщение Mar 10 2011, 09:20
Сообщение #4


Знающий
****

Группа: Свой
Сообщений: 815
Регистрация: 7-06-06
Из: Харьков
Пользователь №: 17 847



Цитата(des00 @ Mar 10 2011, 12:11) *
а чем плох сдвиговый регистр ? или на памяти


Сдвиговый регистр как раз подходит к сигнатурному анализатору! Согласен!... Я в этом случае не имею информации о неоднозначности результата такой операции сжатия. Для CRC такая оценка есть. Для пробы можно. Кстати, сигнатуру можно получить, помнится, и из двумерного массива.

Так в саму память заброс информации потребует тот-же рессурс. Да, дальше легче пойдётЁ...
Go to the top of the page
 
+Quote Post
iosifk
сообщение Mar 10 2011, 09:23
Сообщение #5


Гуру
******

Группа: Модераторы
Сообщений: 4 011
Регистрация: 8-09-05
Из: спб
Пользователь №: 8 369



Цитата(Мур @ Mar 10 2011, 11:47) *
Время не жмёт, его достаточно. ...Итог,- убедиться в одинаковости приходящей извне(в последовательном коде) со сгенерированной у себя.

Так вот прямо при приеме побитно и проверять. Всего-то нужен дополнительно сдвиговый регистр (СР), для загрузки шаблона, схема сравнения на 1 бит и триггер совпадения. В СР заносите шаблон и при приеме данных его сдвигаете. И сравниваете приходящий бит с битом шаблона. Если есть несовпадение хотя бы в одном бите - сбрасываете триггер...
Я так делал проверку МАС-адреса...
Собственно и все.
Удачи!


--------------------
www.iosifk.narod.ru
Go to the top of the page
 
+Quote Post
Мур
сообщение Mar 10 2011, 09:26
Сообщение #6


Знающий
****

Группа: Свой
Сообщений: 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
Go to the top of the page
 
+Quote Post
yes
сообщение Mar 10 2011, 11:11
Сообщение #7


Гуру
******

Группа: Свой
Сообщений: 2 198
Регистрация: 23-12-04
Пользователь №: 1 640



что-то я не понял
если есть 512 бит "сущность" и ее сжимаете/получаете сигнатуру/црц самым прогрессивным методом, известным человечеству. ну, например до 8 бит, то в среднем каждая 256 "сущность" будет иметь одинаковую сигнатуру

--------

то есть нельзя посадить 11 кроликов в 10 клеток так, чтобы в каждой клетке сидело не больше 1 кролика

--------

то есть с сигнатурами можно либо дать ответ: 100% не совпадает, а если сигнатуры равны - то равны ли сущности - достоверно не известно

и если в контексте црц/сигнатур сдвиговый регистр LFSR - то непонятно нафига это надо - сравнивайте побитно сущности.

---------

с LFSR наверно можно уменьшить вероятность если считать несколько сигнатур, но это имеет смысл только при каких-то знаниях о структуре "сущности" - в общем случае - см. про кроликов
Go to the top of the page
 
+Quote Post
Oldring
сообщение Mar 10 2011, 11:27
Сообщение #8


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(yes @ Mar 10 2011, 14:11) *
с LFSR наверно можно уменьшить вероятность если считать несколько сигнатур, но это имеет смысл только при каких-то знаниях о структуре "сущности" - в общем случае - см. про кроликов


Угу. Достаточно двух клеток, чтобы избежать размножения кроликов. Но нужно в кроликах разбираться, да и ошибиться проще.


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Мур
сообщение Mar 10 2011, 12:18
Сообщение #9


Знающий
****

Группа: Свой
Сообщений: 815
Регистрация: 7-06-06
Из: Харьков
Пользователь №: 17 847



Цитата(yes @ Mar 10 2011, 14:11) *
что-то я не понял
если есть 512 бит "сущность" и ее сжимаете/получаете сигнатуру/црц самым прогрессивным методом, известным человечеству. ну, например до 8 бит, то в среднем каждая 256 "сущность" будет иметь одинаковую сигнатуру
то есть нельзя посадить 11 кроликов в 10 клеток так, чтобы в каждой клетке сидело не больше 1 кролика
то есть с сигнатурами можно либо дать ответ: 100% не совпадает, а если сигнатуры равны - то равны ли сущности - достоверно не известно
и если в контексте црц/сигнатур сдвиговый регистр LFSR - то непонятно нафига это надо - сравнивайте побитно сущности.
с LFSR наверно можно уменьшить вероятность если считать несколько сигнатур, но это имеет смысл только при каких-то знаниях о структуре "сущности" - в общем случае - см. про кроликов

У меня на стапеле CRC32. Говорить о неравенстве при истинном равенстве(или наоборот) можно с вероятностью 10 в минус 1х степени. Это обговаривалось выше. Кстати, пускать весь поток извне для сравнения в лоб,-тоже подвергать систему лишнему сбою. Вопрос требует изучения.
Go to the top of the page
 
+Quote Post
i-mir
сообщение Mar 10 2011, 14:56
Сообщение #10


Частый гость
**

Группа: Свой
Сообщений: 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
Эскизы прикрепленных изображений
Прикрепленное изображение
 
Go to the top of the page
 
+Quote Post
Мур
сообщение Mar 11 2011, 07:53
Сообщение #11


Знающий
****

Группа: Свой
Сообщений: 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};
Go to the top of the page
 
+Quote Post
=SSN=
сообщение Mar 11 2011, 08:05
Сообщение #12


Частый гость
**

Группа: Участник
Сообщений: 161
Регистрация: 9-09-08
Из: РФ
Пользователь №: 40 076



Цитата(Мур @ Mar 11 2011, 10:53) *
Тут, при определённом умении, легко реализовать любой полином. От CRC4 до CRC100

А оно надо, умение? CSC Tool.
Go to the top of the page
 
+Quote Post
Мур
сообщение Mar 11 2011, 08:39
Сообщение #13


Знающий
****

Группа: Свой
Сообщений: 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
 
Go to the top of the page
 
+Quote Post
dvladim
сообщение Mar 12 2011, 17:40
Сообщение #14


Знающий
****

Группа: Свой
Сообщений: 654
Регистрация: 24-01-07
Из: Воронеж
Пользователь №: 24 737



Цитата(Мур @ Mar 11 2011, 11:39) *
Мне это известно. Ловушка в том, что в этом тулзе разрядность выхода не 1,- а это уход от сдвигового регистра! Это куча мультиплексоров.

Нормально там все. Пишешь: crc <= newCRC(crc, data); и получается нормальный сдвиговый регистр с xor-ми в нужных местах.
Go to the top of the page
 
+Quote Post
Мур
сообщение Mar 14 2011, 06:48
Сообщение #15


Знающий
****

Группа: Свой
Сообщений: 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;
Go to the top of the page
 
+Quote Post

3 страниц V   1 2 3 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 11th July 2025 - 11:30
Рейтинг@Mail.ru


Страница сгенерированна за 0.01528 секунд с 7
ELECTRONIX ©2004-2016