Fundamentals of data representation

• Natural numbers are numbers that occur commonly and obviously in nature. As such, it is they are whole, non-negative numbers. The set of natural numbers, denoted N, can be defined in either of two ways:.

N=[0,1,2,3,...]
N=(1,2,3,...)

• Integer numbers are whole numbers. The set of integer numbers, denoted Z, can be defined in the following way:.

Z = { ..., -3, -2, -1, 0, 1, 2, 3, ... }

• Rational numbers are numbers that can be written as fractions. By default, all integers are rational numbers. A set of rational numbers can be expressed as:

Q = { 1/3, 3/4, 1/6, 0.5, -3, -2, -1, 0, 1, 2, 3, ... }

• Irrational numbers An irrational number is one that cannot be written as a fraction, for example √2. A set of rational numbers can be expressed as:

I = { √2, √3, Π}

• Real numbers are possible real world quantities. This includes both the rational and irrational numbers. A set of real number, denoted as R:

R = {√2, 1.23, 3.142, -3, -2, -1, 0, 111, 245.56, 3, ... }

• Ordinal numbers When objects are placed in order, ordinal numbers are used to tell their position.
• For example, the following set of ordered objects, 'a' is the 1st object, 'b' is the 2nd, so on and so forth.

S = {‘a’, ‘b’, ‘c’, ‘d’}

• Counting and measurement :
  • natural numbers are used for counting.
  • real numbers used for measurement.

• decimal numbers, or denary numbers also known as base 10 numbers. We use base 10, or decimal numbers in our daily lives. Base-10 number system has 10 digits to make up all numbers:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

1. Decimal numbers have place values of 10⁰, 10¹, 10², 10³, 10⁴, etc
2. Decimal numbers OR base 10 numbers are wrtten as:

Number₁₀, eg 67₁₀

• binary numbers are made of only two digits, 0 and 1.
  1. Binary numbers have place values of 2⁰, 2¹, 2², 2³, 2⁴, etc
  2. Binary numbers or base 2 numbers can be written as:

Number₂, eg 1001₂

• hexadecimal numbers are base 16 numbers. Hexadecimal number system has 16 symbols:

  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
  

  • the notation of hexadecimal

    Several different notations are used to represent hexadecimal in computing. The prefix "0x" is widespread due to its use in Unix and C, some denote hexadecimal values using a suffix or subscript. For example, user prefix: 0x2AF3 or use subscript 2AF3₁₆.

  • the purpose of hexadecimal
    1. In computing, it is very inconvenient to write or read a long string of 1s and 0s. Hexadecimal is used to "compress" binary bit patterns. Each hex digit represents 4 binary bits (or a nibble).
    2. Hex is commonly used in computer memory addresses.
    3. Binary numbers are difficult for programmers to work with.
    4. If we're building a web-page, then chances are we're going to want to use colour.
    5. In general computers use the RGB colour model, where any colour we need is made up by additive mixing Red, Green and Blue.
    6. The value of RGB colours ranges from 0,0,0 up to 255,255,255.

Here's a colour that is represented as R-159, G-028, B-173.

• Counting in Binary starts with 0, then 1. Since there are only '0' and '1' to be used, when counting the next number (decimal 2), we need to move the place value to the left and use '1' to indicate that the 2's place is used. Usig this method, counting in binary from 0 to 8 is like so:

0, 1, 10, 11, 100, 101, 110, 111, 1000

• Have a look at this page on counting in binary and hex

1. To convert binary to decimal:

        Using binary number 1011 as an example:
   Step 1: write the place values of each bit
    place value          8     4     2    1
    binary number        1     0     1    1
   
   Step 2: if there is a '0' bit under the place value, make it 0, else, write down the place value
    place value           8     4     2    1
    binary number:        1     0     1    1
                          8     0     2    1
   
   Step 3: add all the place values with a bit '1' (on bit) together and you will get the decimal value for the binary number
                          8     4     2    1
                          1     0     1    1
                          8         + 2  + 1 = 11
   
   Therefore, binary 1011 is decimal number 11.
   

