Representation - mandyHoneyman/CIE_ALevel_CS GitHub Wiki

=Number Representation=

=The denary number system (decimal, base 10)=

• From right to left: units, tens, hundreds, thousands, etc.
• Mathematically these values are expressed like this: 10^0, 10^1, 10^2, 10^3
• Ex 1: 35 = (310^1) + (510^0)
• Ex 2: (310^4) + (510^3) + (210^2) + (010^1) + (9*10^0)

Decimal digits: 0 1 2 3 4 5 6 7 8 9

=Binary number system (base 2)=

• Digital logic and computer systems use just two values or states to represent a condition, a logic level “1” or a logic level “0”
• In binary system, digits are called 'bits'
• Example of a binary number: 10111101

Binary digits: 0 1

=Converting a binary to denary= Example 1: 101 = (12^2) + (02^1) + (1*2^0) = 4 + 0 + 1 = 5

A different way: ||= 2^2 ||= 2^1 ||= 2^0 || ||= 1 ||= 0 ||= 1 ||

Example 2: convert 1001 to denary.

=Converting a decimal number to binary= Ex: convert 14 to binary Number: 14 14/2 = 7 remainder 0 7/2 = 3 remainder 1 3/2 = 1 remainder 1 1/2 = 0 remainder 1 //14 in binary: 1110//

=Hexadecimal number system (base 16)= Humans are not very good at remembering long strings of numbers so, to make it easier for us, we can represent every group of 4 bits with a single digit.

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

Exercise: @http://cse4k12.org/hexadecimal/counting_in_hex.pdf

=Convert hexadecimal to denary=

Example 1: convert 3B in base 16 to denary.

3B = 316^1 + 1116^0 = 48 + 11 = 59

Example 2: Convert 3E8 to denary

=Convert denary to hexadecimal=

Example: convert 500 in base 10 to hexadecimal

Number: 500 500/16 = 31 remainder 4 31/16 = 1 remainder 15 1/16 = 0 remainder 1 Result: 1(15)4 = 1F4

=Convert binary to hexadecimal= Example: Convert the binary number 101010111100010 to hexadecimal

101010111100010 => 55E2 == == To check the result use http://www.binaryhexconverter.com/binary-to-hex-converterconverter. = = =Convert hexadecimal to binary= Example: Convert the hexadecimal number EA13B to binary EA13B => 11101010000100111011

To check the result you can use @http://www.binaryhexconverter.com/hex-to-binary-converterconverter.

Exercises

1. Convert from decimal to binary: @http://acc6.its.brooklyn.cuny.edu/~gurwitz/core5/binquiz.html

2. Play the game @https://studio.code.org/projects/applab/iukLbcDnzqgoxuu810unLw.

=Two's complement= Two's complement is one of many ways to represent negative integers with bit patterns. In decimal we represent negative 24 like this: -24 Unfortunately in binary we can't use the sign -. Remember, we can only use 0s and 1s.

How to represent a negative integer in two's complement:

• Start with an N-bit representation of an integer.
• To find the N-bit representation of the negative integer:

• Change 0 to 1, and 1 to 0.
• Add one.

Example: Positive integer: 00000011 Find the negative of the number above.

We change 0s to 1s and 1s to 0s 11111100

11111101

Solution: The negative integer of 00000011 is 11111101

So what is the range of integers in 2's complement? Ex. What integers can be represented in 3 bit 2's complement? With 3 bits we have the following combinations: 000 001 010 011 100 101 110 111

000 Good, zero is the same than minus zero.

111 (-1)

Let's get the two complement of 010. Change 0's to 1's: 101 Add 1: 110 (-2)

Let's get the two complement of 011. Change 0's to 1's: 100 Add 1: 101 (-3)

100 ?

111 (-1)

So what number is 100 representing?

What is the range of three bit two's complement?

===Range of N bit two's complement=== -(2^(n-1)) ... 0 ... 2^(n-1) - 1

Does the following 4 bit two's complement represent a negative or a positive integer? 1010

==Two's complement to denary conversion==

1. Check if the number is negative or positive by looking at the sign bit.
2. If the number is positive, simply convert it to decimal.
3. If the number is negative, make it positive by inverting the bits and adding one.
4. Then, convert the result to decimal.
5. The negative of this number is the value of the original binary.

Example: Interpret 11011011 as a two's complement binary number, and give its denary equivalent.

1. The number is negative since it starts with a 1.
2. We get the 2's complement of the number 00100100 + 1 = 00100101
3. Convert to denary: 37
4. Since the original number was negative, the final result is -37.

