Subject: [codec] #20: Computational complexity?

From: "codec issue tracker" <[email-masked]>
Date: Sat, 01 May 2010 10:48:52 -0000

#20: Computational complexity?
------------------------------------+---------------------------------------
 Reporter:  hoene@…                 |       Owner:     
     Type:  defect                  |      Status:  new
 Priority:  major                   |   Milestone:     
Component:  requirements            |     Version:     
 Severity:  -                       |    Keywords:     
------------------------------------+---------------------------------------
 How large shall the complexity of the CODEC be? How to measure it?
 Shall the CODEC support modes of different complexity?
 How much memory is the implementation instance going to consume?

-- 
Ticket URL: <http://trac.tools.ietf.org/wg/codec/trac/ticket/20>
codec <http://tools.ietf.org/codec/>

---

From: "codec issue tracker" <[email-masked]>
Date: Sat, 01 May 2010 14:30:37 -0000

Comment(by hoene@…):

 [Raymond]:

 > 3) Many telephone terminal devices at the edge of the Internet use
 > embedded processors with limited processing power, and the processors
 > also have to handle many tasks other than speech coding. If the IETF
 > codec complexity is too high, some of such devices may not have
 > sufficient processing power to run it. Even if the codec can fit, some
 > battery-powered mobile devices may prefer to run a lower-complexity
 > codec to reduce power consumption and battery drain. For example, even
 > if you make a Internet phone call from a computer, you may like the
 > convenience of using a Bluetooth headset that allows you to walk
 > around a bit and have hands-free operation. Currently most Bluetooth
 > headsets have small form factors with a tiny battery. This puts a
 > severe constraint on power consumption. Bluetooth headset chips
 > typically have very limited processing capability, and it has to
 > handle many other tasks such as echo cancellation and noise reduction.
 > There is just not enough processing power to handle a relatively
 > high-complexity codec. Most BT headsets today relies on the extremely
 > low-complexity, hardware-based CVSD codec at 64 kb/s to transmit
 > narrowband voice, but CVSD has audible coding noise, so it degrades
 > the overall audio quality. If the IETF codec has low enough
 > complexity, it would be possible to directly encode and decode the
 > IETF codec bit-stream at the BT headset, thus avoiding the quality
 > degradation of CVSD transcoding.

 [Koen]: By the time the BlueTooth Special Interest Group will have adopted
 a future IETF codec standard, Moore's law will surely have multiplied CPU
 resources in the BT device by one order of magnitude..?  Not sure it makes
 sense to apply today's BT constraints to tomorrow's codec.

 [Raymond]: Most importantly, guess what, in the last several years the
 Bluetooth headset chips have been growing its processing power at a MUCH,
 MUCH slower rate than what the Moore's Law says it should. Sometimes they
 did not increase the speed at all for years.  The reasons? The ASP
 (average sale price) of Bluetooth chips plummeted very badly, making it
 unattractive to invest significant resources to make them significantly
 faster.  Also, for low-end and mid-end BT headsets, the BT chips were
 often considered "good enough" and there wasn't a strong drive to increase
 the computing resources.  In addition, the BT headsets got smaller over
 the last few years; the corresponding reduction in battery size required a
 reduction in power consumption, which also limited how fast the processor
 speed could grow.  In the next several years, it is highly likely that the
 computing capabilities of Bluetooth headset chips will continue to grow at
 a rate substantially below what's predicted by the Moore's Law.

 [Raymond]: I would like to take this opportunity to express my view that
 although codec complexity isn’t much of an issue for PC-to-PC calls where
 there are GHz of processing power available, the codec complexity is an
 important issue in certain application scenarios. The following are just
 some examples.
 1) If a conference bridge has to decode a large number of voice channels,
 mix, and re-encode, and if compressed-domain mixing cannot be done (which
 is usually the case), then it is important to keep the decoder complexity
 low.

 [JM]: The decoder complexity is very important. Not only because of mixing
 issue, but also because the decoder is generally not allowed to take
 shortcuts to save on complexity (unlike the encoder). As for compressed-
 domain mixing, as you say it is not always available, but *if* we can do
 it (even if only partially), then that can result in a "free" reduction in
 decoder complexity for mixing.

 [Koen]: A codec/mode that meets the BT requirements for ultra-low
 complexity will have a relatively poor coding efficiency, resulting in
 lower audio quality and/or a higher bitrate.  Both of these negatively
 impact the user experience over the Internet.  Therefore, you do not want
 to run a BT codec over the Internet if you can use a more efficient codec
 instead.

 [Raymond]: Bluetooth headsets have much lower processing power and much
 smaller batteries than cell phones. The complexity of cellular codecs,
 typically in the range of 20 to 40 MHz on a DSP, is too high to fit most
 Bluetooth headsets. However, unlike cell phones and Bluetooth headsets
 where each is a specific type of device with a relatively narrow range of
 device complexity, Internet voice/audio applications can potentially
 encompass a large variety of different device types, from desktop
 computers at the high end with > 3 GHz multi-core CPU to IP phones and
 possibly even Bluetooth headsets at the low end with a processor of only a
 few tens of MHz.  It is up to the IETF codec WG how we want the complexity
 of the IETF codec to be.  We can standardize just one codec mode that
 works well for computer-to-computer calls but can't fit in low-end
 devices, or we can keep that mode but also have a low-complexity mode that
 can be implemented in low-end devices.