2. To convert decimal to binary:

   Using decimal number 27 as an example:
   Step 1:  find the highest place value in the decimal number 27. In this case, it is 16.
    Because the next place value will be 32 which is too large for 27. Place a '1' bit under 16.
    place value          32    16    8    4    2    1
    binary number              1     
   
   Step 2: subtract 16 from 27, now we have 11. Repeat the last step on the remaining decimal number 11
    place value:         32    16    8    4    2    1
    binary number:             1     1
   
   Step 3: repeat step 2, now we have the remaining 3 left. The next place value 4 is too big, so will not be used. 
   We place a bit '0' underneath it.
    place value:         32    16    8    4    2    1
    binary number:             1     1    0
   
   Step 4: Since there is a 2 and 1 in the remaining 3, we place a bit '1' underneath them
    place value:         32    16    8    4    2    1
    binary number:             1     1    0    1    1
   
   Therefore, the decimal number 27 is decimal number 11011.
   

3. To convert a binary bit pattern into hex:

   example 1: Binary bit pattern: 10011110
   Group the bits in 4
   starting from the LSB (least significant bit, the rightmost bit): 
   There are exactly 2 groups of 4-bits
       binary: 1001 1110
       hex:     9    E
   Therefore, the binary pattern 10011110 can be written in hex as 9E.
   
   example 2: Binary bit pattern: 1001111.
   There are 7 bits.
   In this case, you group the bits in 4
   starting from the LSB (least significant bit, the rightmost bit)
   You pad the remaining 3-bits with a leading 0:
         binary: 0100 1111
         hex:     4    F 
   Therefore, the binary pattern 1001111 can be written in hex as 4F
   

4. to convert hex to decimal:

   example 1: Hex number: C4
   Work out the place values for each hex character.
        The C is at the 16^1 and the 4 is at the 16^0
   Work out the C hex character's decimal value, which is 12
   Work out the 4 hex character's decimal value, which is 4
   
         12x16^1 + 4x16^0 = 196
   
   Therefore, the hex number C4 in decimal is 196.
   
   example 2: Hex number: F16
   Work out the place values for each hex character.
        The F is at the 16^2,1 at 16^1 and 6 at the 16^0
   Work out the F hex character's decimal value, which is 15
   Work out the 1 hex character's decimal value, which is 1
   Work out the 6 hex character's decimal value, which is 6
   
         15x16^2 + 1x16^1 + 6x16^0 = 3862
   
   Therefore, the hex number F16 in decimal is 3862
   

5. You can confirm the above example's correctness by convert each hex number into binary, then to decimal.

   Example 1: hex number C4
   
    4 in binary: 0100
    C in binary: 1100
    The binary number for hex 4C therefore is: 100 1100
   
       1  1  0  0  0 1  0  0
      128 64 32 16 8 4  2  1     = 128+64+4=196
   

• a bit is either 0 OR 1.
  1. Binary numbers are made of 0s and 1s
  2. A byte is a group 8 bits
  3. n bits can make 2ⁿ different binary values. For example, using 3 bits, we can make 2³=8 different binary values:

000, 001, 010, 011, 100, 101, 110, 111

• A nibble is a group of 4 bits.
• A byte (a group 8 bits) is a unit of storage in a computer which contains 8-bits and can store 256 different values: 0 to 255. Letters are usually stored in a byte for example.
• A kilobyte is 1000(10³) bytes. But a kibibyte is 1024(2¹⁰) bytes.kibi is the ki lo in bi nary.Since computers store and measure things in binary, to differentiate the base 10 and base 2 units, here is a table of those unit's names:

Kilobytes (KB)	1000	Kibibyte (KiB)	1024
Megabyte (MB)	10002	Mebibyte (MiB)	10242
Gigabyte (GB)	10003	Gibibyte (GiB)	10243
Terabyte (TB)	10004	Tebibyte (TiB)	10244
Petabyte (PB)	10005	Pebibyte (PiB)	10245
… … … …

• Unsigned binary numbers do not have a bit to indicate they are positive or negative numbers. If you have a 8-bit unsigned binary number, the maximum value can be is 255 and there are 256 (2⁸) different values.
• Singned binary numbers use one bit to indicate positive (+) or negative (-). In this case, if you have a 8-bit signed binary number,

