Question 1.
ISDN code is 978-80-7472-498-7, using the ISBN-13 check digit calculation we are able to determine missing number.
9*1 + 7* 3 + 8*1 + 8* 3 + 0*1 + 7* 3 + 4*1 + ^*3 + 2*1 + 1*3 + 9*1 + 8* 3 + 7 * I = 0 (mod 10)
141 + 3« = 0 (mod 10) x = 3
Using the complete ISBN 978-80-7432-498-7, we are able to reveal title of the book which is An-
tifragilita: Jak těžit z nahodilostí, neurčitosti o, chaosu.
Question 2.
AU three codes have in common that they assign one codeword to each of í-bit messages. There are 2f such messages, so for all cases, M = 2^.
(a) (m£,2e,m).
Obviously, n = ml (as the original message is repeated m times) and M = 2f.
As each message is copied m times, given two messages differing in x bits, corresponding codewords differ in mx bits. The minimum difference between messages is 1, so d = m.
(b) (2£,2f,rain{í,3)).
Obviously, n — 2t (as the original message of length I is appended by a check bit for every neighboring pair, including the first-last pair, of which there are () and M = 2ť.
For two messages differing in x bits, the corresponding codewords differ in x bits + count of neighboring pairs of bits in the messages where one bit in the pair differs between messages and the second one does not (let's call this count y). This puts two upper bounds on minimum distance of codewords: d <x + y = i + 0 = £ (two codewords corresponding to two messages differing in all bits), and (i<z + j/ = l + 2 = 3 for messages differing in one bit (yielding codewords thai differ in one ''message" bit and two "xor" bits).
For i > 2, d can't be any less than the upper bound, as codewords differing only in 1 or 2 bits are impossible, as seen from the definition of the "xor" part.
(c) (£+(«(£-l))/2,2f,ť).
Obviously, n — Í + (1(1 — f))/2 (an i-bit message is appended by a checkbit for every pair of bits) and M — 2f.
We now show that all pairs of codewords differ by at least i bits. Let's take any two messages, which differ in x bits (meaning i — x bits are the same). The corresponding checksums will differ in bits that correspond to pairs of message bits where one differs between messages and the second does not. That means x(l — x) bits. The two codewords then differ by x + x(£ — x) bits, which is minimized for x — (. (this is the case when all the message bits differ, checksums are the same, which also gives a concrete example for upper bound of d), so d = I.
Question 3.
(a) C] = {001,110}
(i) We need to find greater probabilities of the correct, decoding for the corresponding codeword (we know that p < 1):
i.	P(000	001)	= (i	-pf	■P
ii	P(001	001)	= (i	~pf	
iii	P(010	001)	= (i	-p).	P2
iv.	P(011	001)	= (i	~Pf	■P
V.	P(100	001)	= (i	-PI-	P2
\ i	P(101	001)	= (i	-P?	■P
vii.	P(110	001)			
viii.	P(lll	001)	= 0	-Pi-	P2
i.	P(000	no)	= (1	-P)-	P2
ii	P(00]	no)	= p*		
iii	P(010	no)	= (1	-Pf	■P
iv	P(011	no)	= (1	~P)-	P*
v.	P(100	no)	= (1	-P?	■P
vi.	P(101	110)	= (1	-P)-	P2
vii.	P(110	no)	= (1	-Pf	
viii.	P(lll	110)	= (1	-Pf	■P
The words 000,001,011,101 are decoded as codeword 001, while the words 010,100,110, 111 are decoded as codeword 110.
(ii) The formula for the total probability is in this case the same for the both codewords:
P = (l-p)3 + 3-(l-p)2-p If p = 0.05. then probabilities of the correct decoding are:
P(001) = P(110) = 0.95s + 3 ■ 0.952 ■ 0.05 = 0.99275
(b) C2 = {0000,1110,0101}
(i) The same method is applied for C%.
i. Words which cannot be uniquely determined: 0001, 0011, 0100 and 1001 (the same probability for more codewords).
ii. Words which are decoded as codeword 0000: 0000, 0010 and 1000.
iii. Words which are decoded as word 1110: 0110, 1010, 1011, 1100, 1110 and 1111.
iv. Words which arc decoded as codeword 0101: 0101. 0111 and 1101.
(ii) The formulas for the total probabilities are:
P(0000)   =   (1 - p)4 + 2 ■ (1 - pf ■ p
P(1110)   =   {1-pf + 4-(l-p)3 -p + il-pf p2
P(0101)   =   (l-p)4 + 2-(l-pf p
If p = 0.05, then probabilities of the correct decoding are:
P(0000)   =   O.OS4 + 2 ■ 0.953 ■ 0.05 = 0.9
P(1110)   =  OM11 + 4 ■ 0.95s ■ 0.05 + 0.£>52 • 0.052 = 0.988
P(0101)   =  0.954 + 2 ■ 0.953 ■ 0.05 = 0.9
Question 4.
(a) yes; C% can be obtained from Ci by Hipping all the bits
(b) no; C\ contains a pair of codewords with hamming distance 4 (0011, 1100), but there is no such pair in C2
(c) no; different number of codewords (Ci has 16. C2 has 11)
Question 5.
(a) (i) Entropy for binary code: S(X) — -^,J.^xp(x)log2P(x)
-T5 * loS2 jjj - 2* |; * log2 =| - i * log2 1 - 2 * i * log2 i = 2.470951
(ii) Entropy for ternary code: S(X) = —J2xexP(x)^°&3P(x)
~To * lo& S " 2 * |j * log3 I, - i * log3 \ ~ 2 * io * log3 s = 1-559
(b) (i) Huffman tree
A = 11 £ = 101
C = 100
D = 01 E = 001 F = 000
Average code length: 2 * 0.3 + 3 * 0.15 + 3 * 0.15 + 2 * 0.2 + 3 * 0.1 + 3 * 0.1 = 2.5 Efficiency: ™ = 0.98838
(ii) Huffman tree (X is added as dummy symbol)
A= 1 B = 21 C = 20 D = 22 E = 02 F = 01
Average code length: 0.3 + 2 * 0.2 + 2 * 0.15 + 2* 0.15+ 2* 0.1 + 2* 0.1 = 1.7 Efficiency:   '"'.'""j, : 1^ = 0.917
By comparing efficiencies, we can sec that binary code is more efficient than ternary code.
Question 6.
(a)
A2(S,5) = 4
not a proof (wasn't required), only how did I get to my answer
• wo can assume that 00000000 6 C
• all other words have to have at least 5 l's.
• C can contain max 2 words with 5 l's (d — 5).
• C may contain at most 1 word with at least 6 ones
- if 11111111 6 C, than it cannot contain any other word (because d = 5) and M would be 2
- if C contains word with 7 l's (e.g. 11111110), than it cannot contain any other word (because d = S) and M would be 2
- if C contains word with 6 l's (e.g. 11111100), than it could only contain 2 other words with 5 l's (e.g. 01010111 and 10101011) and M would be 4
- if C would contain only 00000000 and words with 5 l's (max 2), then M would be 3
example of binary (8, 4, 5)-code:
C = {00000000,11111100,01010111,10101011}
(b) there is no Aq(n, d, w) if d > 2w.
Because there arc no two words with weight w and distance d\id> 2w Proof:
• let's take any two words v\, V2 of length n with weight w,
■ let's say these word have x non-aero symbols on the same positions and y non-zero on different positions, where 0<i<ibA0<j<ioAi + !/ = iii
- if x = 0, then y = w — x — to, therefore none of non-zero symbols are on overlapping positions, therefore h{v\,wi) = 2y + x = 2w, contradiction to d > 2w
- if x = 1, then y = w — x = w — 1 therefore exactly one non-zero symbol is on the same position in both words, therefore h(v\, V2) <2y + x< 2w — 1, contradiction to d > 2w
- if x = i", where 0 < k < w then y = w — k therefore exactly k symbols are on overlapping positions, therefore h(vi,V2) < 2y + x < 2w — 2k + k < 2w — k. contradiction to d > 2w
Therefore for all possible positions of non-zero symbols of any two words with weight w. is distance less or equal to 2w