ADVERTISEMENT

Supplementary information to "A Design Example"

How receivers learn the values of a and b

If the code a x X + b x Y is going to be fixed once and then used for many strings X and Y, then the receiver can learn a and b through the following procedure. In the very first transmission, it is made known to everyone that the messages to be sent will be X = 1 and Y = 0. As a result, the message received will be a x 1 + b x 0 = a. In the second transmission, the messages to be sent will be X = 0 and Y = 1, giving a x 0 + b x 1 = b. The cost of this procedure can easily be amortized over subsequent uses.

How the receivers use the output from node E to recover the value of X and Y

Carl in the example receives 21, the value of X, from node A. From link 6, Carl knows that 3 x X + 20 x Y = 23, as defined by the code. So Carl's computer essentially plugs in 21 for X and asks, for what value of Y is the following equation satisfied?
3 x 21 + 20 x Y = 23.

As before, the way we define addition and multiplication always returns values in the range 0 through 31, and the computer finds that 3 x 21 = 31. Well, it finds that 3 x 21 = 63 in standard multiplication. But, using our definition, the computer subtracts 32 to get a value within the desired range (0 through 31), ending up with 31. Then it subtracts this value from both sides of the equation, finding
20 x Y = 2331

In traditional arithmetic, the 2331 would be –8, but –8 is outside of our allowed range. To get a value in range, the computer adds 32. The end result is
23 ¿ 31 = 24

Which means that
20 x Y = 24.

Only one value in the set 0 through 31 satisfies that equation, namely
Y = 30.

How so? Because in traditional arithmetic 20 x 30 = 600, and subtracting 32 18 times leaves a remainder of 24.

Similarly, Dana's computer learns that 3 x X + 20 x Y = 23 and that Y = 30

Together, that information implies 3 x X = 2320 x 30 = 2324 = 31
and the only value of X satisfying 3 x X = 31 is
X=21.

Share this Article:

Comments

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Scientific American Holiday Sale

Give a Gift &
Get a Gift - Free!

Give a 1 year subscription as low as $14.99

Subscribe Now! >

X

Email this Article

X