1.3 Data Storage and Compression

(i) Bit:

Bit stands for binary digit — the basic unit of data storage in computer memory.

It could be either 1 or 0, that represents the ON or OFF state of an electrical signal, which is the only thing a computer can understand.

(ii) Byte:

A group of 8 bits is called a Byte.

Byte is the smallest unit of memory in a computer.

Processors are all built to work with a set length of bits, which is usually a multiple of byte, like 8, 16, 32, 64, etc.

(iii) Nibble:

A group of 4 bits is called a Nibble, which is equal to half a byte.

A Nibble could represent 2⁴ = 16 possible values. Hence, each hexadecimal digit is represented by a nibble.

To calculate the file size of a bitmap image:

Size of image file (in bits) = Image resolution (in pixels) × Colour depth (in bits)

= Width (in pixels) × Height (in pixels) × Colour depth (in bits)

To calculate the file size of a Mono-sound:

Size of sound file (in bits) = Sample rate (in Hz) × Sample resolution (in bits) × Length of sound (in seconds)

To calculate the file size of a Stereo-sound (2 channels of audio):

Stereo is the sound recorded with two microphones placed in strategically chosen locations relative to the sound source, and played back through two channels (speakers). The two simultaneously recorded channels will be similar, but each will have distinct time-of-arrival and sound-pressure-level information.

Size of stereo-sound file (in bits) = Sample rate (in Hz) × Sample resolution (in bits) × Length of sound (in seconds) × 2 (number of channels)

To convert the size of file from bits to bytes, kilobytes, megabytes, etc.:

Size of file (in bytes) = File size in bits ÷ 8 bytes (since 1 byte = 8 bits)

Size of file (in Kibibytes) = File size in bits ÷ 8 × 1024 KiB (since 1 KiB = 1024 bytes)

Size of file (in Mebibytes) = File size in bits ÷ 8 × 1024 × 1024 MiB (since 1 MiB = 1024 KB)

(a) Image with 8 colours at 512 × 300 pixels:

8 colours = 2³ colours.

Hence, Colour depth = 3 bits (i.e. number of bits needed to represent 8 colours).

Working:

Size of image file (in bits) = Image resolution × colour depth = 512 × 300 × 3 bits

Size of image file (in bytes) = (512 × 300 × 3) ÷ 8 = 57 600 bytes (divide by 8, since 1 byte = 8 bits)

Size of image file (in KiB) = (512 × 300 × 3) ÷ (8 × 1024) = 56.25 KiB (or 57.6 KB approximately)

(b) Image converted into Black and White:

Black and White means 2 colours = 2¹ colours.

Hence, Colour depth = 1 bit (i.e. number of bits needed to represent 2 colours).

Working:

Size of image file (in bits) = Image resolution × colour depth = 512 × 300 × 1 bits

Size of image file (in bytes) = (512 × 300 × 1) ÷ 8 = 19 200 bytes

Size of image file (in KiB) = (512 × 300 × 1) ÷ (8 × 1024) = 18.75 KiB (or 19.2 KB approximately)

(a) Size of one sample, in bits:

Size of one sample (in bits) = Sample rate (Hz) × Sample resolution × Length of audio (in sec)

= 44 100 × 8 × 30 = 10 584 000 bits

(b) Size of the audio recording in MiB (stereo = 2 channels):

File size of stereo recording (in bits) = Size of one sample (in bits) × 2 Channels

= 10 584 000 × 2 = 21 168 000 bits

File size of stereo recording (in MiB) = 21 168 000 ÷ (8 × 1024 × 1024) = 2.52 MiB

(a) Data / File Compression:

File Compression is the process of encoding data more efficiently to achieve a reduction in file size.

It helps to reduce resource usage, such as data storage space or transmission capacity.

Compressed data has to be decompressed while using.

(b) Why is it necessary to compress files?

• It helps to store more data in less storage space.
• It helps to transmit large amounts of data with fewer bits.
• It minimizes the download and upload time.

(a) How Lossless compression reduces the file size:

• Lossless compression reduces file size by identifying and replacing repeated data bits or words with shorter codes.
• No information is lost in lossless compression.
• The original data is completely recovered when decompressed.
• It is used to compress files which cannot afford any loss of data, like documents, databases, program codes, etc.

(b) Compressing program file, text or document files:

• Program files use lossless compression to reduce their size, by storing repeated words in a table and replacing them with its index or numerical value.
• It identifies and replaces the repeated phrases with shorter codes generated by a complex algorithm.
• The original data is completely recovered when the file is uncompressed before using.

(a) Run Length Encoding (RLE) algorithm:

• Run Length Encoding is a lossless data compression algorithm.
• It reduces the size of a string with consecutive identical data (e.g. repeated characters of text or pixels of an image).
• A repeating character in the string is encoded with two values:
• → the first value represents the number of repetitions or identical data items in the run.
• → the second value represents the code of the repeated data item (ASCII code for characters, pixel detail for an image).
• RLE is only effective where there is a long run of repeated units of data.

(b) RLE on 'a a a a a b b b b c c d d d d':

This string contains 16 characters. If each character requires 1 byte of memory, then this string needs 16 bytes.

