Run length encoding

1. RUN LENGTH ENCODING Praseetha S Nair M.Tech(CS)

2. COMPRESSION Data compressed by eliminating redundant elements. Purpose of compression:- -save storage space -reduce communications capacity requirements Some code must be substituted for eliminated element. Based on this code receiver can reconstruct original data.

3. Categories:- 1.lossless compression -no information lost -decompressed data are identical to original uncompressed data 2.lossy compression -decompressed data may be an approximation to the original uncompressed data

4. Null Suppression Oldest and simplest Long string of blanks , nulls etc cause redundancy. At transmitter: -scans data for string of blanks. -substitute two character code for any string that is encountered.

5. Example : the string XYZ bbbbb QRX is replaced by XYZS C 5QRX where S c is a special compression indication character b is symbol for a blank space

6. At receiver : -scan incoming character for special indication character -reconstruct original data

7. Run-Length E ncoding Compress any type of repeating data sequence At transmitter: -identify repeating characters to replace -if found, eliminate and replace by three- character code

8. S c X C c S c -Special character indicating compression follows X-Any repeated data character C c -Character count (a) Compression format Original data string Encoded data string $******55.72 $ c *655.72 --------- S c- 9 Guns bbbbbbbbb Butter GunsS c b9Butter (b)Examples Fig: Run-Length Encoding

9. Efficiency depends on -number of repeated character occurrences in data to be compressed -average repeated character length. Compression ratio= length of uncompressed data length of compressed data Any compression scheme will have variable performance as the content of the input varies.

10. It is used as an element in more complex image compression technique. For run-length encoding on an image, transmission of digital line scan is replaced by transmission of a quantity count of each of successive run of black or white scanned picture element.

11. 0000000000 0000000000 000 1111 000 000 1 00 1 000 000 1111 000 000000 1 000 000000 1 000 000 1111 000 0000000000 0000000000 Length:100 bit 23W 4B 6W 1B 2W 1B 6W 4B 9W 1B 9W 1B 6W 4B 23W or: 23 4 6 1 6 4 9 1 916 4 23 Length:15characters=120bit (c)Simple run-length encoding (a)Image Fig: Run-Length Code for a 100-pixel image

12. Application of run length encoding to a 10X10 image. 10X10 representation is converted to a 100-bit code. Each pixel is represented by a single bit indicate black or white. Run-length code consist of length of alternate black or white sequence. Encoded data stream is a string of number that indicate length of alternate black or white runs.

13. THANK YOU