## Reprezentace čísel, aritmetika

číslo A je:
A = SUM[-m,n](aizi)    (1)
(tj. i náleží (-m,n); číslice s i <=0 jsou za řadovou čárkou)
a - číslice, 0 <= a < z
i - řád
Z(či M) = zn+1 (modulus)
epsilon = z-m  jednotka (unit), nejmenší reprezentovatelná jednotka, viz LSB

#### Vlastnosti

Z (1) plyne, že Amin = 0 a že Amax = zn+1 - z-m

### Zobrazení záporných čísel

Z ("M" v angličtině) = Amax+1 = počet čísel zobrazitelný s daným počtem bitů
D(A) značí obraz (image) čísla A v daném kódu (tj. zakódované číslo A)

#### 1.Doplňkový kód (complement code)

Čísla od 0 do Z/2 jsou kladná, čísla od Z/2 do Z kódují záporná čísla z rozmezí -Z/2 až -1.
Platí -Z/2 <= A < Z/2

 A >= 0 A < 0 D(A) A Z+A

Příklad, Z = 16 (tj. -8 <= A < +8)

A = -6  =>    D(A) = 16 - 6 = 10 je obraz -6

Z = A + A + 1 (A je inverz od A; A + A = Amax neb ai=amax-ai). [pozn.: místo 1 má být epsilon]
D(A<0) = invert A, přičti epsilon (1 v dvojkové), ignoruj carry.
Pokus získat absolutní hodnotu -Z/2 => overflow.
Pozn.: v angličtině se užívá C(X) místo D(A).

Aritmetický shift

a) doprava (= dělení z) pro A<0: D(A) = Z + A, D(A/z) = Z + A/z, D(A)/z = Z/z + A/z
=> D(A/z) = (Z + A/z)+(-Z/z+Z/z) = D(A)/z + zn+1-zn+1/z = D(A)/z + (z-1)zn
kde (z-1)zn je nový MSB (the bit shifted in).

b) doleva: aby nenastalo overflow, musí platit (A << 1) >> 1 = A

Sčítání a odčítání

D(X+Y) = [D(X)+D(Y)] mod Z
D(X-Y) = [D(X)+D(-Y)] mod Z
overflow: ++ => - nebo -- => +

#### 2. (Signed magnitude representation)

 A >= 0 A <= 0 SM(A) A Z/2+|A|

0 and Z/2 represent both zero, -Z/2 < A < Z/2

The first bit is the sign:

 ± |A|

#### 3. (Biased representation)

Use: for exponent part of numbers in the floating point representation.
Def.: B(X) = X + K, usually K = M/2, thus B(X) = X + M/2
Range - nonsymetrical: -M/2 <= X < M/2

 X >= 0 X < 0 B(X) X+M/2 X+M/2 biased B(X) C(X)+M/2 C(X)-M/2 biased C(X) X X+M complement

- B(X) and C(X) differ only in the most significant bit (MSB).

B(X+Y) = (X+Y) + M/2 = B(X) + B(Y) - M/2
B(X-Y) = (X- Y) + M/2 = B(X) -  B(Y) + M/2

#### 4. Inverzní kód (Diminished radix complement representation)

 X >= 0 X <= 0 I(X) X M-e+X

e = epsilon = the smallest number different from 0 we can express in the representation (1 for integers).
This is also a complementory code, but the complement is taken w.r.t.Amax =  M-e (one's complement ...)
Range: -M/2 < X < M/2, ambigous representation of zero
Sign defined by the most significant digit

Shift to right: if the digits shifted in and out are equal then no loss of accuracy has occured.

Addition: 1) add both images 2) if carry, add e => I have to wait for all adders (if more than 1 bit input) to finish and if carry isn't zero, add e to the result (circular carry for z-2) => slower than in radix complement representation, the same holds for subtraction.

#### Poznámky

binary byte větší než 9 na BCD byte : přičti 6 (ekvivalentní odečtení 10).
Obraz A<0 v 2's complement: invert + přičti 1 (hot one), ignoruj carry.

## Error control codes

Codes:

• linear: sum (xor) of the code words is a code word.

