Need to store 1.000.000 positions in memory

[kakolon]

Hi,
I need to build a some kind of counter. Picaxe will have stored 1.000.000 positions, starting from number 000001 to 999999. Each positiosn must have a state of 0 or 1.
The picaxe will be reading numbers, first it will have to search for the number, and the chech the state (0 or 1).

How much memory is needed for this task? Do I need external memory?
Do you think that searching for a number in a 1.000.000 positions will take long ?

Any help is much apreciated,

Best regards,
Kakolon

 

[westaust55]

1,000,000 bits of data as a single bit could be stored in 125000 bytes.
But that will involve some maths to store the data - maybe complex but not impossible.
No PICAXE has that much memory, so you would need to use say an i2c based EEPROM. The 24LC256 has hold 32768 bytes so use 4 (or a 24LC128 with 16384 bytes - use 8) would suffice.

So a first question is:
which PICAXE, if any, do you already have?
will need an X, X1 or X2 type for use of the i2c BASIC commands.

 

[BCJKiwi]

Since this is a counter, there may be issues withh eeprom write life.

 

[vttom]

Picaxe will have stored 1.000.000 positions, starting from number 000001 to 999999.

Well, first off, lets see how hard it will be for the PICAXE to support counting that high...

1.000.000 takes 20 bits. If you plan to store the data in a word variable, which has 16 bits, then you can break those 20 bits into 2 separate counters:

