[daala] daala Digest, Vol 24, Issue 2

[Knight Kim]

Thank you for your response.
I am studying the PDF you sent.
Could I ask you more if I have more questions?

Thanks again.
Best regards,
Knight.

2020년 7월 28일 (화) 오전 7:48, <daala-request at xiph.org>님이 작성:

> Send daala mailing list submissions to
>         daala at xiph.org
>
> To subscribe or unsubscribe via the World Wide Web, visit
>         http://lists.xiph.org/mailman/listinfo/daala
> or, via email, send a message with subject or body 'help' to
>         daala-request at xiph.org
>
> You can reach the person managing the list at
>         daala-owner at xiph.org
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of daala digest..."
>
>
> Today's Topics:
>
>    1. Re: Can I implement entropy of AV1 encoder without
>       back-propagation of precarry buffer? (Timothy B. Terriberry)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Mon, 27 Jul 2020 14:54:59 -0700
> From: "Timothy B. Terriberry" <tterriberry at mozilla.com>
> To: Jarek Duda <dudajar at gmail.com>, daala at xiph.org
> Subject: Re: [daala] Can I implement entropy of AV1 encoder without
>         back-propagation of precarry buffer?
> Message-ID: <3c41971f-b803-7d3b-1b02-5bfa7488b20d at xiph.org>
> Content-Type: text/plain; charset="utf-8"; Format="flowed"
>
> Jarek Duda wrote:
> > I don't know the details, but might be the one to blame: sounds like an
> > artifact of being able to switch between RC (range coder) and rANS
> > during development (I think Alex Converse was responsible), while
> > finally RC was used.
>
> No, this was actually a totally unrelated software optimization. See
> Section 5.2 of Thomas Davies' 2008 paper "Speeding Up Arithmetic Coding
> and Decoding in the Schroedinger Implementation of Dirac." I can't
> actually find a copy online anymore to link, so I've attached it.
>
> > W dniu 27.07.2020 o 11:07, Knight Kim pisze:
> >> Hello,
> >>
> >> I am implementing entropy HW for AV1 video codec.
> >> I want to make the HW with the smallest precarry buffer.
> >> Currently, aom encoder is scanning reverse direction adding precarry
> >> to previous buffer point.
> >> It means that I should keep all bitstreams in a tile, and scan all the
> >> bitstreams then generate it.
> >> At HW point of view, this kind of operation is quite inefficient.
> >> Is there any way to implement the entropy encoder without precarry
> >> back-propagation?
> >> Can I determine the maximum length of back-propagation?
>
> In general there is no limit to how far a carry can propagate. The
> traditional way to handle this (described, e.g., by witten, Neal, and
> Cleary in their 1987 Communications of the ACM paper, "Arithmetic Coding
> for Data Compression") is to maintain a counter storing how many
> outstanding 1 bits a carry *could* propagate through, in lieu of
> actually outputting those bits. Only once the final value of those bits
> is determined would you actually flush them to the buffer. We don't do
> this in modern software because it puts expensive branches in an inner
> loop.
>
> In practice you still need to have some maximum in order to know how
> many bits to use for the counter, but it could be as large as the
> maximum number of output bits for a tile, in theory (although this is
> exceedingly unlikely). In practice H.264's CABAC and other entropy
> coders (VP8, VP9, etc.) all require the exact same carry-propagation
> behavior, so whatever you are doing to deal with it for those codecs
> should apply just as easily for AV1.
> -------------- next part --------------
> A non-text attachment was scrubbed...
> Name:
> Davies08-_Speeding_Up_Arithmetic_Coding_and_Decoding_in_the_Schroedinger_Implementation_of_Dirac.pdf
> Type: application/pdf
> Size: 123626 bytes
> Desc: not available
> URL: <
> http://lists.xiph.org/pipermail/daala/attachments/20200727/148bc030/attachment.pdf
> >
>
> ------------------------------
>
> Subject: Digest Footer
>
> _______________________________________________
> daala mailing list
> daala at xiph.org
> http://lists.xiph.org/mailman/listinfo/daala
>
>
> ------------------------------
>
> End of daala Digest, Vol 24, Issue 2
> ************************************
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.xiph.org/pipermail/daala/attachments/20200728/cadbc142/attachment.html>