Hi to all,
this is my first post here and i hope i can find an answer to my
problem as well as to contribute, whenever possible, to
this group!
I have to solve the following problem:
given an integer number of N bits (we can assume that N is <= 32 bit),
which we will call ID, i have to compute another integer
number of M bits, with M <= N. Call this last number CRC. The
properties that CRC should have are:
suppose to fix N and M <= N and use a distance measure d which count
the number of positions at which the corresponding bits are different
(the Hamming distance)
1] if ID1 and ID2 are such that they are similar (for example,
d(D1,D2) is a little fraction of N) then CRC1 (the CRC associated with
ID1)
and CRC2 (the CRC associated with ID2) are much more different
2] the computation of the CRC is deterministic
3] the computation of the CRC is "fast"
4] if the bit pattern of ID is uniform (number of times two adjacent
bits are different) then CRC is much less uniform
5] since M <= N, we have the collision problem (the same CRC
associated to different ID's)...there should not be CRC
that are associated to much more ID's than others CRC
(NB 1. 4) is not so important).
(NB 2. I know i should clarify things when i speak of "similar",
"much more different", "fast" and so on, but to keep things simple,
lets use the common sense...)
I know of the exsistence of the CRC computation using polynomials (i
admit i don't know much more about this topic),
but my system should work with different values for M.
The ideal solution would be the following:
- suppose we are given M. We have two routine:
- SetupCRCM(M) : pre-compute some data that will be used later (such
like an array of integers..). Eventually, it does not do anything
- ComputeCRC(ID, N): return an M-bit values wich is the CRC of the
given ID and wich respects the above requirements.
Is the CRC computation with polynomials the only way? Are there more
simpler algorithms?
Links, reference to books, papers or suggestions are really welcome!
Thank you,
Luca
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