-- 
Ticket URL: <http://trac.tools.ietf.org/wg/codec/trac/ticket/20#comment:1>
codec <http://tools.ietf.org/codec/>

---

From: "codec issue tracker" <[email-masked]>
Date: Mon, 24 May 2010 14:14:30 -0000

Comment(by hoene@…):

 [Benjamin]:
 I think this is a typo, and you mean "lessened the pressure to reduce
 bitrates and complexity, and has shifted the focus to fidelity and delay
 instead".
 ...
 I'd also like some clarification as to whether we're talking about ... or
 (b) future hardware designed to support the IWAC.  If (b), then this is
 just a matter of negotiating the acceptable
 encode+decode complexity, for eventual implementation by DSP or ASIC.

 [Raymond]:
 My main point in this area is just that there are complexity-sensitive
 applications such as low-end devices and VoIP gateways where a low codec
 complexity is important or even necessary.  In other words, if the IETF
 codec complexity is too high, then either it will become much more
 expensive for some applications (e.g. gateways), or it may not even be
 feasible to put the codec in some low-end devices. ...
 I merely wanted to use Bluetooth headset as an example to make a point
 that a low codec complexity is desirable and a high codec complexity can
 have negative consequences.

 [Kevin]: This is all perfectly reasonable, but given the likely timeframe
 we are talking about for this codec to be produced and published as a
 standards-track RFC, the definition of 'low complexity' in this discussion
 is really talking about the 2012-2013 version of 'low complexity', not
 today's. It seems highly likely that the MIPS capacity of the DSPs
 designed into Bluetooth headsets in 2012 will be vastly greater than what
 is used today, if there is an application to take advantage of the
 additional MIPS.

 [Raymond]: I completely agree with you that the IETF codec development
 should not be constrained by a low-complexity device designed in 2009 or
 earlier, and we should look toward the time frame of 2012 and 2013
 instead.

 In my previous emails I have indicated that due to many reasons, over the
 last several years the processing power of Bluetooth headsets has been
 increasing at a rate much slower than what's predicted by Moore's Law, and
 it doesn't look like this will change significantly in the next few years.
 I also said that for the current-generation Bluetooth headset chips, the
 maximum codec complexity it can support is probably somewhere around 5
 MIPS on a 16-bit fixed-point DSP, and by the time the IETF codec becomes a
 standard, the number may go up to 10 MIPS, or 15 MIPS at most.

 Thus, if we want mono Bluetooth headsets in the FUTURE (i.e. in the next
 several years) to be able to run the IETF codec in the narrowband or
 wideband mode at least, a good complexity target to shoot for is 10 to 20
 MIPS on a fixed-point DSP.

 [JM]
 I'm just curious about where you got your MIPS figures for Bluetooth? I'm
 not familiar with the type of DSPs used in those applications, but from a
 quick search of more "general-purpose" DSPs (TI, ADI and similar), the
 lowest speed I was able to find (sold in 2010) was a 50 MIPS DSP. Any idea
 what type of DSPs are currently used in Bluetooth?

 [Raymond]:
 I should have clarified:
 I am not proposing that we limit the complexity of all IETF codec modes to
 10 to 20 MIPS.  That would be unreasonable, especially for high- sampling-
 rate and high-fidelity applications.

 Just like we seemed to have reached a consensus that a low-delay mode is
 necessary to address delay-sensitive applications (as is specified in the
 codec requirement document), we can also have a low-complexity mode to
 address complexity-sensitive applications such as low- end/mobile devices
 and gateways. It is for such a low-complexity mode that 10 - 20 MIPS is a
 good target to shoot for, at least for narrowband and wideband. (Super-
 wideband and full-band can be layered coding on top of that and do not
 need to be subject to this 10 - 20 MIPS target.) For other coding modes
 that require more processing power, this 10 - 20 MIPS target obviously
 would not apply.

 Also, if we don't like to have too many different coding modes, and if
 some modes can be combined, for example, if the low-delay mode can also
 achieve low complexity, then we can combine the low-delay mode and the
 low-complexity mode into a single mode.  We can have another mode that's
 more efficient in bit-rate but may have higher delay and complexity to
 address those applications that are less sensitive to delay and
 complexity.

 [JM]: Oh, I realise your original message did not state 10-20 MIPS as the
 target for all modes. My only questions was about how you came to the
 10-20 MIPS figure in the first place. Any DSP vendor(s) roadmap or
 something? Or what would be the relevant existing DSP for which we could
 extrapolate future performance? As I said, I'm not too familiar about the
 DSPs used in Bluetooth because all the regular DSPs I can find are 50 MIPS
 or above.

 [Raymond]: Bluetooth headsets normally don't use general-purpose DSPs from
 those traditional DSP houses that you mentioned below.  A lot of mid- to
 low-end Bluetooth headsets (where most of the shipping volume is) don't
 even have any DSP and instead just rely on an ARM processor to do all
 voice/audio processing and Bluetooth protocol stack.  The 5 MIPS number
 for current-generation BT headsets was quoted to me by an experienced
 Bluetooth audio engineering manager in terms of MIPS on an ARM processor,
 but since most speech coding engineers are more familiar with the MIPS for
 a general-purpose 16-bit fixed-point DSP, so I converted the MIPS on an
 ARM to the equivalent MIPS on a fixed-point DSP, and it came to around 5
 MIPS.  The 10 to 20 MIPS number is what we may expect in a several years
 as Moore's Law helps to increase the processing power of Bluetooth
 headsets.

 High-end Bluetooth headset chips may have a DSP on-chip, but it is usually
 either a proprietary DSP or a DSP core not from the traditional DSP houses
 but from companies like ARM.

 One thing to keep in mind, though, is that even if you have a DSP on a
 Bluetooth headset chip, and it is clocked at 50 MHz or higher, it doesn't
 mean that you can use all or most of that DSP processing power for speech
 or audio coding.  This is because it has to handle many other signal
 processing tasks such as acoustic echo canceller, single-mic or multi-mic
 noise suppression, wind noise suppression, packet loss concealment, voice
 prompt decoding, and even voice command recognition, to name just a few.
 You can't even get half of the DSP processing power solely dedicated to
 speech coding.  You will be lucky if you can get 20% of the DSP for speech
 coding.  Remember that currently the speech coding part (CVSD codec) takes
 0% of the DSP or ARM because it is done in chip hardware.

 [Christan]: what do you think about STL2005/9 described in ITU-T G.191. It
 might be a good metric to measure the codec performance in low-complexity
 mode. STL2009 is not yet published officially but the STL 2005 manual is
 available for free.
 http://www.itu.int/rec/T-REC-G.191-200508-I/en
 Chapter 13, Page 159 describes a set of basic operator and their
 complexity weights. STL2009 is similar but has guidelines on data movement
 and program ROM estimation tool for fixed-point c code and a complexity
 evaluation tool for floating-point C Code.

 However, STL2005 might not be optimal for soft-phone complexity prediction
 because many operations have overflow control and saturation, that
 typically cannot be translated into a single native assembler instruction.
 Thus, for soft-phone I would recommend to use slightly modified
 measures...

 [Raymond]:
 The ITU-T software tool library has been used to measure the complexity of
 many fixed-point standard speech codecs, and we have done that, too.  So,
 yes, I think it is a good and well-accepted way to measure the complexity
 of fixed-point codecs.

 For floating-point implementations, although I don't know of a similar
 software tool for complexity measurement, it is not that difficult to do
 something similar and add some complexity counting code to an existing
 floating-point C code to measure the complexity of a floating-point codec.

-- 
Ticket URL: <http://trac.tools.ietf.org/wg/codec/trac/ticket/20#comment:2>
codec <http://tools.ietf.org/codec/>