Subject: Re: [MMUSIC] [Fecframe] Flexible FEC grouping and associations

From: Mark Watson <[email-masked]>
Date: Fri, 01 Feb 2008 08:47:13 -0800

Thomas,

This is like the example given by Ali, where there are two source flows (#1
and #2) and two repair flows (which I will call #A and #B). #A protects
source flow #1 and #B protects source flow #1 and #2.

#A and #B may or may not be additive, meaning that they could be combined
into a single decoding operation (in your example they can). However, either
way, there is no "dependency" between #A and #B in the sense that there is a
dependency between #1 and #2. #B is perfectly useful to recover data from #1
and #2 without #A. However #2 is of no use without #1.

So the relationship between #A and #B is different in character from that
between #1 and #2 which is why we did not want to use the same dependency
syntax for both.

I don't think it's quite correct to say that this approach can never be
worse than traditional FEC. Suppose #A uses an ( n1, k1 ) code, #B is an (
n2, k1+k2 ) code (so #1 has k1 source symbols and #2 has k2 source symbols).
One would send n1+n2-k1 symbols (since we do not want to send the k1 source
symbols of #1 twice). So, overall we have an ( n1+n2-k1, k1+k2 ) code.

For a traditional code, the best possible is that receipt of any k1+k2
symbols from the n1+n2-k1 sent symbols will allow recovery of the source.
And of course such codes exist. However the layered code cannot have this
property. For example, suppose I receive k1+k2 symbols, k1+1 of which are
from #1/#A. Assuming ideal codes, I can recover #1 using just k1 of the
symbols from #1/#A. The additional symbol is redundant. Thus I have only
k1+k2-1 symbols of real information towards the second code which therefore
cannot recover.

...Mark

On 1/31/08 11:19 AM, "Thomas Wiegand" <[email-masked]> wrote:

> Mark,
> 
> Layer-based FEC (L-FEC), as we refer to it, is a new method where the
> layer-dependencies of a scalable codec are taken into account.
> 
> By a layered codec, I mean a codec consisting of a hierarchy of layers
> with one layer being the base layer and each enhancement layer
> linearly  is building on top of it.
> 
> The concept of L-FEC then attempts to solve the core problem when
> protecting a layered codec: You have to make sure that all layers are
> available on which the highest layer that you access depends on .
> 
> Let me explain how L-FEC solves this by using an example.
> 
> Let's assume for simplicity that we have two layers each consisting of
> 3 information bits.
> 
> Base layer: '001'
> Enhancement layer: '110'
> 
> Let's assume the protection is an XOR operation and 2 parity bits are
> produced through an XOR operation.
> 
> In a traditional scheme, we would be XORing for the 1. parity bit the
> 1. and 2. bit of the 3 bits and for the 2. parity bit the 1. and 3.
> bit of the 3 bits of the base layer. To obtain both parity bits of the
> enhancement layer we would do the corresponding operation there: for
> the 1. parity bit, the 1. and 2. bit of the 3 bits are XORed and for
> the 2. parity bit, the 1. and 3. bit of the 3 bits of the enhancement
> layer are XORed.
> * For the base layer, we get
> 1. parity bit: 0 XOR 0 = 0
> 2. parity bit: 0 XOR 1 = 1
> * For the enhancement layer we get
> 1. parity bit: 1 XOR 1 = 0
> 2. parity bit: 1 XOR 0 = 1
> If in this case the problem that you correctly referred is occurring
> when 3 bits of the base layer are lost. Then the base layer cannot be
> decoded and the enhancement layer is useless even if it is correctly
> received in its entirety.
> 
> L-FEC solves this as follows:
> * For the base layer, we perform the exact same XOR operation as in
> traditional FEC:
> 1. parity bit: 0 XOR 0 = 0
> 2. parity bit: 0 XOR 1 = 1
> * For the enhancement layer, however, we also include the base layer
> into the XOR operation. This is done, for example, by applying the XOR
> operation to the 1. and 3. bit of the base layer and the 1. and 2. bit
> of the enhancement layer jointly to produce the first parity bit. For
> the second parity bit, the example could be to apply the XOR operation
> to the 2. bit of the base layer and the 1. and 3. bit of the
> enhancement layer.
> 1. parity bit: 0 XOR 1 XOR 1 XOR 1 = 1
> 2. parity bit: 0 XOR 1 XOR 0 = 1
> If in this case the problem occurs and 3 bits of the base layer are
> lost, then the base layer CAN be decoded since the enhancement layer
> parity bits can be used to correct the errors.
> 
> Please note that L-FEC can never be worse than traditional FEC as
> described above in terms of error correction capability. The price to
> pay is more complexity.
> 
> I hope the example makes clear what we mean by L-FEC. (I have also
> attached a JPEG picture that illustrates the example that I have
> described above)
> 
> L-FEC has been developed at HHI by Cornelius Hellge, Thomas Schierl
> and me.
> 
> Best Regards,
> Thomas Wiegand
> 
> ----
> Visit us at
> 
> GSMA Mobile World Congress / Barcelona, Spain / 11 - 14 February 2008 /
> Broadcast Mobile Convergence Forum / Booth 2B82
> http://www.mobileworldcongress.com/homepage.htm
> 
> OFC 2008 / San Diego, California, USA / 26 - 28 February 2008 / Booth 411/415
> http://www.ofcnfoec.org
> 
> 
> ---
> Thomas Wiegand, Dr.-Ing.
> Head, Image Communication Group
> Image Processing Department
> Fraunhofer Inst. for Telecommunications - HHI
> Einsteinufer 37, D-10587 Berlin, Germany
> Phone: +49 30 31002 617,
> Mobile: +49 172 381 3814
> http: iphome.hhi.de/wiegand
> ---
> 
> 
> 
> On Jan 31, 2008, at 7:14 PM, Mark Watson wrote:
> 
>> Thomas,
>> 
>> What do you actually mean by "layered FEC" ?
>> 
>> Certainly there is a concept of multiple FEC layers which makes
>> sense, and
>> in fecframe we have discussed this. This is what Ali refers to below
>> as
>> additivity - where multiple FEC streams can be usefully decoded in
>> combination.
>> 
>> However it's a very different concept from layering in the sense of a
>> layered video codec. In SVC, you absolutely need the base layer in
>> order to
>> make sense of the enhancement layer. This is not (cannot!) be true
>> for FEC
>> "layers" because the whole point of FEC is to deal with losses - the
>> possibility of the "base layer" packets being lost must be accepted.
>> The
>> "enhancement layer" is thus useful on its own.
>> 
>> Put another way, there can be no "dependency" between FEC layers and
>> this is
>> why we thought it would not be correct to use the layer option in your
>> dependency draft for FEC.
>> 
>> In fact FEC "layers" are closer in concept to MDC, but this does not
>> capture
>> the point that, despite the absence of dependency, there may still
>> be a
>> notion of preference amongst the layers.
>> 
>> There is of course a notion of dependency between source flows and
>> an FEC
>> repair flow that protects them.
>> 
>> ...Mark
>> 
>> 
>> 
>> 
>> On 1/31/08 9:42 AM, "Thomas Schierl" <[email-masked]> wrote:
>> 
>>> Hi Ali,
>>> 
>>> 
>>> One comment, we think that layered FEC does make sense. There may
>>> be future
>>> applications, which code the media and the FEC in a layered fashion.
>>> 
>>> You may be right that from the current viewpoint layered FECs may
>>> not be of
>>> much use.  But currently no one is using layered codecs. That may
>>> change,
>>> since there is now an efficient scalable codec for video. And in
>>> that case,
>>> your assumption may not hold.
>>> 
>>> So, why not supporting this additional feature?
>>> 
>>> 
>>> Thomas
>>> 
>>> 
>>>> -----Original Message-----
>>>> From: Ali Begen (abegen) [mailto:[email-masked]]
>>>> Sent: Wednesday, January 30, 2008 10:53 PM
>>>> To: [email-masked]
>>>> Cc: [email-masked]; [email-masked]; [email-masked]
>>>> Subject: [Fecframe] Flexible FEC grouping and associations
>>>> 
>>>> Hi everyone,
>>>> 
>>>> In Vancouver, we gave a brief introduction on this issue in MMUSIC
>>>> and
>>>> the chairs asked us to examine the existing drafts/RFCs before going
>>>> any
>>>> further.
>>>> 
>>>> In yesterday's FECFRAME design team meeting, we discussed this topic
>>>> and
>>>> concluded that in terms of what we would like to support in
>>>> FECFRAME,
>>>> existing RFCs/drafts were not helping us much. We examined RFC 3388,
>>>> RFC
>>>> 4756, and draft-ietf-mmusic-decoding-dependency-00.
>>>> 
>>>> Here is the summary.
>>>> 
>>>> We would like to support the following:
>>>> 1- A source flow MAY be protected by multiple FEC schemes
>>>> 2- An FEC scheme MAY generate multiple repair flows
>>>> 3- Source flows MAY be grouped prior to FEC protection (One or more
>>>> repair flows can protect a group of source flows)
>>>> 
>>>> The Grouping/Association Problem:
>>>> RFC 3388 states that an "m" line identified by its "mid" attribute
>>>> MUST
>>>> NOT appear in more than one "a=group" line using the same semantics.
>>>> So,
>>>> the FEC grouping semantics (RFC 4756) requires us to put every
>>>> source
>>>> and repair flow in one "group:FEC" line. This is severely limiting
>>>> as
>>>> it
>>>> becomes difficult to associate the source flows with the repair
>>>> flows,
>>>> and/or group them.
>>>> 
>>>> Does anybody remember what the main reason was for this requirement?
>>>> 
>>>> A very simple example:
>>>> Source #1: Base-layer video
>>>> Source #2: Enhancement-layer video
>>>> FEC Scheme #1: Produces Repair #1 that protects Source #1, and
>>>> Repair
>>>> #2
>>>> that protects the group of Source #1 and #2
>>>> 
>>>> RFC 3388 requires us to say
>>>> a=group:FEC S1 S2 R1 R2,
>>>> 
>>>> However, this does not say anything about which repair flow(s) is
>>>> protecting which source flow(s). A new generalized grouping
>>>> attribute
>>>> ("a=gengroup") would help this problem by allowing an "m" line to
>>>> appear
>>>> multiple times in the same grouping semantics. Then, we could write
>>>> 
>>>> a=gengroup:FEC S1 R1
>>>> a=gengroup:FEC S1 S2 R2
>>>> 
>>>> However, we do need additional mechanisms for:
>>>> 
>>>> The Additivity Problem:
>>>> We would like to support additive repair flows (multiple repair
>>>> flows
>>>> can be decoded jointly to improve decoding rate). Note that we don't
>>>> need layered dependency among the repair flows. Source flows might
>>>> be
>>>> layered encoded, but we don't think layered encoded FEC streams are
>>>> much
>>>> of use.
>>>> 
>>>> Currently, there is no support for additivity from existing
>>>> documents.
>>>> decoding-dependency draft offers "mdc" dependency relation, however,
>>>> (i)
>>>> using the keyword "mdc" is not very suitable for FEC, and (ii) the
>>>> draft
>>>> is only intended for RTP flows.
>>>> 
>>>> The Prioritization Problem:
>>>> We would like to support prioritization of the repair flows. The
>>>> sender
>>>> can assign different priorities to different repair flows and we
>>>> require
>>>> the receivers to act accordingly. However, there is no support for
>>>> prioritization from existing documents.
>>>> 
>>>> One option is of course to define new stuff specific to our needs in
>>>> the
>>>> FECFRAME WG, however, we believe it is for everybody's benefit to
>>>> coordinate this effort with MMUSIC and address these issues in a
>>>> more
>>>> general way as they may be required by other frameworks/
>>>> applications.
>>>> 
>>>> We would like to get everybody's opinion on this issue.
>>>> 
>>>> Thanks,
>>>> -acbegen
>>>> 
>>>> _______________________________________________
>>>> Fecframe mailing list
>>>> [email-masked]
>>>> https://www1.ietf.org/mailman/listinfo/fecframe
>>> 
>>> 
>>> 
>>> ----
>>> Visit us at
>>> 
>>> GSMA Mobile World Congress / Barcelona, Spain / 11 - 14 February
>>> 2008 /
>>> Broadcast Mobile Convergence Forum / Booth 2B82
>>> http://www.mobileworldcongress.com/homepage.htm
>>> 
>>> OFC 2008 / San Diego, California, USA / 26 - 28 February 2008 /
>>> Booth 411/415
>>> http://www.ofcnfoec.org
>>> 
>>> _______________________________________________
>>> Fecframe mailing list
>>> [email-masked]
>>> https://www1.ietf.org/mailman/listinfo/fecframe
>>> 
>> 
>> 
> 

_______________________________________________
mmusic mailing list
[email-masked]
http://www.ietf.org/mailman/listinfo/mmusic

---

From: "Ali Begen (abegen)" <[email-masked]>
Date: Fri, 1 Feb 2008 15:56:17 -0800

I agree with Mark's comments. Any dependency between the FEC streams MAY
cause a decoding failure even for a successfully received FEC stream
just because its ancestor FEC stream is missing. 

We are all aware that layering offers good network-adaptive transmission
for the source flows, but it does not do so for the FEC streams. If one
is receiving all source layers, he may choose to receive the FEC for the
base layer only, or a single FEC stream that protects all the source
layers together, or multiple (preferably additive)
independently-decodable FEC streams. 

There is an interesting paper, which I believe, might be useful from an
information theory perspective..
http://research.microsoft.com/~helenw/papers/ChouWP03.pdf

If you don't have time to go through the whole paper, you may get the
picture from the introduction and conclusion sections.

BR,
-acbegen

> From: Mark Watson [mailto:[email-masked]] 
> Sent: Friday, February 01, 2008 8:47 AM
> To: Thomas Wiegand
> Cc: Thomas Schierl; Ali Begen (abegen); [email-masked]; 
> [email-masked]; [email-masked]; 
> [email-masked]; [email-masked]
> Subject: Re: [Fecframe] Flexible FEC grouping and associations
> 
> Thomas,
> 
> This is like the example given by Ali, where there are two 
> source flows (#1 and #2) and two repair flows (which I will 
> call #A and #B). #A protects source flow #1 and #B protects 
> source flow #1 and #2.
> 
> #A and #B may or may not be additive, meaning that they could 
> be combined into a single decoding operation (in your example 
> they can). However, either way, there is no "dependency" 
> between #A and #B in the sense that there is a dependency 
> between #1 and #2. #B is perfectly useful to recover data 
> from #1 and #2 without #A. However #2 is of no use without #1.
> 
> So the relationship between #A and #B is different in 
> character from that between #1 and #2 which is why we did not 
> want to use the same dependency syntax for both.
> 
> I don't think it's quite correct to say that this approach 
> can never be worse than traditional FEC. Suppose #A uses an ( 
> n1, k1 ) code, #B is an ( n2, k1+k2 ) code (so #1 has k1 
> source symbols and #2 has k2 source symbols).
> One would send n1+n2-k1 symbols (since we do not want to send 
> the k1 source symbols of #1 twice). So, overall we have an ( 
> n1+n2-k1, k1+k2 ) code.
> 
> For a traditional code, the best possible is that receipt of 
> any k1+k2 symbols from the n1+n2-k1 sent symbols will allow 
> recovery of the source.
> And of course such codes exist. However the layered code 
> cannot have this property. For example, suppose I receive 
> k1+k2 symbols, k1+1 of which are from #1/#A. Assuming ideal 
> codes, I can recover #1 using just k1 of the symbols from 
> #1/#A. The additional symbol is redundant. Thus I have only
> k1+k2-1 symbols of real information towards the second code which 
> k1+therefore
> cannot recover.
> 
> ...Mark
> 
> > 1. parity bit: 0 XOR 1 XOR 1 XOR 1 = 1 2. parity bit: 0 XOR 
> 1 XOR 0 = 
> > 1 If in this case the problem occurs and 3 bits of the base 
> layer are 
> > GSMA Mobile World Congress / Barcelona, Spain / 11 - 14 
> February 2008 
> > / Broadcast Mobile Convergence Forum / Booth 2B82 
> > OFC 2008 / San Diego, California, USA / 26 - 28 February 
> 2008 / Booth 
> > 411/415 http://www.ofcnfoec.org
> > 
> > 
> > ---
> > Thomas Wiegand, Dr.-Ing.
> > Fraunhofer Inst. for Telecommunications - HHI Einsteinufer 
> 37, D-10587 
> > Berlin, Germany
> > Phone: +49 30 31002 617,
> > Mobile: +49 172 381 3814
> >> sense, and in fecframe we have discussed this. This is what Ali 
> >> refers to below as additivity - where multiple FEC streams can be 
> >> usefully decoded in combination.
> >> 
> >> order to make sense of the enhancement layer. This is not 
> (cannot!) 
> >> be true for FEC "layers" because the whole point of FEC is to deal 
> >> with losses - the possibility of the "base layer" packets 
> being lost 
> >> must be accepted.
> >> The
> >> this is why we thought it would not be correct to use the layer 
> >> option in your dependency draft for FEC.
> >> 
> >> capture the point that, despite the absence of dependency, 
> there may 
> >> still be a notion of preference amongst the layers.
> >> 
> >> There is of course a notion of dependency between source 
> flows and an 
> >> FEC repair flow that protects them.
> >> 
> >> ...Mark
> >> 
> >> 
> >> 
> >> 
> >>> One comment, we think that layered FEC does make sense. 
> There may be 
> >>> future applications, which code the media and the FEC in 
> a layered 
> >>> fashion.
> >>> 
> >>> not be of much use.  But currently no one is using 
> layered codecs. 
> >>> That may change, since there is now an efficient scalable 
> codec for 
> >>> video. And in that case, your assumption may not hold.
> >>> 
> >>>> and the chairs asked us to examine the existing 
> drafts/RFCs before 
> >>>> going any further.
> >>>> 
> >>>> In yesterday's FECFRAME design team meeting, we discussed this 
> >>>> topic and concluded that in terms of what we would like 
> to support 
> >>>> in FECFRAME, existing RFCs/drafts were not helping us much. We 
> >>>> examined RFC 3388, RFC 4756, and 
> >>>> draft-ietf-mmusic-decoding-dependency-00.
> >>>> 
> >>>> Here is the summary.
> >>>> 
> >>>> MUST NOT appear in more than one "a=group" line using the same 
> >>>> semantics.
> >>>> So,
> >>>> source and repair flow in one "group:FEC" line. This is severely 
> >>>> limiting as it becomes difficult to associate the source 
> flows with 
> >>>> the repair flows, and/or group them.
> >>>> 
> >>>> appear multiple times in the same grouping semantics. Then, we 
> >>>> could write
> >>>> 
> >>>> a=gengroup:FEC S1 R1
> >>>> a=gengroup:FEC S1 S2 R2
> >>>> 
> >>>> flows can be decoded jointly to improve decoding rate). 
> Note that 
> >>>> we don't need layered dependency among the repair flows. Source 
> >>>> flows might be layered encoded, but we don't think 
> layered encoded 
> >>>> FEC streams are much of use.
> >>>> 
> >>>> draft is only intended for RTP flows.
> >>>> 
> >>>> sender can assign different priorities to different repair flows 
> >>>> and we require the receivers to act accordingly. 
> However, there is 
> >>>> no support for prioritization from existing documents.
> >>>> 
> >>>> One option is of course to define new stuff specific to 
> our needs 
> >>>> in the FECFRAME WG, however, we believe it is for everybody's 
> >>>> benefit to coordinate this effort with MMUSIC and address these 
> >>>> issues in a more general way as they may be required by other 
> >>>> frameworks/ applications.
> >>>> 
> >>> Booth 411/415 http://www.ofcnfoec.org
> >>>

---

From: Thomas Wiegand <[email-masked]>
Date: Sat, 2 Feb 2008 10:36:37 +0100

We don't talk about such dependencies between FEC streams.

But in a layered codec, the FEC of the enhancement layer should always  
cover the information bits/packets of the base layer.

Best Regards,
Thomas

----
Visit us at

GSMA Mobile World Congress / Barcelona, Spain / 11 - 14 February 2008 / Broadcast Mobile Convergence Forum / Booth 2B82
http://www.mobileworldcongress.com/homepage.htm

---

From: "Michael Luby" <[email-masked]>
Date: Sat, 2 Feb 2008 10:58:34 -0600

One comment (***) below.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf
Of Thomas Wiegand
Sent: Saturday, February 02, 2008 1:37 AM
To: Ali Begen (abegen)
Cc: [email-masked]; [email-masked]; [email-masked];
[email-masked]; Thomas Schierl; [email-masked]
Subject: Re: [MMUSIC] [Fecframe] Flexible FEC grouping and associations

*** There are advantages and disadvantages of this.  I'm not sure this
is a "should".

Best Regards,
Thomas

----
Visit us at

OFC 2008 / San Diego, California, USA / 26 - 28 February 2008 / Booth
411/415
http://www.ofcnfoec.org
_______________________________________________
mmusic mailing list
[email-masked]
http://www.ietf.org/mailman/listinfo/mmusic

---

From: Marshall Eubanks <[email-masked]>
Date: Sat, 2 Feb 2008 13:34:08 -0500

Dear Mike;

> *** There are advantages and disadvantages of this.  I'm not sure this

I would agree that it should not be a MUST,
but is there any reason why not to make it a SHOULD ? From RFC 2119

3. SHOULD   This word, or the adjective "RECOMMENDED", mean that there
    may exist valid reasons in particular circumstances to ignore a
    particular item, but the full implications must be understood and
    carefully weighed before choosing a different course.

(I guess it could be a should and not a SHOULD, if you want.)

Regards
Marshall

> http://www.ietf.org/mailman/listinfo/fecframe