Representation of data.md (1515B)
1 +++ 2 title = 'Representation of data' 3 +++ 4 # Representation of data 5 ## Representing data 6 Binary circuits in computers 7 8 Unit of information: bit (binary digit) — 0 or 1 (data values or boolean) 9 10 Bit strings: multiple bits together, which can be given a specific meaning (such as natural numbers) 11 12 ## Computing — boolean algebra 13 we want a computer that can calculate (expression string → result string(s)) 14 15 operations: 16 17 - x.y (or x ^ y) — “AND", class of objects with both properties 18 - x.x— no further information 19 - x*x = x² = x 20 - 0.x = 0 (annihilator) 21 - 1.x = x (identity) 22 - x+y (or x v y) — “OR”, merges independent objects 23 - x+x — no further information 24 - x+x = x 25 - 0+x = x (identity) 26 - 1+x = 1 (annihilator) 27 28 complements: 29 30 - if x, then complement is 1-x 31 - x(1-x) = x-x² = x-x = 0 32 - 1-x = x̄ 33 34 therefore, any function ƒ(x) can be written as ƒ(x) = a ⋅ x + b ⋅ (1-x) 35 36 can it really? let’s try one: 37 38 ``` 39 ƒ(x) = a₀ + a₁x 40 let b = a₀, a = a₀ + a₁ 41 ∴ ƒ(x) = a ⋅ x + b ⋅ (1-x) 42 ƒ(1) = a 43 ƒ(0) = b 44 ƒ(x) = ƒ(1) ⋅ x + ƒ(0) ⋅ x̄ 45 ``` 46 47 ## Truth tables 48 Binary addition — XOR 49 50 x ⨁ y = x ⋅ ȳ + y ⋅ x̄ 51 52 | x | y | ⨁<br>(carry result) | 53 | --- | --- | --- | 54 | 0 | 0 | 0 0 | 55 | 0 | 1 | 0 1 | 56 | 1 | 0 | 0 1 | 57 | 1 | 1 | 1 0 | 58 59 Binary multiplication — AND 60 61 x ⨂ y = x ⋅ y 62 63 | x | y | ⨂<br>(carry result) | 64 | --- | --- | --- | 65 | 0 | 0 | 0 | 66 | 0 | 1 | 0 1 | 67 | 1 | 0 | 0 1 | 68 | 1 | 1 | 1 0 |