Error Detecting Codes: An example Ad am Pi ggott May 2023 Most communication channels are subject to noise that creates er rors. \"Fe say the channel is unreliable. If you have played the game of \"telephone\". also known as \"whispers\". you have seen an extreme example of the errors that are brought into communication via unreli able channels. One needs to realise that almost all of the channels of communication we use are unreliable. 13$th are channels unreliable? Commlmication chamlels are subject to interference. Even when commlmication takes place using highly engineered equipment such as satellite and microwave transmission. signals fade. while weather and other disturbances occur between the transmitter and receiver. For example. here is a website that dis cusses the effects that heavy rain and snow. ice and water accumulation can have on a satellite TV reception: http:ffdishcab1e.ccmfrain_ fade.htm Unreliable channels are a problem because we need communication to be reliable! One way to create reliable communication over unreliable chaImels is to add redlmdant information to the message in a clever way so that one can say either: [1) this message has denitely been corrupted and should not be acted upon; or [2) there is no evidence that this message has been corrupted so it is probably an accurate record of what was sent. 'What we are describing is an error detecting code. 1 Error Detecting Codes Most error detecting codes work as follows. Let A denote the set of all possible messages. Let C denote another nonempty set. Let h : A A C denote a function called a hash Jf'rtnctt'on. "Whenever a sender wishes to transmit a message rn E A, they instead transmit a pair [m,c) with Mm) = c, which happens to be an element ofA x C. So the sender sends the message and something else which is computed from the message. The recipient receives a transmission [m', c'). If the transmission went well, then rn = m' and c' = Mm}; but the recipient cannot know rn to check this. The recipient can only compute Mm') and check it against (9'. If Mm') a c', then the recipient knows that something definitely went wrong in the transmission; in this case, the recipient should not act upon the message [they might instead ask for a retransmission an nntornottc repent request might be built into the communications protocol). In the case that Mm') = c', no error is detected. This does not necessarily mean that rn = rn'. Instead it means that one of the following has occurred: 1. rn=rn'and c=c' 2. rn a m' and c = c' and Mm) = Min") 3. mat in' and eat c' and Mirn') = e' The rst case is the desirable scenario that the message was transmitted accurately and sender has no reason to doubt its accuracy. The second and third cases are scenarios in which the message contains errors, but the recipient has no reason to suspect this. These are dangerous, so we would like to minimize the occurrences of the second and third cases. The likelihood of the second case depends on how many different mes- sages map to the same \"hash code\". The likelihood of the the third case also depends on how many rliHerent message maps to the same hash- code, and how random-like the function h is. An excellent choice of it makes the second and third possibilities unlikely, while keeping C small so that Min) is small for every message, and so that the transmissions are not much longer than the messages. 2 ISBN-1 0 Notation: For any positive integer of and any integers a and b, we snaii write a f t) instead ofa E b ( mad of}. So a f b means that d divides b - a. An [SET-LIE]| is a 10 digit code assigned to a publication (books etc). Its use was standard in the publishing industry between 19TH and 200?. The rst 9 characters of an ISBN-1UI code are digits that uniquely iden- tify the publication [the title, author, edition etc). The tenth character, which is either a digit or the letter X , is a check character used to detect errors in transmission or recording. More formally, let X = 10 and D = {0,1,2,3,4,5,5,7,8,9}, C = {0,1,?,3,4,5,5,7',8,9,X}, A=DxDx---XD. \\.,_,.r .9 times \"We define a function h : A > C by the rule .9 V[o1,...,og)EA f1({1,...g)) ghts. i=1 \"When the ISBN-10 is written, no parentheses or commas are included. Often hyphens are used (for reasons we may ignore). For example, the paperback third edition of Herstein's \"Abstract Algebra\" was assigned the ISBN-1f} code [1471358792. [11 this case we have (11 =Ua2=4as=754= 1:015 =3as =557 =85s =75s =9- Then : m,- =1(IJ)+ 2(4) + 3(?) + 4(1) + 5(3) + 6(6) + T(8) + 8(?) + 9(9) - =2??=25(11)+2. Thus we have that the message is m = (0,4,T, 1, 3,6,8,T, 9), and the hash-code is Mm) = 2. The transmission is then the concatenation of these; that is, the transmission is the message followed by the hash- \f\f\fis not divisible by 11. Now in ' f '.l" to; E arrU 31] . 1: 3:] if] 1 =1 in; :2: io,- [by the lemma, because m is a valid ISBN-10} it11b i do; [1,} [using algebraic properties of summation}} E o} 01,-) + Mo}, ck) [because a,- = a; when 1' a j, k). E ak Hi) + Ho,- ck) [because a; = oh. and :11 = 51,-}. H l U\" - Lilla; - as} H 1 Since 1 17. j s: k g 10, we have that 1 g It j E 9; it follows that 11 does not divide k j. Since 0 S a_,-,o;, g 10 and :1,- 3E ok, we have that l| E o,- m, E 1|]| and a,- m, I]; it follows that 11 does not divide a,- ck. By the Prime Divisibility Property, 11 does not divide {e j}[c_,- gr}. Hence 2,12, m; is not divisible by 11. III 3 ISBN-13 An ISBN-13 is a 13 digit code assigned to a publication [books etc). It replaced the ISBN-1E} on January 1, 2007'. The rst 12 characters of an ISBN-l3 code are digits that uniquely identify the publication [the title, author, edition etc). The thirteenth character is a check digit used to detect errors in transmission or recording. More formally, let \f\f3n; + . . .3612 + [133 is not divisible by 10. D If any two distinct digits in a valid ISBN-13 are transposed, then the resulting string of 13 digits is not a valid ISBN 13. 'We note that both 102000000000? and 201000000000? are valid ISBN- 13's; perhaps more alarniinglv, we note that both 160000000001 and 61010000000001 are valid ISBN-13's. Hence we know that the ISBN-13 error deteeting code does not always detect the transposition of distinct digits. 4 The Task: TrySBN-IB Imagine that publications are now to receive 15 digit identificat ion num- bers. Publishers agree to add a 16th character which will be an error detecting code. Invent an error detecting cede scheme, called TrySBN 16, that is guaranteed to detect: (T1) errors in which exactly one character is misrecorded; and (T2) errors in which two distinct characters are transposed. [n no more than 4 pages, describe your code scheme. 'Write your an- swer in the form of a memorandum for the leaders of the publishing industrythe idea is that you are trying to convince them that your scheme achieves its aims, and is a good choice for their industry. You may assume that your audience has taken a course like MATHEWS, so they know the notation of congruence arithmetic including the variation of the notation used in this document. An excellent memorandum will give some context of the scheme, describe it with precision, prove that the error detection scheme will detect errors of type (T1) and (T2), and give examples of errors that will not be detected by your code scheme