Please enable JavaScript.

Coggle requires JavaScript to display documents.

02 Data Representation (2.0 OBJECTIVES (numerical data representation and…

- - - - 2--10 & 8--10 & 16--10
      - 2--8 & 2--16
      - 10--2 & 8--2 & 16-2
      - 8--16 & 16--8
- - - - disadvantage
        
        运算加减法时，超出 7 words 的取值范围会出现问题
        
        requires complicated computer hardware
        
        allows 2 zeros
      - advantage
        
        easy to understand
      - 取值范围： -(2^(n-1)-1) ~ (2^(n-1)-1)
    - - binary
        
        two's complement
        
        addition
        
        discard any carries 丢弃超出取值范围的数(overflow)
        
        rules for detecting overflow
        
        carry in != carry out of the sign bit , overflow
        
        carry in = carry out, no overflow
        
        positive number
        
        = signed magnitude
        
        negative number
        
        = one's complement + 1
        
        advantage
        
        only one zero
        
        easy to detect overflow error
        
        one's complement
        
        advantages
        
        able to eliminate the need for subtraction
        
        simpler to implement than signed magnitude
        
        addition
        
        carry bit is carried around and added to the sum 超出取值的数可以直接加到结果中(overflow)
        
        disadvantages
        
        allows 2 zeros
        
        negative
        
        flipping 被反转所有的bits(base-2)
        
        start with 1
        
        positve
        
        start with 0, =signed magnitude
      - in different radix system, the complements are different
      - maximum possible value 减去 the number provided = (r-1)'s complement
      - (r)'s complement = (r-1)'s complement +1
  - - - 溢出word总长
      - for unsigned word
    - - for signed word
      - 溢出到high-order bit
  - - - 所有的1左移一位， signed number不变
    - - 所有1右移一位，signed number 不变
- - - - scientific notation
  - - - sign
        
        1 bit
        
        +0
        
        -1
      - exponent
        
        5 bits
        
        0~31(32 possible)
        
        二进制
        
        exponent + bias
        
        why bias(偏差值）
        
        to express values <1 such as 0.5 (=2^(-1))
        
        no sign in the exponent field
        
        definition: midway in the range of values
        
        negative- small number 00001
        
        positive- large number 11110
        
        bias 16
        
        excess-16 representation
      - signidand
        
        8 bits
        
        normalization
        
        rule: first digit must be 1(implied bits)
        
        e.g. 0.125 #
        
        in this model, we use no implied/hidden bits.
        
        二进制
      - 有正负的0
        
        sign bit can be either 0 or 1
        
        programmers should avoid testing a floating-point value for equality to zero
    - - binary 32-bit
        
        a single-precision floating-point standard
        
        8-bit exponent
        
        23-bit significand
        
        an implied/hidden 1 to the LEFT of the radix point
        
        e.g. 1.xxx...
        
        why: 大家都知道那里一定有个1，可以节省出一位的空间
        
        bias of 127
        
        exponent 255
        
        significand is 0, +-infinity
        
        significan is nonzero, NaN
        
        flag an error
      - binary 64-bit
        
        a double-precision floating-point standard
        
        11-bit exponent
        
        bias of 1023
        
        52-bit significand
        
        an implied/hidden 1 to the LEFT of the radix point
        
        e.g. 1.xxx...
        
        special exponent 2047 #
      - 有正负的0 #
  - - - sign
      - exponent
      - significand/mantissa
      - why this model better than complement
        
        negative complement looks very big
        
        the absolute value of the complement is not clear
    - - fix
        
        similar in magnitude相似的值先进行计算 p84
        
        增加model 的 bits
      - low-order bit error
      - high-order bit error
        
        more problematic
    - - don't use: if x = 2 then ...
      - better use: if (abs(x -2) < epsilon) then ...
  - - - add the numbers
      - preserving the exponent in the sum
      - do exponent adjustment if we need, for nomalization or there is carry out in significand
      - use 14-bits model
      - convert decimal to binary
      - express both operands in the same exponential power
    - - multiply the two operands and add their exponents.
      - do exponent adjustment if we need, for nomalization or there is carry out in significand
      - use 14-bits model
      - convert decimal to binary
    - - 因为 truncated bits
      - 不一定成立 (a + b) + c = a + (b + c) & a*(b + c) = ab + ac
- - - - are polynomials over the modulo 2
        
        modulo 2 division
        
        not used in modern computer
        
        for CRC detection, may not = decimal devision
        
        for education purpose
        
        works like clock arithmetic
      - Cyclic redundancy checking
      - for large blocks of data
    - - last characters of UPC barcodes and ISBNs are check digits.
      - appended to the end of a long number
      - a form of redundancy check
    - - bits that append to the end of the number
  - - - only copy in memory or on disk
      - hamming codes
        
        mathematics much simpler than Reed-Solomon
        
        is adding redundant check bits, or parity bits, to a data word
        
        hamming distance
        
        minimum distance
        
        smallest Hamming distance between all pairs of words in the code
        
        determines its error detecting and error correcting capability
        
        D(min)
        
        to detect k(or fewer) single-bit errors, the code must have a Hamming distance of D(min) = k+ 1.
        
        definition
        
        the number of bits in which two code words differ
        
        provided by adding a suitable number of parity bits to a data word
        
        hamming algorithm
        
        correct & detect
        
        correct （（D（min）-1）/2）errors
        
        correct k errors when distance = 2k+1 in any data words
        
        detect D(min) -1 errors
        
        finding check bits
        
        (m+r+1)<=2^r
        
        m= valid word length
        
        r= number of check bits/redundant bits/parity bits
        
        r= 总是取最小值
        
        m+r=n= total length
        
        to build a code with 8-bit data words that will correct single-bit errors, we must add 4 check bits, creating code words of length 12 #
        
        (8+r+1<=2^r) r=4
        
        detect and correct error
        
        具体题目看assignment 1的习题
      - Reed-Solomon codes
        
        particularly useful in correcting burst errors
        
        CD-ROMs
- - - - 6 bits
        
        IBM 1950s-1960s
        
        Binary- coded decimal(BCD)
      - 8 bits
        
        Extended Binary-Coded Decimal Interchange Code (EBCDIC).
        
        include: 大写，小写，标点符号，控制符
      - based upon punched card codes
      - 现在仍然在IBM 的框架下使用
    - - ASCII (American Standard Code for Information Interchange)
      - based upon telecommunications (Telex) codes #
      - dominant character code outside the IBM mainframe world.
    - - Unicode
      - encode the characters of every language in the world
      - Java, some operating systems use Unicode
      - codespace is divided into six parts
        
        Alphabets
        
        Symbols
        
        CJK
        
        Han
        
        User Defined
        
        owest-numbered Unicode characters comprise the ASCII code.
        
        highest provide for user-defined code