the maximum value can be is 127 and there are 128 (2⁷) different values. In signed binary numbers, the left most(the most significant bit AKA msb) is used to indicate positive (0) or negative(1).

1. a 8-bit positive binary number: 01010011
2. a 8-bit negative binary number: 11010011

• Add two unsigned binary integers

While adding binary numbers together, you need to remember that:

1. 0+0=0
2. 0+1=1
3. 1+1=10 –— the 1 in "10" is being carried over to the 2's place
4. 1+1+1=10+1=11

Now, lets apply the above knowledge to some examples:

example 1:                                  example 2:

       1010                                     1010              
      +0010                                    +1111
        1 <-- the carry over bit                 1 <--- the carry over bit 
   --------                                     1 <--- the carry over bit
       1100                                 -----------
                                                11000

• multiply two unsigned binary integers

When multiply binary number, it works the same way as decimal numbers, you need to remember:

1. 0*0=0
2. 1*1=1
3. 0*1=0
4. You should end up with the total number of bits of the two unsigned binary integers.

example 1:                                  example 2:

       11                                     1010              
      x10                                     x101
   -------                                ----------
       00                                     1010
      11                                     0000    
      110 <-- the product                   1010
                                            110010 <--- the product

• In 2's complement, the msb is used for sign (0 for positive AND 1 for negative).
• The remaining n-1 bit is used for the absolute number value (magnitude). Therefore, the maximum magnitude of a n-bit pattern can have is 2^n-1.
• The range of values will be between -2^n-1 and 2^n-1-1

1. Work out the sign bit If the decimal number is positive, the msb is 0 If the decimal number is negative, the msb is 1
2. Work out the magnitude of the decimal number in binary
   1. If the decimal number is negative, invert the bit pattern from step 2 and add 1
   2. If the decimal number is positive, move to step 3
3. Place the sign bit (0 or 1) at the leftmost position of the bit pattern from step 2

For example, to convert -7 into a 8-bit binary in 2's compliment

Step 1: negative number → sign bit (msb) is 1 

Step 2: decimal 7 in binary → 000 0111

Step 3: Invert the bits: 000 0111 ⇒ 111 1000

Step 4: Add 1 to the inverted bits: 111 1000 + 1 = 111 1001

Step 3 and step 4 can be also replaced by finding the first '1' bit
 from the bit pattern result from step 2 
 and simply flip all the bits to its left.

Step 5: Place the sign bit at the msb position to make the resulting 8-bit 1111 1001

1. Check the sign bit If the sign bit is 0, the number is positive and its absolute value is the binary value of the remaining n-1 bits. Stop here. If the sign bit is 1, the number is negative, and proceed to step 2.
2. Invert the remaining bits and plus 1 to get the absolute value (magnitude) of the negative number.

For example,
8-bit pattern: 1 100 0100
Sign bit is 1 → negative (-)

Invert the remaining bits: 100 0100⇒ 011 1011

Add 1 to the inverted bits: 011 1011 + 1 = 011 1100 which in decimal is 60

Hence, 8-bit 1100 0100 in 2's compliment has the decimal value of -60

Step 2 can also be done by checking the remaining bits from the right
 (least-significant bit AKA lsb). Look for the first occurrence of 1.
 Flip all the bits to the left of that first occurrence of 1.
 The flipped pattern gives the absolute value.

1. When perfroming decimal subtraction, for example, 12-9, you practically perform addition 12+(-9)
2. The same principle applies to binary numbers — so change the second binary to negative first, then just perform addition .

For example, subtracting 1(0001) from 7(0111) using 2's complement with 4-bit pattern.

Step 1: convert 0001 to its negative equivalent in 2's complement.
       1) invert the bits -> 1110
       2) add 1           -> 1111   <- note the msb is 1

Step 2: perform the additon:  0111 + 1111 = 10110

Step 3: Since the result has 5 bits, which is one bit more than the original 4 bits,
        the addition has caused overflow.
 Wherever there is an overflow bit in 2's complement,
 discard that extra bit. 
 The result 0110 is the answer.

