COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Newbie Q's about arithmetic coding?

• Email
• Follow

```I am trying to create my own compression method to better compress but
don't think I can do it.  However, I am still trying.  I've been
looking at online documentation for arithmetic coding (http://
en.wikipedia.org/wiki/Arithmetic_coding) and am confused.  I get most
of it but don't understand renormalization.  Under that section is the
line, "those digits are sent to the output."  This line is confusing
to me.  Can anybody explain this section to me?  I am limited to a
high-school education.  Thank you!
---------
Joseph Rose, a.k.a. Harry Potter
Creating magic in the computer community...or at least striving to!
```
 0

See related articles to this posting

```"Harry Potter" <maspethrose7@aol.com> wrote in message
> I am trying to create my own compression method to better compress but
> don't think I can do it.  However, I am still trying.  I've been
> looking at online documentation for arithmetic coding (http://
> en.wikipedia.org/wiki/Arithmetic_coding) and am confused.  I get most
> of it but don't understand renormalization.  Under that section is the
> line, "those digits are sent to the output."  This line is confusing
> to me.  Can anybody explain this section to me?  I am limited to a
> high-school education.  Thank you!

It means that as soon as you determine that a digit will never change
anymore, you can save it ("send to output") and remove it from further
calculations (because they wouldn't change anyway)
Most of the rest of that paragraph is just there to confuse you, I think
someone felt the need to give an informal proof of correctness.
Anyway, let's have an easy explanation:
You're "zooming in" on the eventual value, which means that at every
iteration your value will be closer to the end result than you were before,
so sometimes you will have digits at the beginning that are already the same
as what they will end up being. Since they won't change, you might as well
stop trying to change them.

```
 0

```Harry Potter schrieb:
> I am trying to create my own compression method to better compress but
> don't think I can do it.  However, I am still trying.  I've been
> looking at online documentation for arithmetic coding (http://
> en.wikipedia.org/wiki/Arithmetic_coding) and am confused.  I get most
> of it but don't understand renormalization.  Under that section is the
> line, "those digits are sent to the output."  This line is confusing
> to me.  Can anybody explain this section to me?  I am limited to a
> high-school education.

The state of an arithmetic coder is defined by the current interval
describing - or encoding - the input stream seen so far. That is, by an
upper and lower interval edge. Let's say:

upper = 0.54434235 and
lower = 0.54324325

Since by the construction of arithmetic coding the coding interval can
only become smaller, "lower" can only grow and "upper" can only shrink,
but always under the constraint that upper > lower.

By that you'll see that the first two digits ("54") no longer change in
the coding process, and these two can be written out to disk
immediately. Since they no longer change, one can, indeed, ignore them
completely and ignore them in further processing.

Mathematically this means first multiplying upper and lower by 100 (thus
moving the 0.54 in front of the fraction) and then subtracting 54. That
is, you replace

upper = 0.54434235 -> 54.43423500 -> 0.43423500
lower = 0.54324325 -> 54.32432500 -> 0.32432500

and continue with these numbers as before. As you can see, in this
example no infinite precision is needed.

(There is a catch here, namely you'd still need infinite precision for
the special "race condition" of

upper = 0.540000000....
and
lower = 0.539999999....

because then it might take a very long time before the first two digits
may become identical, but there is also a trick here to handle this
"carry over" situation. Please come back if you want to know.
)

So long,
Thomas
```
 0

```On Jul 6, 10:39=A0am, "Harold Aptroot" <harold.aptr...@gmail.com> wrote:
> "Harry Potter" <maspethro...@aol.com> wrote in message
>
>
> > I am trying to create my own compression method to better compress but
> > don't think I can do it. =A0However, I am still trying. =A0I've been
> > looking at online documentation for arithmetic coding (http://
> > en.wikipedia.org/wiki/Arithmetic_coding) and am confused. =A0I get most
> > of it but don't understand renormalization. =A0Under that section is th=
e
> > line, "those digits are sent to the output." =A0This line is confusing
> > to me. =A0Can anybody explain this section to me? =A0I am limited to a
> > high-school education. =A0Thank you!
>
> It means that as soon as you determine that a digit will never change
> anymore, you can save it ("send to output") and remove it from further
> calculations (because they wouldn't change anyway)
> Most of the rest of that paragraph is just there to confuse you, I think
> someone felt the need to give an informal proof of correctness.
> Anyway, let's have an easy explanation:
> You're "zooming in" on the eventual value, which means that at every
> iteration your value will be closer to the end result than you were befor=
e,
> so sometimes you will have digits at the beginning that are already the s=
ame
> as what they will end up being. Since they won't change, you might as wel=
l
> stop trying to change them.

I still don't understand.  Unfortunately, I have been unsuccessful at
my goal with file compression, so I don't want to pursue the issue--
yet.
---------
Joseph Rose, a.k.a. Harry Potter
Creating magic in the computer community...or at least striving to! :(
```
 0

3 Replies
103 Views

Similar Articles

