- 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
Z (1) plyne, že Amin = 0 a že Amax = zn+1 - z-m
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)
Čí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 -- => +
| 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.
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
| 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.
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.
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)
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.
nce <= nde always true
nde + nce < hd
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}.)
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.
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).
|
|
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 |
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).
- 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)
|
????????????????? (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
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