Exercise 1 Interpret 01101001 as a two's complement binary number, and give its decimal equivalent.

Exercise 2 Interpret 11110010 as a two's complement binary number, and give its decimal equivalent.

==Denary to two's complement conversion==

1. First, you convert the magnitude of the number to binary
2. and pad to the bit size
3. If the original number was positive, you are done.
4. Otherwise, you must negate the binary number by inverting the bits and adding 1.

Example: Convert -72 to an 8-bit, twos complement binary number.

1. Convert the magnitude, 72 to binary. 1001000
2. Pad to the bit size: 01001000
3. Two's complement: 10110111 + 1 = 10111000

So, -72 is 10111000 as an eight-bit, two's complement number.

Exercise 1: Convert 47 to an 8-bit, two's complement binary number.

Solution: 00101111

Exercise 2: Convert -109 to an 8-bit, two's complement number.

Solution: 10010011

=Exercises= 1. Write the 2's complement for each of the following 5-bit binary numbers. a) 01001 b) 01011 c) 00111 d) 00001

2. In 2's complement, what do all the positive numbers have in common?

3. If you want to write the number 7 in base 10 using 2's complement representation, what do you need to do?

4. If you want to write the number -7 in base 10 using 2's complement representation, what do you need to do?

5. Convert the following decimal numbers to binary using 6-bit 2's complement representation. a) -16 b) 13 c) -3 d) -10 e) 26 f) -31

Solution to the exercises above: 1. a) 10111 b) 10101 c) 11001 d) 11111

2. In 2's complement all the positive numbers begin with a zero.

3. To write the number 7 in base 10 using 2's complement representation you need only to convert 7 to binary.

4. To write the number -7 in base 10 using 2's complement representation you need to convert 7 to binary, complement this number, and then add 1.

a) -16 => 110000 b) 13 => 001101 c) -3 => 111101 d) -10 => 110110 e) 26 => 011010 f) -31 => 100001

=BCD (Binary Coded Decimal)= BCD splits a decimal number up into its digits and converts each digit to 4-bit binary. Example: Convert the decimal number 987 to BCD 9 => 1001 8 =>1000 7 => 0111 So 987 in decimal is 1001 1000 0111 in BCD

==Converting from BCD to decimal== To convert from BCD to decimal, separate the BCD number into 4-bit groups, and write the decimal equivalent of each group. Example. Convert the BCD number 100110101 to decimal. Solution: we separate the BCD number into 4-bit groups 0001 0011 0101 we convert each 4-bit into decimal, and we get: 135

=Character Set=

A character set is a group of unique symbols used for display and printing.

When processing characters, computer systems handle character data as numeric codes rather than as their graphical representation. For instance, when a computer stores the letter "A", it actually stores a numeric code that is interpreted by software as that letter.

A group of characters (e.g., alphabetic characters, ideographs, symbols, punctuation marks, control characters) can be encoded as a coded character set. A coded character set assigns unique numeric codes to each character in the character repertoire.

Examples of coded character sets: EBCDIC, ASCII, Unicode

==EBCDIC== @http://www.astrodigital.org/digital/ebcdic.html == == ==ASCII (American Standard Code for Information Interchange)==

@http://ascii-world.wikidot.com/history

image:sahsinfotech/ascii.JPG ==Unicode==

With ASCII one can represent only English characters. Eventually, Americans realized that they need to come up with a standard scheme to represent all characters in all languages of the world to alleviate some of the pain software developers were feeling. And out of this need, Unicode was born.

Unicode provides a unique number for every character in the world, no matter what the platform, no matter what the program, no matter what the language.

For more information take a look at @http://www.unicode.org/standard/WhatIsUnicode.html and @https://10kloc.wordpress.com/2013/08/25/plain-text-doesnt-exist-unicode-and-encodings-demystified/

@http://unicode-table.com/en/

=Units of measurement= Storage amounts are measured in bytes and there are 8 bits in 1 byte. Bits are short for "binary digits". This is the smallest unit of data that can be stored on the media.

|| 1 bit || || || 1 byte || 8 bits || || 1 kibibyte (KiB) || 2^10 bytes = 1024 bytes || || 1 Mebibyte (MiB) || 2^10 KiB = 1024 KiB || || 1 Gibibyte (GiB) || 2^10 MiB = 1024 MiB || || 1 Tebibyte (TiB) || 2^10 GiB = 1024 GiB || || 1 Pebibyte PiB) || 2^10 TiB = 1024 TiB ||

