Access Control System

Hi to all.

I am in the middle of an access control system using keys with 20 digits long each (5bit each digit).

The total number of keys would be 500. So, a PIC and an EEPROM are called to do a store and search function of the huge data for the controller.

The question is, how to implement a quicker way to search the tons of data (in less that 0.5 second if possible).

One idea is to use a b-tree structure but I really did not find how to start filling the data space.

Another would be to use insert-sort algorithm but this is also difficult to implement.

The keys may have random numbers since they will probably be RFiD tags or cards. For example they may look like 0000 0000 0000 0000 3785 or
1349 0000 0000 2131 0090. So there is no relation of the previous or next key.

Any ideas very welcome.

Regards,
Ioannis

How about storing the data as packed BCD and then doing a search on it? Won't it reduce the time to search? I have done a similar system using RFID cards which spit out 10 bytes ids. These are compressed to 5 bytes as packed bcd and I can search these fast. I haven't benchmarked the time.

Jerson

Thanks for the reply Jerson.

The cards to be used are ISO type 125KHz. They respond with 20 digits and when grouped in BCD format, 10 bytes long. If the stored codes are 500, total 5000 bytes, the search time is really long for someone to wait for the door to open.

Ioannis

Ioannis

I think you are making some mistake. The data I have and use suggests that the tags have a 10 digit code of the type
0F0184F20B
I have used both the ISO type tags and also the clamshell cards @125KHz and see no difference in the coding.

Jerson

Thanks Jerson. I'll have a look again. The cards are (although nothing is printed on them) from Promag.

From the reader I still see 20 5bit digits...

Anyway, even if the case is as you describe, 2500 bytes of 5byte group, is a lot of work for a PIC to search in linear manner.

Ioannis

The only sensible option is to organise the Data stored in EEPROM. No, you don't have to sort every single Record entry. Firstly, over-size your EEPROM. EEPROM is cheap and oversizing it will be not much of an issue. The bigger your EEPROM, the easier your job. Secondly, perform a simple calculation on the Record to give you a number (say modulus 20 divide to give you a number from 0 to 19) which we'll call a Hash Key. Divide up your EEPROM (in this example into 20 regions), and store your Record in that zone of the EEPROM corresponding to the Hash Key. Simply do a sequential scan thereafter. In fact you can do a bubble-sort on the records in each Hash Key Zone (rather than in the entire EEPROM) and do a binary search just within that zone. Using this method, when storing a Record, you will not have to sort the entire content of EEPROM, and when retrieving a record, you will be able to do so in about nine Record accesses (worst case) (assuming a file of 500 Records all with the same Hash Key).

Actually, you can be more clever... because your Access Control System will be idle most of the time. When you add a new entry, set a flag in the EEPROM Zone to indicate it is unsorted. Assign a spare area of EEPROM (size of a Zone), and start a process to sort an unsorted EEPROM zone within it during idle time (basically, perform a job process within a job process). When the zone is sorted, assign it the Reference Address of the previously unsorted zone, which itself then becomes the 'spare zone area' for the next sort job when it comes along. That way your EEPROM is dynamically sorted for maximum performance.

Thanks Melanie. 'Hash' was the keyword I was needed to get kick-started!

Yes, EEPROM will be much bigger, and in fact, since sorting, writing, reading and deleting might be often, I decided to place an FM24C256 device instead of the classic 24Cxx ones.

I really appreciated.

Ioannis