Reprezentace čísel, aritmetika

Polyadické číselné soustavy (radix number systems)

- dvojková, hexadecimální, desítková ...
číslo A je:
    A = SUM[-m,n](aizi)    (1)
(tj. i náleží (-m,n); číslice s i <=0 jsou za řadovou čárkou)
z - báze, základ (radix, basis)
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|

Disadvantages: complicated addition and subtraction.

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:

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

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)

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

Jakub Holý 2003 AD