• cyclic: the same as linear + logical rotation of a code word is a code word.

Channels: 1)symetrical (probability of error when 1 is changed to 0 is the same as for 0->1) x nonsym., 2) without x with memory (if an error occurs, it's likely that other errors follow = cluster of errors)
Notion:
d
- data/information vector (data/info bits). d = (d1,d2,...,dk)
p - check bits, redundancy; created from d [and p].p =(p1,...,pm)
c - encoded d sent over the channel and received on the other side, includes info bits + check bits
d' - info bits from decoding c (Decode(c) = d' + s)
s
-so called syndrome (vector), if it's zero vector => no error occurred (or so many errors that not discovered). |s|= |p| (equal sizes)
CW - code words, all c vectors that are not corrupted (i.e. after decoding, s = 0 and d'=d). |CW| = 2|d| (there is as many CW as the # of different data vectors)
NCW - non-code words, the set of all corrupted c vectors (Note: corrupted = changed code word may become either another CW or a NCW - see hamming distance ...)
|CW| + |NCW| = 2|c| where |c| is # bits in c vector. |c| is often called n.
Error correction: Algorithm: Replace the corrupted c from NCW by such code word from CW, which is the most close to c (replace a NCW by the nearest CW).
Codes: systematic (checkbits follow after data bits in c) x non-syst.(data&check bits are mixed in c)

#### Terms

nde - number of detectable errors
nce - # of correctable errors.
hd (Haming distance) - a) hd of 2 symbols b and b': hd(b,b') = # of different bits between them; b) hd of code = min hd(b1,b2) where b1 and b2 belong to CW.
For @-o-o-o-@ where @ are CW and o are NCW, hd is 4. If 1 error -> can be corrected, if 2 errors (the middle NCW) can't be corrected, for no CW is closer than the other, if 3 errors it seems to be only 1 error from the other CW.
w (word weight): w(b) = # of 1s in b. Note: hd(b,b') = w(b xor b')
Code naming: (S|D|T)E(D|C), where S=single, D=double, T=triple; E=error; D=detecting, C=correcting. The code with @-o-o-o-@ is SEC&DED, while @-o-o-@ is either SEC or DED, not both at once (because for SEC we think the double error is a single corruption of the other CW).
Code type is (n,k) where n = #bits of c, k = # data bits; m=n-k is # of check bits.

#### Formulas

nce <= nde always true
nde + nce < hd

#### Matrices

• generator matrix G is such matrix, that: c = d*G (used for encoding data).
G' = (E|B) is generator matrix for the systematic code; E is identity ("jednotková") matrix and B is a matrix. G' may be created from G according to Gauss' rules.
G (G') size is k*n. (Can be derived from d*G=c - |d|=k {#rows}, |c|=n {#columns}.)

• control matrix H is such matrix, that: s = H*cT (the order - H 1st - is important; it generates the syndrome).
H' = (BT|E) is control matrix for the systematic code (generated by G'). Note the order of B and E is switched and B is transposed here (w.r.t. G').
Iff G' may be created from G without operating on columns (i.e. operating on rows only), both H and H' may be used to check the code, for G and G' generate the same set of code words (though not always the same code word for the same data)
H (H') size is n*m. (Can be derived from H*cT = s - |cT|=n {#rows}, |s|=m {#check bits = #columns}.)

### Some error control codes

#### 1. Repetition code

is type (n,1). Def.: just repeat the single data bit n-1 times. To get TEC I need hda >=7 (see formulas).
Or TEC is @-o-o-o-o-o-o-@ (3 NCW belong to one CW) => hd = 7.

#### 2. Parity code

is (k+1,k) => 1 check bit only. Def.: check (parity) bit = a) even parity: xor of all data bits; b) odd parity: p1 = d1 xor ... xor dk xor 1.
Even parity - # of 1s in the resulting vector c is even. It's SED => error correction impossible (actually it discovers any odd # of errors).

#### 3. Cross parity code

 Type (8,4) d1 d2 p1 d3 d4 p2 p3 p4
 Type (9,4) d1 d2 p1 d3 d4 p2 p3 p4 p5
