Wednesday, June 6, 2018

Blind detection of checksums (1)

This is a generalization of T207_test.m to arbitrary checksums, assuming that

  • there is a fixed frame length k
  • the last m bits in a frame are a checksum
  • the checksum is formed by a (possibly non-linear) combination of the first k-m bits in the frame
  • there are no collisions between checksums, i.e., that a given sequence of k-m data bits always map onto the same checksum

The test for a T207 checksum looks like this (thanks to Antonio for providing a bit stream):

T207_test.m

Suppose that we only know that the data consist of frames of 14 bits where the last two bits are a checksum but not know how the checksum is formed and where the frames start. Then a search for the presence of such frames results in the plot below using test_checksum.m

test_checksum(bits,14,2)
Indeed the right start position of the frames is recovered when searching for the minimum number of checksum collisions without assuming anything about the way the checksum is formed besides the frame length and the number and position of the checksum bits.

This method can be easily generalized for checksums which are formed using bits both from the present and from the previous frame, e.g., the GPS navigation message, see 20.3.2.5 in IS-GPS-200H.

No comments:

Post a Comment