|| 1 bit || || || 1 byte || 8 bits || || 1 Kilobyte (KB) || 10^3 bytes = 1000 bytes || || 1 Megabyte (MB) || 10^3 KB = 1000 KB || || 1 Gigabyte (GB) || 10^3 MB = 1000 MB || || 1 Terabyte (TB) || 10^3 GB = 1000 GB || || 1 Petabyte (PB) || 10^3 PB = 1000 PB ||

=Images=

file:images.pdf

Vector vs. Bitmap images media type="youtube" key="fy9Pby0Gzsc" width="420" height="315"

==Bitmap==

Main terms Bitmap graphic: Image made up of rows and columns of picture elements. Image file header: Specifies the image size, number of colours, and other data needed to display the image. Pixel: Picture element. Screen resolution: Value quoted for a monitor specification, such as 1024x768. The larger the numbers, the more pixels will be displayed. Colour depth: The number of bits per pixel. Image resolution: Measured in dots per inch (dpi); this value determines the amount of detail an image has. Its value is calculated: Image resolution = Number of pixels per row * Number of rows Bitmap file size: A bitmap file has to store the pixel data but the file must also have a header that defines the resolution of the image and the coding scheme for the pixel colour. To calculate the minimum size (the size not including the header) of a bitmap file: Bitmap file size = Image resolution * colour depth

Example: A bitmap file is needed to fill a laptop screen where the resolution is 1366 by 768. The color depth is to be 24. What is the size of this image?

Solution: 1366 x 768 x 24 = 25178112 bits

The result of this calculation shows the number of bits but a file size is always quoted as a number of bytes or multiples of bytes. Thus our file size could be quoted as: 25178112 bits = 25178112/8 = 3147264 bytes .......................= 3147264/1024 = 3073.5 kibibytes (KiB) .......................= 3073.5/1024 = approx. 3MiB

Exercises 1. w15_qp_12, q 3bii How many bits are required to store each pixel for a 256-colour bitmap. Explain your answer. [2]

Characteristics of bitmap graphics:

• Bitmaps are made up of individual pixels.
• Each pixel is an addressable unit which allows subtle changes to be made to the image.
• Bitmaps can be compressed to reduce the file size, although this may result in a loss of detail.
• Each pixel represents a colour. Every pixel can be a different colour so this can result in very detailed images.
• Pixelation occurs when the image is enlarged.
• Bitmaps take a lot of storage space as the information needs to be stored for every pixel.
• Large bitmap images can take a long time to open and load.
• The more pixels, the better the resolution and the quality of the image.

Vector graphics

• Vector graphics are created by mathematical equations and calculations.
• Points in a vector graphic are described by a relative distance from the origin.
• Vector graphics can be resized, made larger or smaller without losing any clarity.
• Every line in a vector graphic is described by its features (length, thickness, colour of line, etc.)
• Objects in a vector graphic can be grouped together.

Exercises 1. The following is a file containing a drawing list. Draw the graphics from the instructions in this file. Use the bottom left corner of the box (the screen) as the origin of a coordinate system.

=Sound= //Objective:// //Show understanding of how sound is represented and encoded.// //Use the associated terminology: sampling, sampling rate, sampling resolution.// //Show understanding of how file sizes depend on sampling rate and sampling resolution.// //Show understanding of how typical features found in sound-editing software are used in practice.//

image:ADCsamplingSound.png

Sound: wave of air that interacts with our eardrum. Amplitude of a wave: it refers to the height of the wave. Sampling: measurement of value of analogue signal at regular time intervals. Sample: sampling value. Sampling rate: number of samples taken per second. Sampling resolution: the number of bits used to store each sample (sometimes referred to as bit depth).

//(Reading resources: @https://books.google.es/books?id=DYaHCgAAQBAJ&pg=PA76&dq=representing+audio+data&hl=en&sa=X&ved=0ahUKEwiGy7zCxq7KAhUFXRoKHUXKC3kQ6AEIPTAE#v=onepage&q&f=false (pages 76 to 82))// = = Exercises (From: 9608_s15_qp_11_Q2) 1 (ii) Give one reason why 16-bit sampling is used in an audio compact disc (CD). [1]

Solution: 16 bits are sufficient for good quality sound. A higher sampling resolution would mean bigger files, hence less content on each CD. 16 bits is a good compromise between quality and reasonable file size.

(iv) Give one benefit and one drawback of using a higher sampling resolution. Benefit: Drawback: [2]

Solution: Benefit: more accurate representation of the sound wave. Higher sound quality. Drawback: bigger files. Greater processing power needed. It would take longer to download.

2. Describe two typical features found in software for editing sound files. [2]

