Question

Hotel Rooms and Beyond: Error-and-erasure correction leveraging the CRT (58 pts) Note: for this entire problem, you can use properties of the Chinese Remainder Theorem that we discussed in lecture, notes, homework, and discussion without proof and without having to specify all the details. Alice is staying at a hotel and she wants to share her room number with Bob by leaving a sequence of notes in a list of pre-arranged locations.

i) There are only 100 possible hotel rooms, labeled 0 to 99.
ii) Alice takes her room number p and computes the remainders y; = p mod pi. The specific p; that she uses are pı = 3, p2 = 5,23 = 7,24 = 11, and ps = 13.
iii) She writes y, on the i-th note and places the note in location i. (Both Alice and Bob know which location corresponds to which numbers i and p.) This sequence of notes can be viewed as a codeword y(p). For example, if Alice is in room 51, she sends the codeword y(51)=(0,1,2,7,12) since 51 mod 3=0, 51 mod 5= 1, 51 mod 7=2, 51 mod 11 = 7, 51 mod 13= 12.

(a) Unfortunately, there is a chance that some of Alice's notes get blown away by the wind. Those missing notes will be treated as erasures and denoted by X It turns out that Alice is in room 51 as above, so she sends the codeword (0,1,2,7,12). Bob gets the received symbols (0,1,2,X,X). Explain how Bob can leverage the CRT to identify Alice's room number. (Alt + A)
(b) Generalizing the previous part, prove that in the case of up to two erasures anywhere, your scheme will always correctly identify the room number. For this part, feel free to just use the properties of the CRT along with the following facts. • Pi

Answer 1

Explanation:

From the information given we know that

And we know as well that

Remember what that the Chinese reminder theorem states.

Theorem:

Let p,q be coprimes, then the system of equations

has a unique solution .

Now, if you read the proof of the theorem you will notice that if

the the solution looks like this.

Now. you can easily generalize what I just stated for multiple equations and you will see that if you apply the theorem for this case it is straightforward that

Therefore, Alice is in room 51.

(b)

Using the Chinese reminder theorem you need less than 2 erasures. The process is very similar.

Explanation:

Answer 2

Explanation:

From the information given we know that

`p \equiv 0 \,\,\,\, \text{mod(3)}\\p \equiv 1 \,\,\,\, \text{mod(5)}\\p \equiv 2 \,\,\,\, \text{mod(7)}\\`

And we know as well that

`p \equiv x \,\,\,\, \text{mod(11)}\\p \equiv x \,\,\,\, \text{mod(13)}`

Remember what that the Chinese reminder theorem states.

Theorem:

Let p,q be coprimes, then the system of equations

`x \equiv a \,\,\,\, mod(p)\\x \equiv b \,\,\,\, mod(q)`

has a unique solution
`mod(pq)`.

Now, if you read the proof of the theorem you will notice that if

`q_1 = q^(-1) \,\, mod(p) , p_1 = p^(-1) \,\,mod(q)`

the the solution looks like this.

`x = aqq_1 + bpp_1`

Now. you can easily generalize what I just stated for multiple equations and you will see that if you apply the theorem for this case it is straightforward that

`p \equiv 0*35*[35^(-1)]_3+1*21*[21^(-1)]_5+2*15[15^(-1)]_7 \,\,\,\,\,\,\,\, mod(3*5*7)\\p \equiv 1*21*1+2*15*1 \,\,\,\,\,\,\,\,mod(105) \\p \equiv 1*21*1+2*15*1 \,\,\,\,\,\,\,\, \\p \equiv 51`

Therefore, Alice is in room 51.

(b)

Using the Chinese reminder theorem you need less than 2 erasures. The process is very similar.