Transcript Run Length Encoder/Decoder

Run Length
Encoder/Decoder
EE113D Project
Authors: Imran Hoque
Yipeng Li
Diwei Zhang
Introduction – What is RLE?

Compression technique
• Represents data using value and run length
• Run length defined as number of consecutive
equal values
e.g
1110011111
RLE
130215
Values
Run Lengths
Introduction - Applications

Useful for compressing data that contains
repeated values
• e.g. output from a filter, many consecutive
values are 0.


Very simple compared with other
compression techniques
Reversible (Lossless) compression
• decompression is just as easy
Introduction - Applications

Image Compression – JPEG
Run Length Encoder!
Introduction


Compression effectiveness depends on input
Must have consecutive runs of values in order
to maximize compression
• Best case: all values same

Can represent any length using two values
• Worst case: no repeating values


Compressed data twice the length of original!!
Should only be used in situations where we
know for sure have repeating values
Encoder - Algorithm


Start on the first element of input
Examine next value
• If same as previous value


Keep a counter of consecutive values
Keep examining the next value until a different
value or end of input then output the value
followed by the counter. Repeat
• If not same as previous value

Output the previous value followed by ‘1’ (run
length. Repeat
Encoder – Matlab Code
% Run Length Encoder
% EE113D Project
function encoded = RLE_encode(input)
my_size = size(input);
length = my_size(2);
run_length = 1;
encoded = [];
for i=2:length
if input(i) == input(i-1)
run_length = run_length + 1;
else
encoded = [encoded input(i-1) run_length];
run_length = 1;
end
end
if length > 1
% Add last value and run length to output
encoded = [encoded input(i) run_length];
else
% Special case if input is of length 1
encoded = [input(1) 1];
end
Encoder – Matlab Results
>> RLE_encode([1 0 0 0 0 2 2 2 1 1 3])
ans =
1
1
0
4
2
3
1
2
3
1
>> RLE_encode([0 0 0 0 0 0 0 0 0 0 0])
ans =
0 11
>> RLE_encode([0 1 2 3 4 5 6 7 8 9])
ans =
0
1
1
7
1
1
1
8
2
1
1
9
3
1
1
4
1
5
1
6
Encoder

Input from separate .asm file
• In the form of a vector
• e.g. ‘array .word

4,5,5,2,7,3,6,9,9,10,10,10,10,10,10,0,0’
Output is declared as data memory space
• Examine memory to get output
• Originally declared to be all -1.

Immediate Problem
• Output size not known until run-time (depends on input
size as well as input pattern)

Cannot initialize variable size array
Encoder

Solution
• Limit user input to preset length (16)
• Initialize output to worst case (double input
length – 32)
• Initialize output to all -1’s (we’re only handling
positive numbers and 0 as inputs)
• Output ends when -1 first appears or if length
of output equals to worst case
Encoder – DSP Code
;*******************************************************************
;EE113D Final Project
(encoder)
;
;Run Length Encoder: Shortens a series of input data by representing
;consecutive repeated numbers as the repeated number, followed by
;the number of repetitions.
;
;(Written by: Yi-peng Li, Diwei Zhang, Imran Hoque)
;
.setsect ".text", 0x500,0
.setsect ".data", 0x800,1
;Executible code in ".text"
;section will begin at 0x500
;in program memory
;Numbers to be sorted will
;begin at 0x800 in data memory
.data
;Data section begins
.copy "e_inputs.asm"
;Reads input values and initialize output
.text
;Executible code section begins.
count1
.set 1
;Initialize a counter starting at the number 1
count2
.set 15
;Initialize a counter starting at the number 15
Encoder – DSP Code
AR6 = #array
AR3 = #array
A = *AR3+
A = *AR3
AR5 = A
A = *AR6
AR0 = A
AR4 = #output
AR2 = #count2
;AR6 points to the input data location
;AR3 points to the next input data location
;AR5 represents the actual number stored
;in the memory address AR3 points to
;(the actual number represented in the input)
;AR0 represents the actual number stored
;in the memory address AR6 points to
;AR4 points to the output data location
;AR2 keeps track of how much of the input
;data has been read
;loop1 initializes the count of AR1 to '1'
loop1
AR1 = #count1
;Register AR1 is used to keep track of the
;number of repeated inputs in succession
;loop2 reads through the input data, and keeps
;track of the number of consecutive inputs
loop2 TC = (AR0 != AR5)
A = *AR6+
A = *AR3+
;Compares the number stored in AR5 with the
;number stored in AR0
;Increment the pointer AR6
;Increment the pointer AR3
Encoder – DSP Code
A = *AR3
AR5 = A
A = *AR6
;Re-initialize AR5
AR0 = A
if (TC) goto loop3
A = *AR1+
if (*AR2- != 0) goto loop2
A = *AR2+
;Re-initialize AR0
;Break loop if next number different
;else continue counting
;Stop encoder if count of AR2 reaches zero
;Leave count of AR2 at zero
;loop3 stores the encoded input, followed by
;its repeated count into the output array
loop3
A = *AR6A = *AR6
*AR4+ = A
A = AR1
*AR4+ = A
A = *AR6+
if (*AR2- != 0) goto loop1
stop
nop
goto stop
.end
;Point back to the last repeated number
;Add the repeated number to output
;Add the count of repeated number to output
;Move pointer back to where it left off
;Stop encoder if count of AR2 reaches zero
;infinite loop
Encoder – DSP Results
Input: 4,5,5,2,7,3,6,9,9,10,10,10,10,10,10,0,0
Output: 4,1,5,2,2,1,7,1,3,1,6,1,9,2,10,6,0,2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1…
Valid Output
Output Ends Here
Best Case:
Input: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Output: 0,16,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1…
Worst Case:
Input: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
Output: 0,1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,1,10,1,11,1,12,1,13,1,14,1,15,1
Decoder – Matlab Code
% Run Length Decoder
% EE113D Project
% The input to this function should be the output from Run Length Encoder,
% which means it assumes even number of elements in the input. The first
% element is a value followed by the run count. Thus all odd elements in
% the input are assumed the values and even elements the run counts.
%
function decoded = RLE_decode(encoded)
my_size = size(encoded);
length = my_size(2);
index = 1;
decoded = [];
% iterate through the input
while (index <= length)
% get value which is followed by the run count
value = encoded(index);
run_length = encoded(index + 1);
for i=1:run_length
% loop adding 'value' to output 'run_length' times
decoded = [decoded value];
end
% put index at next value element (odd element)
index = index + 2;
end
Decoder – Matlab Results
>> RLE_decode([0 12])
ans =
0
0
0
0
0
0
0
0
0
0
0
0
>> RLE_decode([0 1 1 1 2 1 3 1 4 1 5 1])
ans =
0
1
2
3
4
5
>> RLE_decode(RLE_encode([0 0 3 1 4 4 5 6 10]))
ans =
0
0
3
1
4
4
5
6 10
Decoder – DSP Code
;*******************************************************************
;EE113D Final Project (decoder)
;
;Run Length Encoder: Takes as its input, a string of data encoded
;according the the run length encoder algorithm, and outputs it
;as the decoded string of data originally input to the encoder.
;(Written by: Yi-peng Li, Diwei Zhang, Imran Hoque)
.setsect ".text", 0x500,0
;Executible code in ".text“ section will begin at 0x500
;in program memory
.setsect ".data", 0x800,1
;Numbers to be sorted will begin at 0x800 in data memory
.data
.copy "d_inputs.asm"
;Data section begins
;Get input values and initialze outputs
.text
;Executible code section begins.
count2
.set 14
AR6 = #array
AR3 = #array
A = *AR3+
A = *AR3
AR5 = A
;Initialize a counter starting at the number 14
;AR6 points to the input data location
;AR3 points to the next input data location
;AR5 keeps track of the number of repetitions
Decoder – DSP Code
AR4 = #output
AR2 = #count2
;AR4 points to the output data location
;AR0 keeps track of how much of the input
;data has been read
;loop2 reads through the input data to the decoder
loop2
if (*AR5- != 0) goto loop3
;Keep outputting the current input number until
;the following count of that number reaches zero
;Else continue reading thru input
;Increment twice to get next number in output
A = *AR6+
A = *AR6+
A = *AR3+
A = *AR3+
;Increment twice to get the count of that number
A = *AR3
AR5 = A
;Re-initialize AR5
if (*AR2- != 0) goto loop2
;Stop encoder if count of AR2 reaches zero
goto stop
;loop3 stores the decoded output, by expanding the number of repeated inputs
loop3
A = *AR6
*AR4+ = A
goto loop2
stop
nop
goto stop
.end
;Add the repeated number to output
;infinite loop
Decoder – DSP Results
Input: 0,16
Output: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Input: 1,5,0,11
Output: 1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0
Conclusion


Results obtained from DSP match theoretical
results as well as Matlab results
Limitations:
• Does not handle negative numbers
• Input to encoder limited to 16 numbers in this
implementation

Future Improvements
• Variable input lengths
• Allocate memory for output real-time