12/20/2013 8:34:37 AM
page loaded in 318748 ms. (1)

Similar Artilces:

Arithmetic Coding newbie

newbie Q
AVR mega16 uC / ICCAVR compiler On reset, I run bootloader code, then I jump to the main application. When doing so, I want to store two bytes of data from the bootloader for use in the main code. It seems that the easy solution probably lies in an area I have virtually no knowledge of, assembly language (I use C and compile with ICCAVR), and direct use of registers. Advice? Thanks, Scott Kelley Scott Kelley wrote: > AVR mega16 uC / ICCAVR compiler > > On reset, I run bootloader code, then I jump to the main application. > When doing so, I want to store two bytes of dat...

Huffman Coding and Arithmetic Coding
Hi everybody, i m trying to find somebody who ever worked on Huffman coding... Trying to use files found in File Exchange, and i ve got a lot of errors I don't understand... Please, contact me if u know stg about image compression... Thanx "amelie" <amelie.quinet@reseau.eseo.fr> wrote in message news:ef2ca1d.-1@webx.raydaftYaTP... > Hi everybody, > > i m trying to find somebody who ever worked on Huffman coding... > Trying to use files found in File Exchange, and i ve got a lot of > errors I don't understand... > > Please, contact me if u know...

Newbie Q: A tougher Q
Hi Gurus, I think i fixed my previous prob. I had to use -G option while linking. Here is another Q. I have Test1.cpp which is compiled using "cc -c Test1.cpp" and linked using "cc -G Test1.o". I rename the result shr.o as libTest1.a. I have Test2.cpp which is compiled using "cc -c Test2.cpp" and linked using "cc -G Test2.o". I rename the result shr.o as libTest2.a. Function F1() in libTest1.a calls function F2() in libTest2.a. When I load libTest1.a dynamically and call F1(), I get a coredump when F1() tries to call F2(). Probably something to do w...

Newbie q
Sorry for the question, but because my English is not so good, i do not know how to look it up in Google, so any hints pointing into a solution or the google entry would help: Sendmail is worling well only: Someon from outside our networkcan send mail into our network using our domain as a "from" adres How can I reject mail that comes from an "exernal"ip adres that uses a from adres that should come from our "internal" ip adres? Sorry for the inconvinience. Henk-J wrote: > Sorry for the question, but because my English is not so good, i do not know >...

Newbie Q
Got some questions that are probably simple to answer - for someone except me! I'm a PC user... We are considering building a multimedia system around a Mac, specifically the non-duo version of the Mac Mini because of its superior (compared to WMP) software. So, some of the questions are: a) Can we rip CDs to disc non-compressed? Is it a standard option? b) How easy is it to replace the 60GB disc with (say) a 750GB one? c) Can we rip CDs to a lossless compressed format? Is there a standard option? If so, which one? d) (And I suspect the answer is no...) Can we rip DVDs to disc? tha...

`If ` Q from newbie
Hi all; As my starter into Python I have a small project using pullparser.py My problem is testing what is coming back from a def() in pullparser.py I bet this is me not understanding something in Python. I do �.. tk = p.get_token() print tk �� and get:- 1 Token('data', '\n \n\n', None) 2 Token('comment', '#include virtual="/software/main/inc/warning.inc" ', None) 3 Token('data', '\n\n', None) 4 Token('startendtag', 'meta', [('name', 'DC.Rights'), ('content', 'Copyright (c) 2004 by IBM...

Newbie Q
Hey... i've made a CPLD board XL9572... it is way to small to put in a softcore uC like an 8051... ??? Any sugestion to a FPGA insead... and which one ? and is it possible to do a board my self ? i looked on this board : http://www.burched.biz/ but a lot of money for a student... and i think i can get made proff 2 sided pcb very cheap... Kasper ??? :) > Hey... > > i've made a CPLD board XL9572... it is way to small to put in a softcore uC > like an 8051... ??? > > > Any sugestion to a FPGA insead... and which one ? and is it possible to do a > board m...

newbie q.
Hello Group, I'm very very new to all things AI. But from what I can tell, Neural networks can be applied to classify a data set? Assume I can generate a large data sets( as large as i want, thousands to hundreds of thousands) These data sets are mainly randomly perturbed parameters of a dynamical system. Let's also say that I can associate outputs to each of the parameters. I would like to now implement neural net to classify the parameters into different categories depending on the behaviors of the output. ie. given x'= b(x_t) we can generate a randomly perturbed syst...

Arithmetic coding?
Hi, Have been researching arithmetic encoding and have managed to get it to work! I have a string "aabbbccccdddddeeeeefffffffgggggggg" and wrote a program that calculated the probabilities and then ran through the arithmetic algorithm. The result is something like 0.000204284822479605. Fine but What does that mean!? How do I find by how much the string has been compressed? How many bits this takes up? etc. I presume that the receiver/decoder would require the probability table also. Do I need to send that? how many bits will that be? So many questions......... If anyone can help I...