Using ASCII code, this string can be coded as follows:

5 97 4 98 2 99 5 100

Where, in each pair, the first values 5, 4, 2 and 5 are number of runs (repetition) and 97, 98, 99 and 100 are the ASCII code for each repeating character.

Assuming each number requires 1-byte of memory, the RLE code will need 8 bytes (4 + 4). This is half the original file size.

(c) RLE on 32-character string:

This string contains 32 characters. If each character requires 1 byte of memory, then this string needs 32 bytes.

A flag value of 255 is used to indicate the repetition of characters, followed by a pair of values — the first value is the number of runs and the second value is the ASCII code of the character.

When the flag is not used, the characters are given only their ASCII code.

Using this algorithm, this string can be coded as follows:

255 8 97 255 10 98 99 100 99 100 99 100 255 8 99

Assuming each number requires 1-byte of memory, the RLE code now requires 15 bytes.

(a) Black and White image (letter 'F' on 8 × 8 grid):

Image: 8 × 8 = 64 pixels showing the letter 'F'.

Resolution: 8 × 8 = 64 pixels

File Size (Uncompressed): 64 bytes (1 byte per pixel)

Method — RLE code (W=White, B=Black):

9W 6B 2W 1B 7W 1B 7W 5B 3W 1B 7W 1B 7W 1B 6W

Binary Representation (W=1, B=0):

91 60 21 10 71 10 71 50 31 10 71 10 71 10 61

(b) Coloured image (8 × 8 with 4 colours — black, white, red, green):

Each pixel is made up of RGB colours (a mixture of three colours red, green and blue), hence each pixel would require 3 bytes of storage.

Original File Size: 8 × 8 × 3 = 192 bytes.

Colour Coding Table (RGB values):

Method — Using RLE, the image is coded row by row:

2 0 0 0 4 0 255 0 3 0 0 6 255 255 255 1 0 0 0 2 0 255 0 4 255 0 0 4 0 255 0

1 255 255 255 2 255 0 0 1 255 255 255 4 0 255 0 4 255 0 0 4 0 255 0 4 255 255 255

2 0 255 0 1 0 0 0 2 255 255 255 2 255 0 0 2 255 255 255 3 0 0 0 4 0 255 0 2 0 0 0

The compressed RLE code has 92 values and therefore needs only 92 bytes to store the image.

(a) How Lossy compression reduces the file size:

• Reduces the file size by permanently deleting the duplicate data without which the file could solve its purpose.
• It permanently deletes the data which human cannot interpret.
• It decides which parts of file need to be retained and which parts can be discarded.
• It is not possible to regain the original file after compression.
• It is generally used to compress audio, video and image files.

(b) Lossy compression for Image files:

• Reduces the file size by reducing the image resolution, permanently deleting the duplicate pixels without which the file could solve its purpose (or by reducing the dimension of the image or number of pixels along length and width of image).
• By reducing the colour depth that reduces the number of bits needed to represent each pixel.
• As the compression increases, the quality of the image decreases.
• It is not possible to regain the original file after compression.

(c) Lossy compression for Sound files:

• Reduces the file size by reducing the sound resolution (or bit-depth), the number of bits needed to represent each sample.
• By reducing the sample rate, the number of samples recorded per second.
• As the compression increases, the quality of the sound decreases.
• It is not possible to regain the original file after compression.

(d) Lossy compression for Video files:

• Reduces the file size by reducing the sound resolution and sample rate of the audio.
• Reduces the pixel dimension and colour depth of all the frames.
• Reduces the frame rate of the video.
• Once compressed, the file cannot be regained to its original form.

(e) Reason to choose lossy over lossless compression:

• It produces a much smaller compressed file than lossless method, that still meets the purpose of the file even by permanently deleting some data.

(a) Uncompressed Image file formats:

RAW images are images that are unprocessed and uncompressed that have been created by a camera or scanner. There are a lot of different raw formats (like .raw, .cr2, .nef, .orf, .sr2, and more), each camera company often has its own proprietary format.

(b) Lossless compression Image file formats:

1. BMP (file types ending in .bmp): BMP stands for Bitmap Image. They are uncompressed, designed to store raw device-independent bitmap images.
2. TIFF (file types ending in .tif): TIFF stands for Tagged Image File Format. They are uncompressed and thus contain a lot of detailed image data, commonly used in medical imaging and in photo software.
3. PNG (file types ending in .png): PNG stands for Portable Network Graphics. They are lossless compressed, commonly used to store web graphics, digital photographs, and images with transparent backgrounds.
4. GIF (file types ending in .gif): GIF stands for Graphic Interchange Format. It has limited 256 colour range, supports transparent background, used for animations. It uses lossless compression suitable for the web.

(c) Lossy compression Image file formats:

1. JPEG (file types ending in .jpg): JPEG stands for Joint Photographic Experts Group. They are compressed files using lossy algorithm, mostly used by digital cameras to store more photos in its memory cards and used for photographs on web pages.
2. AVIF (file types ending in .avif): AVIF stands for AV1 Image File Format. It is the latest image file format that offers excellent lossy compression algorithm to achieve 50% smaller image size than JPEG images.