1. Now we know we can represent any integers (positive or negative) using binary numbers. However, to represent fractions or numbers with decimal points in computers, it is not so easy.
2. First, lets examine fractions in decimal numbers. For example, 52.64 can be written 50 + 2 + 0.6 + 0.04, or in their corresponding place:

   place	10s	1s	.	1/10	1/100
   	5	2	.	6	4

3. Similarly, in binary (base two) notation, the fraction 4.625 can be represented in the following way: 100.101

   place	4s	2s	1s	.	1/2	1/4	1/8
   	1	0	0	.	1	0	1

   The binary 100 is decimal 4, while the .101 uses fractions of (1/2)ⁿ to proximately make the remaining although in this case, 0.625 can be made of (1/2)¹ + (1/2)³ exactly.

   Now lets check if we can convert the following numbers from decimal to binary:

   Example 1: convert 3.14 to binary
          1) convert 3 into binary -> 11
          2) convert .14 into binary:
              1/2 = 0.5, large than 0.14, not use ->0
              1/4 = 0.25, still large than 0.14, not use ->0
              1/8 = 0.125, smaller than 0.14, use ->1,  0.14-0.125=0.015 remaining
              1/16 = 0.0625, large than 0.015, not use ->0
              1/32 = 0.03125, too large, not use ->0
              1/64 = 0.015625, too large but it is close enough, use ->1
           The result for 0.14 in binry is approximately: .001001
    Therefore, 3.14 in decimal to binary is 11.001001
   

4. Fraction numbers can be represented in binary using a fixed number of bits with fixed number of bits for the values before and after the point.

   For example, using 8-bits, one can dedicate the first 4 bits for the number before the point and the remaining 4 bits for the number after the point.

   • to convert a decimal number 9.25 to a 8-bit unsigned binary with the above fixed point system:

     Example : convert 7.25 to binary using 8-bits fixed point
            1) convert 7 into binary in 4-bits -> 0111
            2) convert .25 into binary:
                1/2 = 0.5, large than 0.25, not use ->0
                1/4 = 0.25, just right use ->1
     
          Therefore, 7.25 in decimal to 8-bits binary is 0111 0100
     

• ASCII: American Standard Code for Information Interchange. It is the standard code for representing the characters on the keyboard. ASCII uses 7 bits which form 128 different bit combination, more than enough to cover all of the characters on a standard English-anguage keyboard. See this link for the complete ASCII code table.

"Originally based on the English alphabet, ASCII encodes 128 specified characters into seven-bit binary integers as shown by the ASCII chart on the right.The characters encoded are numbers 0 to 9, lowercase letters a to z, uppercase letters A to Z, basic punctuation symbols, control codes that originated with Teletype machines, and a space. For example, lowercase j would become binary 1101010 and decimal 106. ASCII includes definitions for 128 characters: 33 are non-printing control characters (many now obsolete)that affect how text and space are processedand 95 printable characters, including the space." – from wikipedia

• The ASCII has been used for a long time. But it has some serious shortcomings:
  1. It only uses English alphabets
  2. It is limited to 7-bits, so it can only represent 128 distinct characters.
  3. It is not usable for non-latin languages, such as Chinese
• Character form of a decimal digit In ASCII, the number character is not the same as the actual number value. For example, the ASCII value 011 0100 will print the character '4', the binary value is actually equal to the decimal number 52. Therefore ASCII cannot be used for arithmetic.
• ASCII code has been extended to use 8 bits during the 1980s to include an additional 128 combinations to represent more symbols.
• Unicode (Unique, Universal, and Uniform character enCoding) has been introduced to address the shortcomings with ASCII. The latest version of Unicode contains a repertoire of more than 120,000 characters covering 129 modern and historic scripts, as well as multiple symbol sets. ASCII character encoding is a subset of Unicode.
  1. Unicode has three main encoding forms, UTF-8, UTF-16 and UTF-32.
  2. UTF (Unicode transformation format) is an algorithmic mapping from every Unicode code character called point to a unique byte sequence.
  3. Depending on the encoding form you choose (UTF-8, UTF-16, or UTF-32), each character will then be represented either as a sequence of one to four 8-bits (bytes), one or two 16-bit code units, or a single 32-bit code unit.For example, in UTF-16, 2 bytes (16 bits) combinations are used to code each character.
  4. UTF-8 is the dominant character encoding for the World Wide Web, accounting for 84.6% of all Web pages in August 2015 .
  5. While there is one global standard, this means one character in unicode scheme could use up to 4 bytes, significantly increasing file sizes and data transmission time.

