Lost in transmission

Sending messages over inter-stellar space is slow and error prone. The signals travel long distances, so attenuate and can be susceptible to interference from various space phenomena. As such, a lot of attention is placed on ensuring accuracy of messages received through the use of validation algorithms. Ideally these algorithms should also allow for a certain amount of message self-correcting to recover from small errors, as the time taken for the message to be resent across the vastness of space would take a long time.

One such message validation algorithm being used on your ship is outlined below.

Validation algorithm outlined

Consider the following incoming binary message (shown as hexadecimal): 5468697320b869732061207d7465737421e13140fc4861

Your computer has recognised the message format and organised it into a grid of hexadecimal bytes as follows:

54 68 69 73 20 b8
69 73 60 61 20 7d
74 65 73 74 21 e1
31 40 fc 48 61

Each row in the above represents 5 bytes of message data plus a 1 byte checksum. This is except for the final row, which represent different checksums, 1 for each of the columns above it.

To clarify, there are 15 bytes of actual data contained within the above message. They are

54 68 69 73 20
69 73 60 61 20
74 65 73 74 21

The rest is checksum data.

Calculating checksums

Look at the first row, add the values of the data bytes together:

54 68 69 73 20 = 1b8

Calculate the modulus, 1b8 % 100 (or 440 % 256 in decimal) to obtain the checksum value for that row: b8 (184 in decimal). Notice that b8 is the value originally given for the top row’s 6th column. This indicates the checksum we calculated matches the one provided, so the data in the row can be assumed to be correct.

The process repeats for all the remaining rows except the last one.

For the last row, 31 40 fc 48 61, the values represent the modulus of the sum of the values for the column above it. For instance, observe that the first column…

54
69 
74

…sum together to 131 hex (or in decimal 84+105+116=305). Again, find the modulus against % 100 hex (or 256 decimal). This result is the checksum for that column: 31 hex. Once again, observe that this is the value originally provided for the first column of the last row, showing it was calculated correctly.

This process repeats for all columns of data (note, we do not do this for the column of checksums).

The above explains how the algorithm validates an incoming message, so what occurs when there is an error in the message that is received?!

Locating an erroneous byte

Luckily for you, there will only ever be one byte received in error. It is also guaranteed to occur in a data byte rather than a validation byte. This means you can triangulate using the row-based validation bytes and the column-based validation bytes to find the erroneous byte. Not only that, but because you know there is only one byte in error, you can even determine what its correct value should be!

Back to the example. Calculating the last column and last row validations produces…

54 68 69 73 20 b8
69 73 60 61 20 bd
74 65 73 74 21 e1
31 40 3c 48 61

But the message originally received (refer to the start) was…

54 68 69 73 20 b8
69 73 60 61 20 7d
74 65 73 74 21 e1
31 40 fc 48 61

If observant, you can identify the validation value at the end of the second row is different (bd compared to 7d), as is the validation at the bottom of the 3rd column (3c compared to fc). This indicates the byte where this row/column intersects is an error - the value 60 is wrong!

Correcting an erroneous byte

The error has been identified. How to correct it?

Find the difference between what you calculated for the checksums and what you received.

The row checksum difference is bd-7d = 189-125 = 64. The column checksum difference is 3c-fc = 60-252 = -192. If you get a negative, add 256 (remember we are using the remainder of 256 so the checksum might have had 256 removed from it), so the column difference is also 64.

This means the incoming message had a value 64 too high in the erroneous byte. This difference value of 64 can be subtracted from the erroneous byte to obtain its correct value.

60 - 40 = 20 (hex)
96 - 64 = 32 (decimal)

So the correct value for the byte is 20 (hex) or 32 (decimal).

To submit an answer, multiply the erroneous decimal value by the correct decimal value, 96 * 32 = 3072.

Your input data

As your input data message is longer, instead of each row having 5 bytes + 1 checksum byte, it is now 10 bytes + 1 checksum byte per row.

The last row of the data sequence will finish with 10 bytes of checksum values for the 10 columns of data.

To find your answer to this problem, locate the erroneous byte. Multiply the erroneous value by its correct value. Your answer is the decimal value of that multiplication.