Solution: Edit start time, stop time and duration of any sound file. Extract or delete part of a clip. Pitch alteration. Fade in and fade out of a clip. Merge multiple sound sources.

(From: 9608_w15_qp_12_Q4) 3. The following information refers to a music track being recorded on a CD:

• music is sampled 44100 times per second.
• each sample is 16 bits.
• each track requires sampling for left and right speakers. a) Calculate the number of bytes required to store one second of sampled music. Show your working. [2]

Solution: (44100 * 16 * 2) / 8 = 176400 bytes

b) A particular track is four minutes long. Describe how you would calculate the number of megabytes required to store this track. [2]

Solution: Follow through from part a) on 176400

(4 * 60 * 176400) / (1024 * 1024) =

=Video= Objective: //Show understanding of the characteristics of video streams: the frame rate (frames/second); interlaced and progressive encoding; video interframe compression algorithms and spatial and temporal redundancy; multimedia container formats.//

What is a video? A sequence of still images that represent moving scenes.

What is a frame? It is each of the images that compose the moving scenes.

What is frame rate? The number of frames per second.

You can see a @https://www.supercircuits.com/resources/tools/video-frame-rate-comparison-tool.

Interlaced and progressive encoding Video can be shot and shown using interlaced (i) or progressive (p) scanning.

Progressive scanning works much like you would expect—video is broken down into separate frames. Motion is created by showing one full frame followed by another in rapid succession. Most computer screens and some new HDTVs use progressive scanning.

Interlaced, each of the 60 frames per second are only half images. Alternative rows of a TV image are scanned in each frame of the image. Thus in the first scan, rows 1, 3, 5 and all odd rows of the TV image resolution lines are scanned to form one half frame. In the second scan, rows 2, 4, 6 and all the even rows are scanned to form the other half of the image frame. The two frames are then combined to form the complete picture as shown in the image here.

When interlaced video plays, first one field appears, then the other "half" fills in the missing lines, then the first field of the next frame appears, replacing half of the image, followed by its other half, and so on, one half alternating with the other. It's kind of like weaving. This technique allows for the creation of smoother actions, but freeze-frames are often fuzzy (showing halves of two slightly different images). Since half of each image is drawn at a time, interlaced video has twice the effective frame rate of non-interlaced (progressive) video, so, 29.97 television actually shows 59.94 half-frames a second. The frame rate 60i contains the same number of individual frames as 30p, it just splits them in half.

image:Interlaced.jpg

//(Reading resources: @https://books.google.es/books?id=DYaHCgAAQBAJ&pg=PA83&dq=&hl=en&sa=X&ved=0ahUKEwiGy7zCxq7KAhUFXRoKHUXKC3kQ6AEIPTAE#v=onepage&q&f=false(page 83))//

=Compression techniques= //For more information read @https://books.google.es/books?id=DYaHCgAAQBAJ&pg=PA72&lpg=PA72&dq=&source=bl&ots=mP3UTlIW8M&sig=9xo9bMMPOJesfFCBVs7KbD2vvn8&hl=en&sa=X&ved=0ahUKEwi-17WOmqvKAhXGfxoKHYG1CosQ6AEIQzAG#v=onepage&q&f=false (pages 71 to 75)// //Objectives:// //show understanding of how digital data can be compressed, using either ‘lossless’ (including runlength encoding – RLE) or ‘lossy’ techniques//

The task of compression consists of two components, an encoding algorithm that takes a message (file) and generates a compressed representation (reduction in the amount of space needed to store a piece of data), and a decoding algorithm that reconstructs the original message or some approximation of it from the compressed representation.

==Lossless technique== The data can be retrieved without any loss of the original information.

Common lossless compression techniques: keyword encoding, run-length encoding, Huffman encoding.

===Keyword encoding=== Replace frequently used words with a single character.

//Formula to find the compression ratio:// //CR = size of the compressed data / size of the original data//

Example: Let´s encode the following paragraph:

The human body is composed of many independent systems, such as the circulatory system, the respiratory system, and the reproductive system. Not only must all systems work independently, but they must interact and cooperate as well. Overall health is a function of the well-being of separate systems, as well as how these separate systems work in concert.

We will use the following chart: || Word || Symbol || || as || ˆ || || the || - || || and || + || || that || $ || || must || & || || well || % || || these || # || The encoded paragraph is:

The human body is composed of many independent systems, such ˆ - circulatory system, - respiratory system, + - reproductive system. Not only & each system work independently, but they & interact + cooperate ˆ %. Overall health is a function of - %-being of separate systems, ˆ % ˆ how # separate systems work in concert.