During transmission, digital signals suffer from noise that can introduce errors in the binary bits travelling from one system to other. That means a 0 bit may change to 1 or a 1 bit may change to 0.

• Parity bit is the simplest technique used to check the accuracy of data transimission. In this scheme, the MSB(most significant bit) of an 8-bits word is used as the parity bit and the remaining 7 bits are used as data or message bits. The parity of 8-bits transmitted word can be either even parity or odd parity. Between two parties start data transmission, they MUST agree on using even or odd parity.

1. For even parity, the parity bit is set to 1 or 0 such that the number of "1 bits" in the entire word is even.
2. For odd parity, the parity bit is set to 1 or 0 such that the number of "1 bits" in the entire word is odd.
3. Parity checking at the receiver can detect the presence of an error if the parity of the receiver signal is different from the expected parity. That means, if it is known that the parity of the transmitted signal is always going to be "even" and if the received signal has an odd parity, then the receiver can conclude that the received signal is not correct. If an error is detected, then the receiver will ignore the received byte and request for retransmission of the same byte to the transmitter.

• Majority voting is another technique used to detect error. I this scheme, each bit is transmitted three times (redundancy) in the hope that majority of the bits in each repetition will be correct.

  For example, we want to transmit 8-bits of data, for every bit, we send it three times. At the recieving end, the following bits are seen:

  100 110 001 000 101 010 001 111

  By using majority voting, the first bit is 0, the second is 1, so on and so forth. So the recieving end concludes that the correct data is: 01001001.

• Check sum is a mathmatical algorithm that is applied to a sequence of data to create a checksum value which is transmitted with the data. The same algorithm is applied to the data at the recieving end. If the two checksums match, the data transmission has been successful; if not, an error must have occurred and a re-transmission is requested.

  A simple checksum algorithm could be like so:

  1. the data is being divided into 4-bits groups.
  2. the sum of each group's numerical values is the checksum.
  3. if any bits change occurred during transmission, then it is likely, but not guaranteed to change the checksum.

  

• Check digit is another scheme designed to check for errors in data input or transmission. It uses an extra digit at the end of a sequence of data. The numbers printed normally above or just below the bar codes you see on product packages and books use this scheme.

  UPC (Universal Product Code) example:

ISBN (International Standard Book Number) 13 example:

• An image is made up of tiny dots called pixels.
• A pixel is the smallest element can be drawn on screen.
• The more pixels on the screen, the higher the resolution and the better the quality of the picture will be. Resolution of an image is expressed directly as width of image in pixels by height of image in pixels using notation width x height. Alternatively, resolution can be expressed in number of dots per inch where a dot is a pixel.
• The smaller the pixels the finer the detail that can be displayed on the screen.
• Each pixel is represented by the same number of bits. The number of bits used for each pixel is called colour depth. A 1 bit colour depth can only represent 2 colours. For example, a black and white image can use 0 for black and 1 for white.
• The more bits used in each pixel (higher colour depth), the more colours can be represented (richer colours), the more storage is required.
• Graphics can be classed as either: Bitmapped graphics (painting) Vector graphics (drawing).
  • Bitmapped Graphics are stored in a two dimensional array using binary numbers to represent the colours in the pixels.
    • Some examples of bitmap: png, gif, jpg
    • bitmap image files may contain metadata to describe their height, width and colour depth.
    • by using the metadata in a bitmap, we can calculate:
      1. the size of the image:

         height (number of pixels) x width (number of pixels) x colour depth(number of bits per pixel)

      2. the resolution of the image:

         height (number of pixels) x width (number of pixels)

  • Vector gaphics use coordinates and geometry to precisely define the parts of the image using mathmatic formula. It is more efficient than bitmaps at storing large areas of the same colour because it does not need to store every pixel as a bitmap does.
    1. drawing is made up of drawing objects(circle, rectangle etc).
    2. Objects are stored as drawing commands or drawing list. An example drawing list for a circle would include: centre coordinate, radius, line thickness, line colour, fill or not.
    3. different objects have a defined set of properties.
    4. some properties use mathematical equations or formulae.

       Some examples of vector: SVG

