 dvojková, hexadecimální, desítková ...
číslo A je:
A = SUM[m,n](a_{i}z^{i})
(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) = z^{n+1} (modulus)
epsilon = z^{m}_{ }jednotka (unit), nejmenší
reprezentovatelná jednotka, viz LSB
Z (1) plyne, že A_{min} = 0 a že A_{max} = z^{n+1}  z^{m}
Z ("M" v angličtině) = A_{max}+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 = A_{max
}neb a_{i}=a_{max}a_{i}).
[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 + z^{n+1}z^{n+1}/z
= D(A)/z + (z1)z^{n}
kde (z1)z^{n} 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(XY) = [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(XY) = (X Y) + M/2 = B(X)  B(Y) + M/2
X >= 0  X <= 0  
I(X)  X  Me+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.A_{max}
= Me (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 z2) => 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 = (d_{1},d_{2},...,d_{k})
p  check bits, redundancy; created from d [and p].p
=(p_{1},...,p_{m})
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  noncode 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
nonsyst.(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 @ooo@ 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: (SDT)E(DC), where S=single, D=double, T=triple; E=error;
D=detecting, C=correcting. The code with @ooo@ is SEC&DED, while @oo@
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=nk 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' = (EB) 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*c^{T} (the order  H 1^{st}  is
important; it generates the syndrome).
H' = (B^{T}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*c^{T }= s  c^{T}=n
{#rows}, s=m {#check bits = #columns}.)
is type (n,1). Def.: just repeat the single data bit n1 times.
To get TEC I need hda >=7 (see formulas).
Or TEC is @oooooo@ (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: p_{1} = d_{1}
xor ... xor d_{k} 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).


p_{1} = d_{1} + d_{2}
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 1^{st} bit of data vector d
(d_{1}) is included in the 5^{th} bit of c (c_{5}).
c_{1}  c_{2}  c_{3}  c_{4}  c_{5}  c_{6}  c_{7}  c_{8}  
d_{1}  d_{2}  d_{3}  d_{4}  p_{1}  p_{2}  p_{3}  p_{4}  
G' = 
1  0  0  0  1  0  1  0  d_{1} 
0  1  0  0  1  0  0  1  d_{2}  
0  0  1  0  0  1  1  0  d_{3}  
0  0  0  1  0  1  0  1  d_{4} 
See matrices.
It holds:
H ... if ith 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 ith bit of c
is corrupted, s should be equal to the ith column of H'.
H (H'): # of linearly independent columns in the matrix = hd1. (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 = 2^{m}
 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 = 2^{m1}
 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(2^{n}), i.e. with polynomials of the
order < n and coefficients from {0,1} (modulo 2). We perform multiplication
modulo in such a way, that x^{n} = x^{0} (???). Note: such a
polynomial may be represented as a vector containing 1s and 0s: x^{2}+1
= 1x^{2}+0x^{2}+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(2^{n}), that all the other polynomials from it can be created as multiples of g(x) (using modulo). It holds, that g(x) divides x^{n}+1 (there may be more generators). #of check bits = order of g(x).
d(x) = (d_{k1},...,d_{0}) > [CODING] > c(x) = (c_{n1},...,c_{0}) 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) = x^{3} + x^{1} + 1 it is as follows (FF is a
flipflop):
d(x) is followed by the same # of 0s as the # of flipflops (otherwise the last
bits 3 would stay inside the circuits).
c_{6}...c_{0}  <  xor  <  FF2  <    <  FF1  <  xor  <  FF0  <  \  
^ 
^ 
 

\ 
 
 
 
 
 
 
 
+ 
 
 
 
+  < d_{3}...d_{0}000  
x^{3} 
x^{2}  x^{1}  x^{0} 
Jakub Holý 2003 AD