How many possible invalid AIS message body combinations are there for a specific checksum?

Question

According to the CATB AIS Specification, there is a 2 digit checksum to check an incoming AIS message for validity:

Here is a sample AIS message:

AIVDM,1,1,,B,177KQJ5000G?tO`K>RA1wUbN0TKH,0*5C

The actual AIS message body is the payload which is:

177KQJ5000G?tO`K>RA1wUbN0TKH,0

And the checksum is on the end which is:

5C

Each character placeholder can be a total of 64 different characters. The checksum, however, is tested using a weird XOR calculation which may skew the calculation using finite math. My question is, how many invalid message payload combinations exist for each checksum? That is, if the checksum only has 64^2 or 4,096 combinations, then there are X chunks of payload combinations that match each checksum, and since only 1 of those are valid per AIS message the others would constitute invalid messages (that would still pass the checksum).

Answer 1

You can view the payload as being 8 bit strings of length N where N is the length of the playload. The first bit string being all the most significant digits, the next the second most significant digits etc.

A parity check will eliminate half of these possibilities. So the number of possible passing strings will be $8(2^{n-1})$. Note many of the passing payloads will contain strings with characters outside the given alphabet.