• Regardless of bitmap or vector graphics, all images are converted (rasterised ) and displayed in pixels.

• Advantages of vector graphics
  • (For geometric images) less storage space/memory likely to be needed;
  • (For geometric images) will load faster from secondary storage;
  • (For geometric images) will download faster;
  • Can be scaled/resized without distortion;
  • Image can be more easily searched for particular objects;
  • Can easily manipulate individual objects in an image;
• Disadvantages of vector graphics
  • Only appropriate for images made of geometric shapes;
  • Unsuitable if colour of each pixel is likely to vary such as a digital photograph;
  • Some drawing tools are unlikely to be be available when using vector graphics (eg spray paint, blurring);
  • for complex images, can take longer to render an image;

1. Analogue and Digital data
   • Analogue data have continous values with infinite possible values in between. Sound waves are analogue data (sinewave like).
   • Digital data have discrete and finite set of values.
   • To store sound in computers, it must be converted into digital data first.
2. Convert analogue data into digital data
   • Analogue to digital conversion (ADC) happens when we record sound to be used on a computer. This is accomplished normally by a ADC converter.
   • The number of bits used to represent a value/amplitude, or one sample in analogue data is called sample resolution. The more bits used (higher sample resolution), the wider range of values can be represented.
   • Another factor affecting the quality of ADC is the sampling rate or frequency - the number of samples taken per second, expressed as Hz.
   • The Nyquist Theorem, also known as the sampling theorem, is a principle that engineers follow in the digitisation of analog signals. It states that sample rate should be at a frequency which is at least twice the value of the highest frequency in the sampled signal.

     Take a look at this site for more info on Nyquist Theorem.

   • Bit rate - the number of bits required to store 1 second of sound
   • To calculate a resulting digital file size:

     file size (in bits) = sampling rate x sample resolution x length of sound
     
     OR
     
     file size (in bits) = bit rate x length of sound
     

3. Convert digital to analogue
   • Digital to analogue conversion (DAC) happens when digital sound files(such as CD, mp3 files) are played back as sound waves to be heard. The analogue wave produced may differ significantly from the original sound wave due to the fact that conversion has to best "guess" the fit of a continous wave over a finite set of values (by interpolation algorithms).
4. Musical Instrument Digital Interface (MIDI)

   " MIDI is a technical standard that describes a protocol, digital interface and connectors and allows a wide variety of electronic musical instruments, computers and other related devices to connect and communicate with one another. __wikipedia"

   • MIDI basics MIDI is a communication standard developed in the early 1980s for electronic musical instruments and computers.

     Since MIDI is a communication protocol, it uses a standard collection of messages to communicate. See this for a list of MIDI messages.

     Unlike digital audio files (.wav, .aiff, etc.) or CDs, a MIDI file does not need to capture and store actual sounds. Instead, the MIDI file can be just a list of events which describe the specific steps that a soundcard or other playback device must take to generate ceratin sounds.

   • MIDI audio files MIDI files is a list of time-stamped MIDI event messages that are recordings of musical actions in sequence. MIDI event messages contain MIDI instructions for notes, volumes, sounds, and even effects. MIDI files tend to be significantly smaller than equivalent digitised waveform files. All popular computer platforms can play MIDI files (*.mid).

     Advantages of MIDI files:

     1. MIDI files are much more compact than digital audio files.
     2. MIDI files embedded in web pages load and play more quickly than their digital equivalent.
     3. MIDI data is completely editable. A particular instrument can be removed from the song and/or a particular instrument can be changed by another just by selecting it.
     4. MIDI files may sound better than digital audio files if the MIDI sound source you are using his of high quality.