p1 = d1 + d2 etc.('+' is xor)
Type (8,4): hd=3 => it's SEC or DED
Type (9,4): hd=4 => it's SEC and DED

G' for (8,4) (d*G=c):
In the position (1,5) there is 1 iff the 1st bit of data vector d (d1) is included in the 5th bit of c (c5).

 c1 c2 c3 c4 c5 c6 c7 c8 d1 d2 d3 d4 p1 p2 p3 p4 G' = 1 0 0 0 1 0 1 0 d1 0 1 0 0 1 0 0 1 d2 0 0 1 0 0 1 1 0 d3 0 0 0 1 0 1 0 1 d4

#### 4. Haming codes

See matrices.
It holds:
H ...  if i-th bit of c is corrupted (s != 0), the binary number s is the number of the corrupted bit in c (starting at 1).
H' ... if i-th bit of c is corrupted, s should be equal to the i-th column of H'.

H (H'): # of linearly independent columns in the matrix = hd-1. (If hd=1 => matrix contains at least 2 identical columns).

a) type (7,3) is DED or SEC, hd = 3

 0 1 1 1 1 0 0 H = 1 0 1 1 0 1 0 1 1 0 1 0 0 1

? The order of columns can be changed; they're just all values of 3 bit number except of 000. ?

b) type (8,3) - extended Haming code - is DED&SEC, hd = 4
- add a parity for all 7 bits to (7,3) [G for (8,3) is the same as for (7,3), only we add a last column full of 1s].

For the normal Haming code of the type (n,k), it holds that n = 2m - 1 (s has m bits and must be able to determine the corrupted bit# in c, 0 is excluded [0=no error]).
For the extended Ham.code of the type (n,k), it holds that n = 2m-1 - 1 ( one more bit of s is used to distinguish between single and double error).

### Cyclic codes

- used if clusters of errors are expected (channel with memory); after an error, the probability of another error is higher.

We compute in Galois field GF(2n), i.e. with polynomials of the order < n and coefficients from {0,1} (modulo 2). We perform multiplication modulo in such a way, that xn = x0 (???). Note: such a polynomial may be represented as a vector containing 1s and 0s: x2+1 = 1x2+0x2+1 <=> (1,0,1)
Note: all computations are performed modulo 2 => when adding 1+1, there is no carry.

generator g(x) is such a polynomial from GF(2n), that all the other polynomials from it can be created as multiples of g(x) (using modulo). It holds, that g(x) divides xn+1 (there may be more generators). #of check bits = order of g(x).

d(x) = (dk-1,...,d0) -> [CODING] -> c(x) = (cn-1,...,c0)    for the code (n,k)

• encoding: c(x) = d(x)*g(x)  (modulo)
• decoding:
a) d(x) = c(x)*h(x)    where h(x) is such a polynomial that g(x)*h(x) = xn+1.
The multiplication is done modulo ( xn = x0) - for c(x)=1001110, h(x)=10111 (d(x) is 1010) [type (7,4)]:
 (1 0 0 1 1 1 0) * (1 0 1 1 1) 1 0 0 1 1 1 0 < + + + + / / / / / / / | | | | 0 0 1 1 1 0 1 < + + + / 0 1 1 1 0 1 0 < + + / 0 0 0 0 0 0 0 < + / 1 1 0 1 0 0 1 < / 0 0 0 0 0 0 0 syndrome s is 0

```?????????????????
(1001110)*(10111)
--------------
1001110 0000 /*1
+0000000 0000 /*0
+0010011 1000 /*1
+0001001 1100 /*1
+0000100 1110 /*1
--------------
1010000 1010
is
syndrome data
?????????????????```

b) d(x) = c(x) : g(x)     , dividend is data, remainder is syndrome

#### Circuit for multiplication:

For g(x) = x3 + x1 + 1 it is as follows (FF is a flip-flop):
d(x) is followed by the same # of 0s as the # of flip-flops (otherwise the last bits 3 would stay inside the circuits).

 c6...c0 <- xor < FF2 < -- < FF1 < xor < FF0 <- \ ^ ^ | \- - ---- - -- - ---- - + - ---- -- + -< d3...d0000 x3 x2 x1 x0