Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

Arithmetic Coding

Posted on 2010-11-08
9
349 Views
Last Modified: 2012-05-10
Here is the question im having problems with, i dont know even where to start. All the examples dont use real numbers.

"A data sequence {0.47, 2.61, 1.63, -0.98, 0.23, 1.12} is first quantized by a scalar quantizer shown below, and then coded by the arithmetic coding. Assume the probabilities for the outputs of the quantizer are P(-1.5)=0.2, P(-0.5)=0.3, P(0.5)=0.4, P(1.5)=0.1, calculate the tag value to represent this data sequence."




example-5.png
0
Comment
Question by:stephen_c01
  • 5
  • 4
9 Comments
 
LVL 35

Assisted Solution

by:mccarl
mccarl earned 500 total points
ID: 34090064
First you need to get the output of the quantizer for you input data sequence. So to start you off, the input sequence and out of quantizer would start with...

input = {0.47, 2.61, 1.63, -0.98, 0.23, 1.12}
output = {0.5, 1.5, 1.5, .......}

All I did there was to look on the graph for the input data (eg, the first in the sequence is 0.47), then go directly up from the input axis at that point to where you meet the line representing the quantizer function, and look across to see that at that input value, you get an output of 0.5. Repeat for the other items in the input sequence.

Now, that output sequence contains the "symbols" that you will encode, and the probabilities of getting each "symbol" is what was given to you, eg.

 P(-1.5)=0.2, P(-0.5)=0.3, P(0.5)=0.4, P(1.5)=0.1

Check out this link, http://en.wikipedia.org/wiki/Arithmetic_coding in particular the section directly under the heading "Defining a model". This describes what to do with those probabilities and the sequence of symbols that I started working out above. Note: just because the wiki pages uses words for the symbols (such as NEUTRAL, NEGATIVE, etc) makes no difference to your situation, it is just that you have numbers to describe the symbols (such as -1.5, 0.5, etc)

If you still have questions about either of these steps, come back and let us know.

0
 
LVL 7

Author Comment

by:stephen_c01
ID: 34090173
i think the quantization was my biggest problem, just to make sure the rest of the quantized values would be?

output = {0.5, 1.5, 1.5, -0.5, 0.5, 1.5}
0
 
LVL 35

Expert Comment

by:mccarl
ID: 34090337
Yep! :) And I also went through and got an answer for the output of the encoding if you want to double check that too.
0
Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

 
LVL 7

Author Comment

by:stephen_c01
ID: 34090347
that would be great, im really having a blond moment with this.
0
 
LVL 35

Expert Comment

by:mccarl
ID: 34090379
What have you got so far?
0
 
LVL 7

Author Comment

by:stephen_c01
ID: 34090551
i got 0.49705 for the tag.

l0      0
u0      1
l1      0
u1      0.5
l2      0.45
u2      0.5
l3      0.495
u3      0.5
l4      0.496
u4      0.4975
l5      0.49675
u5      0.49735
l6      0.49675
u6      0.49735
0
 
LVL 35

Accepted Solution

by:
mccarl earned 500 total points
ID: 34090584
I think from that that you are using the symbol name not their probabilities. The -1.5, -0.5, 0.5, 1.5 are just labels, their values have no other significance.

Therefore, the intervals for your 4 symbols are as follows:

-1.5 = [0, 0.2)
-0.5 = [0.2, 0.5)
 0.5 = [0.5, 0.9)
 1.5 = [0.9, 1)

Notice the size of the interval is equal to the probability of that symbol occurring.

Another way to look at it is too rename the symbols, say A = -1.5, B = -0.5, C = 0.5, D = 1.5 and then the problem transforms into the following...

quantized data sequence = {C, D, D, B, C, D}
P(A) = 0.2, P(B) = 0.3, P(C) = 0.4, P(D) = 0.1

and then you can go from there, as a hint the result should start off like this...
// Initial interval
l0      0
u0      1

// After first data item (0.5, or C in what I renamed above)
l1      0.5
u1      0.9

// After second data item....
l2      0.86
u2      0.9

.
.
.
.
0
 
LVL 7

Author Comment

by:stephen_c01
ID: 34090596
i found an error.

l0      0
u0      1
l1      0.5
u1      0.9
l2      0.86
u2      0.9
l3      0.896
u3      0.9
l4      0.8968
u4      0.898
l5      0.8974
u5      0.89788
l6      0.90172
u6      0.89788
      
      0.8998
0
 
LVL 35

Expert Comment

by:mccarl
ID: 34090618
Everything except l6 is correct, the lower bound of the interval can't be higher than the upper bound. But it looks like you have the idea!!
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Odd Behavior 5 64
Homework Help 5 95
c++ reading data from file into two dimensional array 3 117
Does a rhombus have 2 pairs of parallel sides 5 99
How to Win a Jar of Candy Corn: A Scientific Approach! I love mathematics. If you love mathematics also, you may enjoy this tip on how to use math to win your own jar of candy corn and to impress your friends. As I said, I love math, but I gu…
Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…

808 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question