There are a total of 352 characters in the original paragraph, including spaces and punctuation. The encoded paragraph contains 317 characters, resulting in a savings of 35 characters. The compression ratio for this example is 317/352 or approximately 0.9

Exercise: Given the following text: Computers are multimedia devices that manipulate data varying in form from numbers to graphics to video. Because a computer can only manipulate binary values, all forms of data must be represented in binary form. Data is classified as being continuous (analog) or discrete (digital).

Decimal values are represented by their binary equivalent, using one of several techniques for representing negative numbers, such a sign magnitude or two's compliment. Real numbers are represented by a triple made up of the sign, the digits in the number, and an exponent that specifies the radix point.

A character set is a list of alphanumeric characters and the codes that represent each one. The most common character set is Unicode (16 bits for each character), which has ASCII as a subset. The 8-bit ASCII set is sufficient for English but not for other (or multiple) languages. There are various ways for compressing text so that it takes less space to store it or less time to transmit it from one machine to another.

Audio information is represented as digitized sound waves. Color is represented by three values that represent the contribution of each of red, blue, and green. There are two basic techniques for representing pictures, bitmaps and vector graphics. Video is broken up into a series of still images, each of which is represented as a picture.

Create a keyword encoding table that contains a few simple words. || Word || Symbol || || and || & || || an || ! || || character || # || || represented || @ || || to || > || || it || < || || ASCII || % || || the || ¬ || || is || = || || that || $ ||

Compute the compression ratio you achieve.

===Run-length encoding=== A sequence of repeated characters is replaced by a flag character, followed by the repeated character, followed by a digit that indicates how many times the character is repeated.

Example: AAAAAAA

If we use the * character as our flag, this string would be encoded as *A7

Exercise Encode the following text:

nnnnnxxxxxxxxxccchhhhhh some other text kkkkkkkkeee

What is the compression ratio?

==Lossy algorithms== Some information may be lost in the process of compression.

Lossless algorithms are typically used for text, and lossy for images and sound where a little bit of loss in resolution is often undetectable, or at least acceptable.

Digital file formats Digital file formats actually consist of two separate pieces—the container and the codec.

• A container describes the structure of the file, that is where the various pieces of data are stored, how they are related, and which codecs are used by which pieces. A container may specify a separate audio codec as well as video codec, and typically also contains metadata (author names, creation dates, poster frames, etc.). A container is usually identified by a file extension such as .FLV, .AVI, .MP4, .MOV, etc. Below is a list of some of the more relevant container formats: ** MOV: Apple's Quicktime container format. The Panasonic cameras used by TV production export footage as MOV files. ** MP4 (also M4V): The standard container for the MPEG–4 family of codecs, and and H.264 codec. It is a commonly used container for Web videos, podcasts, and consumer camera files. ** WebM: An open-standard container format owned by Google. It's becoming increasingly popular among Web developers. The WebM usually uses the Vorbis codec (below).
• Video codec

Codec stands for Compressor/Decompressor. A video codec refers to the methods used to shrink the size of a movie so that it can be played on a computer or over a network. Below is a list of some of the more relevant codecs: ** MPEG–2: Introduced in 1996 by the Moving Picture Experts Group, the MPEG–2 codec is themain codec used by broadcast television and DVD. When putting packages together for UTVS, you must export your videos in this format (specifically MPEG–2 Transport Stream). ** MPEG–4: A family of codecs first introduced in 1998 by the Moving Picture Experts Group. The MPEG–4 codecs are popular for Web video due to their ability to make very small, but high quality video files. ** H.264: The most commonly used codec for Web video, and is also used for Blu-ray discs. It is actually part of the MPEG–4 family of codecs, specifically the "MPEG-4 (Part 10)" codec. The H.264 codec tends to make better looking, smaller files than the older MPEG-4. The H.264 codec, by the way, is the codec you should use for my classes (comm240, comm404, comm491) unless otherwise instructed. ** Vorbis: An open-source codec used by the WebM container format. Becoming very popular on the Web.

Types of compression that codecs use Most of the video codecs use lossy compression.

• Temporal compression: looks for differences between consecutive frames. A key frame is chosen as the basis on which to compare the differences and its entire image is stored. For consescutive images, only the changes (called delta frames) are stored. Temporal compression is effective in video that changes little from frame to frame,, such as a scene that contains little movement.
• Spatial compression: removes redundant information whithin a frame. Spatial video compression often groups pixels into blocks (rectangular areas) that have the same colour, such as a portion of a clear blue sky. Instead of storing each pixel, the colour and the coordinates of the area are stored. This idea is similar to run-length encoding.