1) a 4-bit counter that tells you which of the 16 bits in the data word you're addressing
2) a 16-bit (that's 20bits - 4bits) counter that tells you which data word you're addressing. This is conveniently the size of a word variable.

So, you would need a nested loop to count over all 1.000.000 positions:

for w0 = 0 to 62500 ' This is 1.000.000/16
for b2 = 0 to 16
' Here is where you access a word based on the value of w0
' and a bit within that word based on the value of b2
next b2
next w0

That's the easy part. The hard part will be reading/writing the data out of/into an external memory.

 

[Andrew Cowan]

What's the application? We might be able to think of a neater solution.

A

 

[kakolon]

What's the application? We might be able to think of a neater solution.

A

Hi, This is a very simple parking lot aplication. Where tickets with a barcode are given at an entrance and then the barcode is read in the exit.
First ticket will be 000001, 000002, etc.

Best regards,
kakolon

 

[MartinM57]

Is this going to be used in a real parking lot (car park to us Brits ) or is it just a model/demonstration/proof of concept exercise?

Doing it for real is completely non-simple and working out how to access 125kBytes of storage to set/read the appropriate bit is probably one of the smallest problems you will face.

I'd be thinking of 128K of FRAM and an addressing stratgey where you just work out the bit you want (eg byte 87,567, bit 4 corresponds to ticket number ~700540) and the code goes straight to the FRAM to read/write it.

So there's no concept of searching a list at all.

The real world problems are when the FRAM get's out of sync with the cars that are in the lot, lost tickets, power supply outages etc etc

 

[Jeremy Leach]

So, the bit of data against each number flags whether the person has paid?

I can see the sense in having a huge number range - it's a nice simple system and ensures that you will never get people in the parking lot with the same number, because the daily throughput of vehicles will be much less than the number range.

Storing a database of the whole number range is simple to code, but seems a bit wasteful to me. Instead you could keep track of the current range of numbers in use, and have a rolling section of memory. For instance, if the absolute maximum number of vehicles a day was 10,000 then you could just use 10,000 bits of memory.

EDIT: I agree, that 'real life' would be more complex. I'm assuming this is a project?

 

[Ralpht]

This may be simplistic but why not just Date & Timestamp the ticket with time down to the second in 24hour format

It will be 'simple' to convert the date/time into barcode and use a lot less memory. The CPU just needs to remember that it issued a ticket dated for example: 12052009:133059 - Twelth of May 2009 at one thirty and 59 seconds in the afternoon. I'm using the standard date format for Oz, which I think is similar in the UK but can be arranged differently.

It will be highly unlikely that two cars would go into the entrance at exactly the same second, even with more than one entrance.

At first glance it looks simpler than counting up to a million, and with the exception of lost tickets, is less likely to go out of sync with the real world.

Just a thought that might be worth looking into.

 

[Rickharris]

Depending on the actual application there can never be any more cars in the car park than there are spaces for them - and I guess that will be a LOT less than 1,000,000. So all you need is a count in - count out to establish if there are spaces and identity of the individual ticket. As said here if only 1 entrance time is a good as any other method as only 1 car can enter at any given time.

 

[Andrew Cowan]

Say there are 800 spaces, you could have 800 variable spaces (external EEPROM), and allocate a barcode number to each space.

A

 

[SilentScreamer]

How many entrances do you have? If you have more than one does each PICAXE need to be networked together somehow?

 

[QuIcK]

date stamping sounds easy. put an identifier at the end for which entrance it was stamped at. if there is 2 entrances, theres a chance 2 cars could enter at the same time, thus the identifier removes this problem.

would also let you track which entrance is being used the most (managers like that sort of information).

for the datestamp, you would probably only need time and day, unless its long-stay (more than a month). or even just day-of-week

if its not a 24 hour, then you could describe the hour using 4bits (16 hours).

this would allow you to describe the time someone entered with just 3 bytes
[day:hour][min][second]

if there is 2 entrances, and identifier would be needed, which could be squeezed into the [day:hour] byte:
[id:day:hour][min][second]

more than 2 entrances, and you would need another byte.

 

[hippy]

I think there needs to be more detail provided as to what the system functionality is meant to be, what it needs to do at a high level, what it sets out to ensure and to prevent.

Most ticket systems are implementable without any database and the physical nature of ticketing makes it inherently secure - How would they have got in without a ticket ? How would they have an invalid ticket ? It's unlikely that people will be printing their own and that can largely be handled without a database using checksums.

Issue tickets on the way in, retain or deface them on the way out and you have probably got most bases covered.

 

[Andrew Cowan]

You could use a serial printer (receipt printer/thermal paper)? To print the tickets. Ticket had time,date,paid or no and a checksum.

No need for a d/base.

A

 

[SilentScreamer]

You could use a serial printer (receipt printer/thermal paper)? To print the tickets. Ticket had time,date,paid or no and a checksum.

No need for a d/base.

A

How could this be re read by a picaxe? If the user enters the data into the system then that could work however what is there to stop the user from entering fake data unless a database is used?

 

[hippy]

How could this be re read by a picaxe? If the user enters the data into the system then that could work however what is there to stop the user from entering fake data unless a database is used?

In Post #6 kakolon said the tickets used a barcode so presumably there's a mechanism to read them.

Even if ticket holders had to type a number in, a two digit checksum would mean there was a 99 in 100 chance of made-up data being detected. Increase the checksum to four digits and there's a 9,999 in 10,000 chance of being detected. You don't even have to care about what the other digits mean, each ticket could simply be randomly generated.

I don't know how the odds on fooling the million database compare as it varies depending on how long it's been operating, how long the fraudster knows its been operating, if he knew a ticket number issued, or not handed in, and how long ago that was.

If there are a million tickets, one thousand potentially active at any time, it's a 999 in 1000 chance of being detected. If he knows only half a million have been issued it's a 499 in 1000 chance of being detected; the odds of getting away with it have doubled. If he knows a ticket number recently issued there's a good chance it's not been handed in and the odds are that this could be used successfully.

A sequentially generated ticket number system is likely more prone to forgery than a randomly generated one.

 

[QuIcK]

for those that dont know how barcodes work, there is a font (well, numerous) that will turn letters into barcodes.

you may be able to get a printer that will convert ascii to barcodes, but more likely you will have to write a program and pixel-set it. as a barcode will only change in 1 axis (ie they are verticle lines), it shouldnt take up too much memory to do this.

barcode readers generally function as a keyboard.
so if a barcode is "Ae14", the barcode reader will 'type' "Ae14" into the computer through the ps/2 port. im not sure that it does case, however.

so, theoretically, that could be interfaced using the "keyin" command & associated pin.

 

[Andrew Cowan]

We'll have to wait and see how kakalon was goin to read the barcodes.

 

[kakolon]

Hi,
Thanks for all the posts,

I'll explain more details of the system.

The parking lot is not a paid one, it's just for security purpose. There is only one entrance and one exit.
Entrance and exit are not connected to each other.
I've got the system working ok. In the entrance I've got a picaxe 18x dealing with the ticket codebars printing to a thermal printer.
In the exit there is another picaxe 18x, connected to barcode scanner reading the barcodes.
The 1.000.000 positions is meant because this quantity, avoids that a used ticket can be usded again, at a later time.
As picaxes dont are not connected and don't share the same database, a 1.000.000 positions, makes the system work for a long time. Before the database gets full.

Best regards,
kakolon

 

[hippy]

We're still missing something in the overview; a rationale.

I can't see what this system attempts to prevent, or how it provides 'security'.

 

[Andrew Cowan]

Instead of having certain numbers and looking up data, just store the date and time it is valid in the barcode. No lookup needed.

A

 

[manuka]

The simpler date/time coding seems to win hands down in this aplication. It's not as if the clients are trying to duplicate the likes of currency after all. How much are they paying anyway? Is the exit manned? Do they pay as they leave? "Early bird" rates?

As one who has memories of arguing the toss with both parking men & machines,printed time stamp based coding (perhaps via a DS1307?) has the immense further benefit of allowing at least modest human insights when later disputes arise. Such disputes may relate to "what time DID you clock in Monday",vandalism,theft or car damage - time based records may be crucial. In contrast the only feature of a plain sequential number, such as 130769, is that it indicates an earlier parker than a 130799.

 

[SilentScreamer]

I don't know how the barcode reader is connected however why not use two 16 bit numbers. Each day the system increments the first 16 (or even 8) bit number. The system then uses the second 16 bit number to issue the days numbers once the day ends the last days numbers are disregarded and the the first 8 or 16 bit number is incremented.

0000100568 = first day running and the 568th car to enter
0168505689 = 1685th day running and the 5689th car

Could this work?

 

[Ralpht]

In the exit there is another picaxe 18x, connected to barcode scanner reading the barcodes.
The 1.000.000 positions is meant because this quantity, avoids that a used ticket can be usded again, at a later time.
As picaxes dont are not connected and don't share the same database, a 1.000.000 positions, makes the system work for a long time. Before the database gets full.

If the Picaxes are not connected in any way including not using the same database - how will the exit picaxe know if any individual ticket is valid and not reused.

It is far too easy to get the enty exit system completly out of sync with each other. I'd almost guarantee it will fall over within a few hundered cars going in then out.

As per my post #9 - A date/timstamp is the only logical and least error prone system to use in this scenario. Not perfect by a long shot but far better and less likely to be misused than sequential numbers. And I would tie both picaxe databases together although in the date/time ticketing system you will have a far simpler database (if any).

Use the KISS principle here- don't complicate something that is really simple.

We're still missing something in the overview; a rationale.

I can't see what this system attempts to prevent, or how it provides 'security'.

Same sentiment here - if it is not a paid for ticketing arrangement, what real point does it have any way?

 

[Jeremy Leach]

Yep, I just don't get the security bit too. Seems an awful lot of bother for an unpaid parking lot.

 

[hippy]

If the Picaxes are not connected in any way including not using the same database - how will the exit picaxe know if any individual ticket is valid and not reused.

It took me a while to understand that but it does work. It logs tickets which are presented on exit so they cannot be re-used more than once. A simple test of 'have we seen this ticket before ?'

What I don't understand is what this achieves, how presenting a previously used ticket would gain the holder anything.

 

[Ralpht]

Hippy:

It took me a while to understand that but it does work. It logs tickets which are presented on exit so they cannot be re-used more than once. A simple test of 'have we seen this ticket before ?'

What I don't understand is what this achieves, how presenting a previously used ticket would gain the holder anything.

Yes Hippy, you are correct, as long as all exit tickets are checked and logged/stored, then I agree it will work, as long as the real world doesn't get in the way. It just seems to be a massive overkill for something that has no security or financial benefit.

It would make a good programming exersise though.

 

[Wrenow]

This may be simplistic but why not just Date & Timestamp the ticket with time down to the second in 24hour format

It will be 'simple' to convert the date/time into barcode and use a lot less memory. The CPU just needs to remember that it issued a ticket dated for example: 12052009:133059 - Twelth of May 2009 at one thirty and 59 seconds in the afternoon. I'm using the standard date format for Oz, which I think is similar in the UK but can be arranged differently.

I agree, but prefer the format YYYYMMDD-HHMMSS, using a 24 hr clock, as all dates will automatically be generated in straight sequential order. Actually started dating my pages this way while taking notes back in the 60's.

Cheers,

Wreno

 

[manuka]

Wreno: Me too- but "time moved a lot slower in the old days", so I used to let the seconds slide!

 

[Ralpht]

WRENOW:

....but prefer the format YYYYMMDD-HHMMSS, using a 24 hr clock, as all dates will automatically be generated in straight sequential order. Actually started dating my pages this way while taking notes back in the 60's.

Now I think about it, it makes a lot more sense that way and will require a bit less number crunching.

I am so used to the " Day-Month-Year " format used here in Oz that I never thought the "Year-Month-Day" format would be more useful in certain circumstances.

I think I'll start dating my projects in the same manner.
Ralph