Source coding Flashcards
What is source coding?
Converting any type of data into a binary form.
e.g. Images, sound, text
What is the equation to calculate the number of bits required for a source code?
2^L = M
M = Number of distinct characters L = Number of bits
What is ASCII? What does it stand for?
American Standard Code for Information Interchange.
A stand source code for alphanumerical data exchange
How can a protocol be synchronised?
We need to send code that that identifies the start and the end of a message
What is a fix length code?
The number of bits used for all symbols/data in a source code is the same.
What is a variable length code? What is the benefit?
The symbols/data that appears more often have fewer number of bits than symbols/data that appear less often. This can save data but requires a carefully designed source code specific to the overall data being sent.
What is required to make a variable length source code?
The data needs to uniquely decodable. This can be achieved with prefix free code.
What does uniquely decodable mean?
When the variable length code data is put in series, you are able to decode it and identify each letter individually.
What does prefix free mean?
This means that when data is put in series you are able to decode it and identify each letter individually. This is required because there is no definition where the data for a single character/data begins and ends.
What algorithm can be used to make prefix free code? and how does it work?
The Huffman algorithm:
- List all the different bits of data with the frequency that they came up and put them in order from least frequent to most frequent. They all form nodes with a value given by their frequency.
- Combine the two top nodes to produce a new node with a new combined value. Re-insert this new node into the list of nodes still in order.
- Repeat combining nodes until a single node is left.
- This should form a tree diagram which can be followed to create a prefix free code.
How are binary values read from a Huffman algorithm?
Follow the tree diagram until you reach the data required.
What is non-singular code?
This is when each character has a unique code assigned to it.
What are the two key factors that contribute to encoding-decoding overhead?
Synchronisation and exchange of encoding table
Why use variable length codes?
To save data (compression)
