Easyelectronics.ru

Электроника для всех
Текущее время: 27 апр 2018, 13:43

Часовой пояс: UTC + 5 часов



    • JLCPCB - Платы прототипов всего за 2$ c бесплатной доставкой (при первом заказе)
    • 10 PCBs за $2 для 2 слоев, $15 для 4 слойной, $74 для 6 слойной платы.
    • Крупнейший китайский производитель прототипных плат. 290000+ клиентов & 8000+ заказов в день!
    • LCSC - Крупнейший китайский онлайн магазин радиодеталей.

Начать новую тему Ответить на тему  [ Сообщений: 11 ] 
Автор Сообщение
 Заголовок сообщения: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 02 авг 2017, 10:27 
Только пришел
Аватара пользователя

Зарегистрирован: 30 май 2011, 18:31
Сообщения: 18
Откуда: Москва
1. Сразу скажу, что я осЁл, поэтому буду рад любым советам, в т.ч. тыканьем в гугол (по делу), т.к. самому подобрать ключевые слова для гугла не получилось.

2. Изобретаю блокиратор нежелательных звонков для городского телефона. Т.к. имеющиеся в продаже на нашем сраном МГТС работают через раз и я эту проблему решил, но осталась сабжевая. По-сути это Caller ID АОН с расширенным черным списком. Аппаратная часть состоит из ардуины про мини, дисплея 16х2, 5-и кнопок висящих на АЦП, пищалки, декодера на HT9032 с дополнительной обвязкой в виде детектора звонка и устройства захвата линии и EEPROM'а на I2C 24C64. В данный момент работает просто как обычный АОН. Списог входящих реализован во встроенной EEPROM на 48 ячеек, в формате 21-го байта, пример:
1 байт порядковый номер в списке (1-48)
1 байт признак черного списка (0x2A, "*")
8 байт дата/время от оператора
11 байт номер телефона от оператора

3. Планируется хранить номера черного списка во внешней EEPROM в формате 11-байт, т.е. просто телефонный номер в виде: 84951234567 за ним следующий и т.д.
24С64 хватает, чтобы набить туда >700 номеров, соответственно нужен быстрый поиск по этим 700 номерам, в первую очередь это нужно при входящем звонке, чтобы определить сидит ли номер в черном списке или нет, вторично это нужно для установки признака черного списка в списке входящих.
Как это можно реализовать? Если ограничиваться строго российскими звонками, то восьмерка в начале будет всегда, а дальше 10 цифр могут быть какие угодно.

_________________
Life is a long jump, from the cunt to the grave...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 02 авг 2017, 11:00 
Только пришел

Зарегистрирован: 20 июн 2016, 15:31
Сообщения: 8
За таблицей с номерами в ЕЕПРОМ создать индексную таблицу и по ней искать .
Правда придется ее пересчитывать каждый раз когда меняется основная.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 02 авг 2017, 11:05 
Старожил

Зарегистрирован: 16 ноя 2012, 07:47
Сообщения: 2563
поставить FRAM. Чтение/запись на скорости SPI, никаких задержек. Flash тоже достаточно быстро читается.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 02 авг 2017, 11:20 
Старожил
Аватара пользователя

Зарегистрирован: 05 фев 2013, 00:58
Сообщения: 2727
Откуда: Тольятти
Отвести первые 700 байт под хэши, искать по ним. В редчайшем случае, если хэш совпадает, делать 2 сравнения строк вместо одного.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 02 авг 2017, 11:29 
Старожил
Аватара пользователя

Зарегистрирован: 06 ноя 2013, 16:07
Сообщения: 524
Откуда: Германия
А сколько времени занимает полное чтение/запись 24С64?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 02 авг 2017, 11:52 
Старожил

Зарегистрирован: 10 окт 2014, 00:48
Сообщения: 4214
Вариант:
1. Удавить жабу
2. Взять STM32F030F4
3. В качестве хранилища использовать Flash. ~20K хватит на много номеров
4. Телефонный номер - это число из десятичных цифр. Значит - храните не ASCII, а именно то ЧИСЛО, что есть. Выйдет 2x uint32_t. Для борьбы с значащими нулями, номер обрамлять фиксированными цифрами - 8 = начало.
5. Оптимизация поиска - Flash, это uint16_t, поэтому первый проход делать по сравнению начального uint16_t номеров. (Мод - сравнивать не по 0 слову, а по 1. В 0 слове лежит код города, а он не уникален)
Без оптимизаций, выйдет < 1к чтений/проверок для нахождения номера. Короче, "пара ms".


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 20 сен 2017, 12:35 
Заглядывает иногда
Аватара пользователя

Зарегистрирован: 23 июл 2010, 09:54
Сообщения: 167
Откуда: Чебоксары
john1770 писал(а):
За таблицей с номерами в ЕЕПРОМ создать индексную таблицу и по ней искать .
Правда придется ее пересчитывать каждый раз когда меняется основная.


Или перед таблицей номеров (все равно максимальное кол-во номеров ограничено). Каждый раз переписываете индексную таблицу, упорядочивая по возрастанию или по убыванию номера телефона. К этой таблице можно будет применить методы быстрого поиска, например метод деления пополам.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 20 сен 2017, 14:19 
Старожил

Зарегистрирован: 08 авг 2013, 09:43
Сообщения: 456
На самом деле даже диапазон номеров 81000000000-89999999999 занимает 34 бита. Но DEF коды у нас ведь определенные. Т.е. 3,4,8 и 9 после 8ки может идти только. Уже опять же если по этой цифре отделить, то остаток уже легко в uint32_t вписывается. Можно 4 отдельных таблички завести. А там уже может и последовательно считывать всю табличку достаточно быстро будет.
Если нет - то наверное оптимальнее хэш-таблицу поиска сделать. Например брать CRC8, где результат будет позиция номера в массиве, а оставшуюся половину таблицы (у нас 64K / 4 табилицы = по 512 х 4-байтовых ячейки можно хранить, а CRC = 256 ячееек) использовать для разрешения коллизий.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 20 сен 2017, 15:52 
Старожил

Зарегистрирован: 08 авг 2013, 09:43
Сообщения: 456
Еще как вариант: Фильтр Блума. Но возможны ложно-положительные срабатывания и посмотреть текущий список номеров никак нельзя будет. Хотя ложноположительных я прикинул даже банально для 1 функции CRC16 будет шанс коллизии менее 0.002%.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 20 сен 2017, 16:17 
Старожил

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 2865
отсортировать строки по возрастанию при записи, причём можно отдельно хранить отсортированные индексы чтобы каждый раз при добавлении всё не перелопачивать, хотя тоже не особо большая проблема. ну а дальше бинарный поиск и тогда прочитать надо будет максимум десяток номеров.
хотя все 64кбит даже на 400кГц целиком прочитаются за 150мс в чём сложность просто читать всё и на ходу сравнивать.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Быстрый поиск по внешней I2C EEPROM
СообщениеДобавлено: 20 сен 2017, 17:37 
Старожил

Зарегистрирован: 08 авг 2013, 09:43
Сообщения: 456
Ну это если список не изменять с самого ус-ва. Только я тогда вообще не вижу смысла в EEPROM внешней, когда можно в прошивку (flash) захардкодить номера. Вон с помощью gperf можно сгенерить идеальную хеш функцию сразу на C/C++ по заданному списку номеров, для быстрого поиска )


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB