text:
# How to make my keywords still get highlighted no matter the breaklines is set to true?

I got a bit of trouble with the listings package. I am trying to highlight a custom language with lstdefinelanguage but for reasons I can't understand, highlighting for my ) keyword, and only the ) keyword, breaks as soon as I enable breaklines in lstset.

I'd expect the keyword ) to get highlighted just like (, +and so on even if breaklines is set to true.

Here's a minimal example to reproduce the issue:

    \documentclass[10pt, leqno]{article}
\usepackage{listings}
\usepackage[usenames,dvipsnames]{color}

\lstdefinelanguage{Test}
{
morekeywords = {), +, (},
alsoletter={), +, (},
}

\lstset{
keywordstyle=\color{red},
breaklines=true % As soon as this is true highlighting for ) breaks
}

\begin{document}
\begin{lstlisting}[language=Test]
)
+
(
A very long line that will get broken A very long line that will get broken A very long line that will get broken A very long line that will get broken
\end{lstlisting}
\end{document}

Is it me doing something wrong or is this a problem with the package?

-
What is your expectation? –  xport Jun 1 '11 at 17:49
That the keyword ) gets highlighted just like (, + and so on no matter what breaklines is set to. –  Stefan H. Jun 1 '11 at 23:31
–  Marco Daniel Jun 6 '11 at 16:58

Here are two solutions. The first uses the beta package version 2 of listings and works out of the box. The second patches listings to avoid the problem. Both use Marco's suggestion of using literate.

Solution with listings2

\documentclass{article}
\usepackage{listings2}
\usepackage{xcolor}

\lstset{
literate={)}{{{\color{red})}}}1 {(}{{{\color{red}(}}}1 {+}{{{\color{red}+}}}1,
keywordstyle=\color{red},
breaklines=true
}

\begin{document}
\begin{lstlisting}
)
+
(
A very long line that (will) get broken A very long line that will get broken A very long line that will get broken A very long line that will get broken
\end{lstlisting}
\end{document}

Notice however that there are a few syntaxic changes between listings and listings2, so you will have to adapt parts of your code.

Solution by patching listings

By removing \lst@ifbreaklines \lst@Def{)}{\lst@breakProcessOther)}\fi from listings's SelectCharTable hook, the problem disappears (it should not have any side effect):

\documentclass{article}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{xstring}

\makeatletter
\noexpandarg % to not expand arguments of \StrSubstitute
\expandafter\StrSubstitute\expandafter{\lsthk@SelectCharTable}{\lst@ifbreaklines \lst@Def{)}{\lst@breakProcessOther)}\fi}{}[\lsthk@SelectCharTable]
\makeatother

\lstset{
literate={)}{{{\color{red})}}}1 {(}{{{\color{red}(}}}1 {+}{{{\color{red}+}}}1,
keywordstyle=\color{red},
breaklines=true
}

\begin{document}
\begin{lstlisting}
)
+
(
A very long line that (will) get broken A very long line that will get broken A very long line that will get broken A very long line that will get broken
\end{lstlisting}
\end{document}

I've used xstring to do the substitution.

-
I am a bit reluctant to use the listings2 package since it doesn't seem like there's much documentation out there. I'd hate to have to stab in the dark because of (maybe subtle) differences between it and the listings package. Also it seems like this package is not part of the standard LaTex distributions. –  Stefan H. Jun 10 '11 at 0:02


text:
It is currently 23 Feb 2018, 04:13

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

# Positive integer n leaves a remainder of 4 after division by

Author Message
TAGS:

### Hide Tags

Veritas Prep GMAT Instructor
Joined: 16 Oct 2010
Posts: 7955
Location: Pune, India
Re: Positive integer n leaves a remainder of 4 after division by [#permalink]

### Show Tags

03 May 2015, 20:27
1
KUDOS
Expert's post
vikasbansal227 wrote:
Dear All,

Its difficult that on what basis we took "First common integer in two patterns" as a remainder for the formula?

Thanks

You want a number, n, that satisfies two conditions:
"leaves a remainder of 4 after division by 6" and
"a remainder of 2 after division by 8"

So you find the first such number by writing down the numbers. You get that it is 10.
10 satisfies both conditions.

What will be the next number?
Any number that is a multiple of 6 more than 10 will continue to satisfy the first condition. e.g. 16, 22, 28, 34 etc
Any number that is a multiple of 8 more than 10 will continue to satisfy the second condition. e.g. 18, 26, 34 etc

So any number that is a multiple of both 6 and 8 more than 10 will satisfy both conditions.
LCM of 6 and 8 is 24. 24 is divisible by both 6 and 8.

So any number that is a multiple of 24 more than 10 will satisfy both conditions.
e.g. 34, 58 .. etc
These numbers can be written as 10 + 24a.

Also, I think you did not check out the 4 links I gave here: positive-integer-n-leaves-a-remainder-of-4-after-division-by-93752-40.html#p1496547
They are very useful in understanding divisibility fundamentals.
_________________

Karishma
Veritas Prep | GMAT Instructor
My Blog

Get started with Veritas Prep GMAT On Demand for $199 Veritas Prep Reviews Director Joined: 10 Mar 2013 Posts: 584 Location: Germany Concentration: Finance, Entrepreneurship GMAT 1: 580 Q46 V24 GPA: 3.88 WE: Information Technology (Consulting) Positive integer n leaves a remainder of 4 after division by [#permalink] ### Show Tags 27 Aug 2015, 00:43 Bunuel wrote: bchekuri wrote: Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30? (A) 3 (B) 12 (C) 18 (D) 22 (E) 28 How to approach this Problem? Positive integer n leaves a remainder of 4 after division by 6 --> $$n=6p+4$$ --> 4, 10, 16, 22, 28, ... Positive integer n leaves a remainder of 3 after division by 5 --> $$n=5q+3$$ --> 3, 8, 13, 18, 23, 28, ... $$n=30k+28$$ - we have 30 as lcm of 5 and 6 is 30 and we have 28 as the first common integer in the above patterns is 28. Hence remainder when positive integer n is divided by 30 is 28. Answer: E. P.S. n>30 is a redundant information. Hi Bunuel, do you think this is a valid approach for this type of questions in general ? I prefer algebra to number picking. Question 1 n=6p+4, n=5q+3 --> 6p+4=5q+3 -> 6p+1=5q -> 5p +(p+1)=5q, so p+1 must be a multiple of 5, means P=4,9,14 etc... if p=4: 6p+4=28 -> q=5:5*5+3=28 => 28 is the first common number 28/30=0+28(R) Answer (E) Question 2 n=6p+4, n=8q+2 /divide by 2 both expressions => 3q+(q-1)=3p q-1 must be a multiple of 3: 4,10,16 etc... let's pick 4 for q 8*4+2=34 --> 34/12=2*12+10(R) _________________ When you’re up, your friends know who you are. When you’re down, you know who your friends are. Share some Kudos, if my posts help you. Thank you ! 800Score ONLY QUANT CAT1 51, CAT2 50, CAT3 50 GMAT PREP 670 MGMAT CAT 630 KAPLAN CAT 660 Current Student Joined: 11 Oct 2013 Posts: 120 Concentration: Marketing, General Management GMAT 1: 600 Q41 V31 Positive integer n leaves a remainder of 4 after division by [#permalink] ### Show Tags 14 Dec 2015, 04:31 Bunuel wrote: To elaborate more. Suppose we are told that: Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 2 after division by 8. What is the remainder that n leaves after division by 12? The statement "positive integer n leaves a remainder of 4 after division by 6" can be expressed as: $$n=6p+4$$. Thus according to this particular statement $$n$$ could take the following values: 4, 10, 16, 22, 28, 34, 40, 46, 52, 58, 64, ... The statement "positive integer n leaves a remainder of 2 after division by 8" can be expressed as: $$n=8q+2$$. Thus according to this particular statement $$n$$ could take the following values: 2, 10, 18, 26, 34, 42, 50, 58, 66, ... The above two statements are both true, which means that the only valid values of $$n$$ are the values which are common in both patterns. For example $$n$$ can not be 16 (from first pattern) as the second formula does not give us 16 for any value of integer $$q$$. So we should derive general formula (based on both statements) that will give us only valid values of $$n$$. How can these two statement be expressed in one formula of a type $$n=kx+r$$? Where $$x$$ is divisor and $$r$$ is a remainder. Divisor $$x$$ would be the least common multiple of above two divisors 6 and 8, hence $$x=24$$. Remainder $$r$$ would be the first common integer in above two patterns, hence $$r=10$$. Therefore general formula based on both statements is $$n=24k+10$$. Thus according to this general formula valid values of $$n$$ are: 10, 34, 58, ... Now, $$n$$ divided by 12 will give us the reminder of 10 (as 24k is divisible by 12). Hope it helps. Thanks for the great explanation Bunuel. I have a doubt though. This seems to be valid when the final divisor mentioned in the question is a factor of LCM of the previous divisors. Are there any cases, where this would not be true? As in what if the question asked for divisibility by 14? i.e remainder of 24k+10 when divided by 14? _________________ Its not over.. Intern Joined: 21 Dec 2012 Posts: 4 Re: Positive integer n leaves a remainder of 4 after division by [#permalink] ### Show Tags 09 Apr 2016, 06:26 How do we solve a question which has different remainder ? because in this case remainder is -2 , ie common to both the cases? What happens to the case when both the case have different remainder ? muralimba wrote: Friends, IT IS VERY COMMON IN GMAT to solve this kind of qtns using "NEGATIVE REMAINDER" theory. The theory says: if a # x is devided by y and leave the positive # r as the remainder then it can also leave negative # (r-y) as the remainder. e.g: 9 when devided by 5 leves the remainder 4 : 9=5*1+4 it can also leave the remainder 4-5 = -1 : 9=5*2 -1 back to the original qtn: n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5 ==> n leaves a remainder of -2 (i.e. 4-6) after division by 6 and a remainder of -2 (i.e. 3-5) after division by 5 ==> n when devided by 5 and 6 leaves the same remainder -2. what is n? LCM (5,6)-2 = 30-2 = 28 CHECK: 28 when devided by 6 leaves the remainder 4 and when devided by 5 leaves the remainder 3 However, the qtn says n > 30 so what is the nex #, > 28, that can give the said remainders when devided by 6 and 5 nothing but 28 + (some multiple of 6 and 5) as this "some multiple of 6 and 5" will not give any remainder when devided by 5 or 6 but 28 will give the required remainders. hence n could be anything that is in the form 28 + (some multiple of 6 and 5) observe that "some multiple of 6 and 5" is always a multiple of 30 as LCM (5,6) = 30. hence when n (i.e. 28 + some multiple of 6 and 5) is devided by 30 gives the remainder 28. ANSWER "E" Regards, Murali. Kudos? Director Joined: 07 Dec 2014 Posts: 907 Re: Positive integer n leaves a remainder of 4 after division by [#permalink] ### Show Tags 31 Aug 2016, 19:11 r1=4 d1=6 r2=3 d2=5 n=r1+d1(d2-1) n=4+6(4)=28 next higher value of n=28+d1*d2=58 58/30 leaves a remainder of 28 Veritas Prep GMAT Instructor Joined: 16 Oct 2010 Posts: 7955 Location: Pune, India Re: Positive integer n leaves a remainder of 4 after division by [#permalink] ### Show Tags 31 Aug 2016, 20:07 happy19 wrote: How do we solve a question which has different remainder ? because in this case remainder is -2 , ie common to both the cases? What happens to the case when both the case have different remainder ? Check out this post. It discusses how to handle questions in which the remainders are different. http://www.veritasprep.com/blog/2011/05 ... s-part-ii/ _________________ Karishma Veritas Prep | GMAT Instructor My Blog Get started with Veritas Prep GMAT On Demand for$199

Veritas Prep Reviews

Intern
Joined: 01 Sep 2016
Posts: 9
Re: Positive integer n leaves a remainder of 4 after division by [#permalink]

### Show Tags

05 Oct 2016, 11:23
n = 6d + 4
n = 5d + 3

if we multiply the first equation by 5 and the second by 6 we get

5n = 30d + 20 (1)
6n = 30d + 18 (2)

if we make (1) - (2)

-n = 2; n = -2

so -2/30 has a remainder of 28
Senior Manager
Joined: 13 Oct 2016
Posts: 367
GPA: 3.98
Positive integer n leaves a remainder of 4 after division by [#permalink]

### Show Tags

03 Dec 2016, 06:59
1
This post was
BOOKMARKED
bchekuri wrote:
Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30?

A. 3
B. 12
C. 18
D. 22
E. 28

$$N=4$$ (mod 6)
$$N= 3$$ (mod 5)

The difference between divisor and remainder is the same for both linear congruences

$$6 -4 = 5 - 3 = 2 = D$$

Hence our N can b represented as:

N = LCM (6, 5)*X - D, where X is >=0 and D is our common differnce.

$$N = 30X - 2$$ X=0 ---> N=28

and for N>30

$$\frac{30*X - 2}{30} = \frac{0 - 2}{30}$$ = $$-2$$ (mod 30) = $$28$$ (mod 30)

Manager
Joined: 19 Aug 2016
Posts: 150
Location: India
GMAT 1: 640 Q47 V31
GPA: 3.82
Positive integer n leaves a remainder of 4 after division by [#permalink]

### Show Tags

16 Jan 2017, 12:08
Bunuel wrote:
To elaborate more.

Suppose we are told that:
Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 2 after division by 8. What is the remainder that n leaves after division by 12?

The statement "positive integer n leaves a remainder of 4 after division by 6" can be expressed as: $$n=6p+4$$. Thus according to this particular statement $$n$$ could take the following values: 4, 10, 16, 22, 28, 34, 40, 46, 52, 58, 64, ...

The statement "positive integer n leaves a remainder of 2 after division by 8" can be expressed as: $$n=8q+2$$. Thus according to this particular statement $$n$$ could take the following values: 2, 10, 18, 26, 34, 42, 50, 58, 66, ...

The above two statements are both true, which means that the only valid values of $$n$$ are the values which are common in both patterns. For example $$n$$ can not be 16 (from first pattern) as the second formula does not give us 16 for any value of integer $$q$$.

So we should derive general formula (based on both statements) that will give us only valid values of $$n$$.

How can these two statement be expressed in one formula of a type $$n=kx+r$$? Where $$x$$ is divisor and $$r$$ is a remainder.

Divisor $$x$$ would be the least common multiple of above two divisors 6 and 8, hence $$x=24$$.

Remainder $$r$$ would be the first common integer in above two patterns, hence $$r=10$$.

Therefore general formula based on both statements is $$n=24k+10$$. Thus according to this general formula valid values of $$n$$ are: 10, 34, 58, ...

Now, $$n$$ divided by 12 will give us the reminder of 10 (as 24k is divisible by 12).

Hope it helps.

Thanks for the amazing concept. I just have one more query:

How will we apply this approach for questions such as:

What is the remainder when the positive integer n is divided by 12?

1. When n is divided by 6, the remainder is 1.

2. When n is divided by 12, the remainder is greater than 5.
_________________

Consider giving me Kudos if you find my posts useful, challenging and helpful!

Math Expert
Joined: 02 Sep 2009
Posts: 43892
Re: Positive integer n leaves a remainder of 4 after division by [#permalink]

### Show Tags

16 Jan 2017, 23:54
ashikaverma13 wrote:
Bunuel wrote:
To elaborate more.

Suppose we are told that:
Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 2 after division by 8. What is the remainder that n leaves after division by 12?

The statement "positive integer n leaves a remainder of 4 after division by 6" can be expressed as: $$n=6p+4$$. Thus according to this particular statement $$n$$ could take the following values: 4, 10, 16, 22, 28, 34, 40, 46, 52, 58, 64, ...

The statement "positive integer n leaves a remainder of 2 after division by 8" can be expressed as: $$n=8q+2$$. Thus according to this particular statement $$n$$ could take the following values: 2, 10, 18, 26, 34, 42, 50, 58, 66, ...

The above two statements are both true, which means that the only valid values of $$n$$ are the values which are common in both patterns. For example $$n$$ can not be 16 (from first pattern) as the second formula does not give us 16 for any value of integer $$q$$.

So we should derive general formula (based on both statements) that will give us only valid values of $$n$$.

How can these two statement be expressed in one formula of a type $$n=kx+r$$? Where $$x$$ is divisor and $$r$$ is a remainder.

Divisor $$x$$ would be the least common multiple of above two divisors 6 and 8, hence $$x=24$$.

Remainder $$r$$ would be the first common integer in above two patterns, hence $$r=10$$.

Therefore general formula based on both statements is $$n=24k+10$$. Thus according to this general formula valid values of $$n$$ are: 10, 34, 58, ...

Now, $$n$$ divided by 12 will give us the reminder of 10 (as 24k is divisible by 12).

Hope it helps.

Thanks for the amazing concept. I just have one more query:

How will we apply this approach for questions such as:

What is the remainder when the positive integer n is divided by 12?

1. When n is divided by 6, the remainder is 1.

2. When n is divided by 12, the remainder is greater than 5.

This question is discussed here: what-is-the-remainder-when-the-positive-integer-n-is-divided-161170.html
_________________
Senior Manager
Joined: 05 Dec 2016
Posts: 263
Concentration: Strategy, Finance
GMAT 1: 620 Q46 V29
Re: Positive integer n leaves a remainder of 4 after division by [#permalink]

### Show Tags

27 Feb 2017, 05:45
6k+4 => 6k-2
5q+3 => 5q-2
Hence, 30m-2 => -2+ 30 = 28
Manager
Joined: 27 Dec 2016
Posts: 152
Re: Positive integer n leaves a remainder of 4 after division by [#permalink]

### Show Tags

03 Jun 2017, 15:51
Bunuel wrote:
bchekuri wrote:
Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30?
(A) 3
(B) 12
(C) 18
(D) 22
(E) 28

How to approach this Problem?

Positive integer n leaves a remainder of 4 after division by 6 --> $$n=6p+4$$ --> 4, 10, 16, 22, 28, ...
Positive integer n leaves a remainder of 3 after division by 5 --> $$n=5q+3$$ --> 3, 8, 13, 18, 23, 28, ...

$$n=30k+28$$ - we have 30 as lcm of 5 and 6 is 30 and we have 28 as the first common integer in the above patterns is 28.

Hence remainder when positive integer n is divided by 30 is 28.

P.S. n>30 is a redundant information.

Hi Bunuel,

I understood everything up to this point "Hence remainder when positive integer n is divided by 30 is 28" I was wondering could you please explain how you got 28 from this statement? Would greatly appreciate it!!

Thank You!
Director
Joined: 07 Dec 2014
Posts: 907
Re: Positive integer n leaves a remainder of 4 after division by [#permalink]

### Show Tags

03 Jun 2017, 19:58
bchekuri wrote:
Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30?

A. 3
B. 12
C. 18
D. 22
E. 28

assume difference of 1 between n/6 and n/5 quotients
(n-3)/5-(n-4)/6=1
n=28
28+5*6=58
58/30 gives a remainder of 28
E
Intern
Joined: 30 Aug 2017
Posts: 22
Concentration: Real Estate, Operations
Re: Positive integer n leaves a remainder of 4 after division by [#permalink]

### Show Tags

11 Sep 2017, 00:38
I think one easy way to solve this is as follows:
Given: n=6q+4 and n=5p+3
multiply first eq by 5 and 2nd by 6(in order to get 30 as factor in quotient)
therefore we have:
5n=30q+20 (a)
6n=30p+18 (b)

b-a: n=30(p-q)-2
since remainder is -2, positive remainder =30-2=28 (option E)
Re: Positive integer n leaves a remainder of 4 after division by   [#permalink] 11 Sep 2017, 00:38

Go to page   Previous    1   2   3   [ 54 posts ]

Display posts from previous: Sort by

format: plain


text:
Cepstrum

kuniga.me > NP-Incompleteness > Cepstrum

# Cepstrum

23 Oct 2021

Cepstrum is a signal transform that can be used in speech analysis for determining voice pitch, separate formants (transfer function of the vocal tract) from voiced and unvoiced sources, and in mechanics, for example to detect local faults in gear [1].

Cepstrum is a wordplay with Spectrum, obtained by reversing the first four letters, and was coined by John Tukey, pictured on the left. Another interesting fact is that Cepstrum was invented before the FFT [1].

In this post we’ll study the Cepstrum and why it’s a useful tool for dealing with human speech.

## Motivation

Recall from Discrete Filters, that the result of a filter with an impulse response $\vec{h}$ over an input signal $\vec{x}$ can be described by a convolution:

$\vec{y} = \vec{x} * \vec{h}$

Also recall from the Source-Filter Model that the human voice can be modeled via a excitation source $\vec{e}$ (vocal chords, impulse train or noise) going through a filter (vocal tract, which amplifies specific frequencies) with impulse response $\vec{h}$:

$\vec{x} = \vec{e} * \vec{h}$

We only have access to the output signal $\vec{x}$ and it would be desirable to extract the impulse response from this output by removing the noisy signal.

### Homomorphic transform

In Discrete Filters we learned about the Convolution theorem, which says that if $\vec{z} = \vec{x} * \vec{y}$, then their DFTF satisfy $\mathscr{F}(\vec{z}) = \mathscr{F}(\vec{x}) \mathscr{F}(\vec{y})$, that is, the convolution in the time domain becomes a product in frequency domain.

In a similar vein, we could define a transform $\mathscr{C}$ that turns the convolution into a sum:

$\mathscr{C}(\vec{z}) = \mathscr{C}(\vec{x}) + \mathscr{C}(\vec{y})$

Such transforms are called homomorphic (the name means same + form: structure-preserving), and we’ll show the Cepstrum transform satisfies this property. We’ll also denote the Cepstrum of a signal $\vec{x}$ as $\vec{\hat x}$.

### Filtering the source

Suppose we apply the Cepstrum transform to an output signal $\vec{x}$ and now have:

$\vec{\hat x} = \vec{\hat e} + \vec{\hat h}$

For voiced sounds in human speech, the Cepstrum has another important property which we’ll call separability. This means that there exists $N$ such that $\hat h_t \approx 0$ for $t \ge N$ and $\hat e_n \approx 0$ for $t < N$. So if we can find that $N$ and apply a filter to remove the entries with $t > N$ and obtain:

$\hat x_t = \hat h_t \qquad t > N$

We can then apply the inverse of $\mathscr{C}$ to recover $\vec{h} = \mathscr{C}^{-1}(\vec{\hat h})$ or $\vec{e} = \mathscr{C}^{-1}(\vec{\hat e})$. This property is very useful for example in extracting the pitch from human voice.

In the rest of this post we’ll formalize the notion of Cepstrum and then prove its 2 main properties: homomorphism and separability.

## Definition

The complex Cepstrum is defined as:

$\hat x_t = \frac{1}{2 \pi} \int_{-\pi}^{\pi} \ln \mathscr{F}(\vec{x}, \omega) e^{i \omega t} d\omega$

Recalling that $\mathscr{F}(\vec{x}, \omega)$ is the DTFT and is a function of $\omega$:

$\mathscr{F}(\vec{x}, \omega) = \sum_{t = 0}^{N-1} x_t e^{-i \omega t} \quad -\pi \le \omega \le \pi$

We can represent the complex result of the DTFT in polar form, $\mathscr{F}(\vec{x}, \omega) = \abs{\mathscr{F}(\vec{x}, \omega)} e^{i\varphi(\omega)}$, where $\varphi(\omega)$ is the argument/phase of the complex number and depends on $\omega$. The complex natural logarithm is then:

$\ln \mathscr{F}(\vec{x}, \omega) = \ln(\abs{\mathscr{F}(\vec{x}, \omega)}) + i \varphi(\omega)$

If we instead take the (real) logarithm of the absolute value, then result is called the real Cepstrum:

$(1) \quad \hat x_t = \frac{1}{2 \pi} \int_{-\pi}^{\pi} \ln \abs{\mathscr{F}(\vec{x}, \omega)} e^{i \omega t} d\omega$

We can also express (1) using the inverse of the DTFT, $\mathscr{F}^{-1}$, which is defined as:

$\mathscr{F}^{-1}(\lambda(\omega)) = \frac{1}{2 \pi} \int_{-\pi}^{\pi} \lambda(\omega) e^{i \omega t} d\omega$

So we set $\lambda(\omega) = \ln \abs{\mathscr{F}(\vec{x}, \omega)}$, we can write (1) as:

$\hat x_t = \mathscr{F}^{-1}(\ln \abs{\mathscr{F}(\vec{x}, \omega)})$

### Real vs Complex Cepstrum

Note that the real Cepstrum is not the real part of the complex Cepstrum. Since the real Cepstrum is more common in practice, when mentioning Cepstrum without qualifiers we’ll be referring to the real Cepstrum.

We can obtain the real cepstrum from the complex cepstrum via a simple identity, as state in Proposition 1.

Proposition 1. If $\vec{x}$ is real, both the real and complex Cepstrum are real. Further, let $\vec{\hat x}^{C}$ and $\vec{\hat x}^{(R)}$ be the complex and real cepstrum of $\vec{x}$ respectively. Then

$(2) \qquad \hat x^{(R)}_t = \frac{\hat x_t^{(C)} + \hat x_{-t}^{(C)}}{2}$

Proof. See Appendix.

### Quefrency Domain

Recall that in Fourier transforms discussions we refer to the original signal $\vec{x}$ being in the time domain, and its Fourier transform $\mathscr{F}(\vec{x})$ being in the frequency domain.

Now we note that if we didn’t apply the logarithm in (1) before integrating, we’d be applying the inverse of the DTFT:

$x_t = \frac{1}{2 \pi} \int_{-\pi}^{\pi} \mathscr{F}(\vec{x}, \omega) e^{i \omega t} d\omega$

And thus going back to the time domain. But because we did apply the log, the value $\vec{\hat x}$ doesn’t really correspond to the time domain, but instead this domain is defined as the quefrency domain, which is yet another word play, this time with “frequency”.

## Cepstrum is Homomorphic

Let’s compute the Cepstrum of a convolution $\vec{z} = \vec{x} * \vec{y}$ and show that $\vec{\hat z} = \vec{\hat x} + \vec{\hat y}$. We know from the convolution theorem that:

$\mathscr{F}(\vec{z}, \omega) = \mathscr{F}(\vec{x} * \vec{y}, \omega) = \mathscr{F}(\vec{x}, \omega) \mathscr{F}(\vec{y}, \omega)$

Representing them by polar forms we have:

$\mathscr{F}(\vec{z}, \omega) = \abs{\mathscr{F}(\vec{x}, \omega)} \abs{\mathscr{F}(\vec{y}, \omega)} e^{i \varphi_x + \varphi_y}$

Where $\varphi_x$ and $\varphi_y$ are the phases of the DTFT of $\vec{x}$ and $\vec{y}$, respectively.

Taking the logarithm of the absolute value we obtain:

$\ln \abs{\mathscr{F}(\vec{z}, \omega)} = \ln \abs{\mathscr{F}(\vec{x}, \omega)} + \ln \abs{\mathscr{F}(\vec{y}, \omega)}$

Plugging this into (1) we have:

$\hat z_t = \frac{1}{2 \pi} \int_{-\pi}^{\pi} \ln \abs{\mathscr{F}(\vec{z}, \omega)} e^{i \omega t} d\omega = \frac{1}{2 \pi} \int_{-\pi}^{\pi} (\ln \abs{\mathscr{F}(\vec{x}, \omega)} + \ln \abs{\mathscr{F}(\vec{y}, \omega)}) e^{i \omega t} d\omega$

Which can be split into two integrals:

$\hat z_t = \frac{1}{2 \pi} \int_{-\pi}^{\pi} \ln \abs{\mathscr{F}(\vec{x}, \omega)} e^{i \omega t} d\omega + \frac{1}{2 \pi} \int_{-\pi}^{\pi} \ln \abs{\mathscr{F}(\vec{y}, \omega)} e^{i \omega t} d\omega = \hat x_t + \hat y_t$

QED

The same can be proven for the complex Cepstrum.

## Cepstrum of impulse response

We’ll show how to compute the Cepstrum of impulse response, $\vec{\hat h}$, from its rational transfer function $H(z)$. Recall that the DTFT is a special case of the Z-transform, so if we set $z = e^{i \omega}$, then $H(z)$ is the DTFT of the impulse response $\vec{h}$.

Thus we can compute the inverse DTFT of the log of $H(z)$ to obtain $\hat h_t$. By still assuming that $z = e^{i \omega}$, we can use the inverse Z-transform to compute the inverse DTFT of $\ln \abs{H(z)}$ and thus obtain $\vec{\hat h}$:

$(3) \qquad \vec{\hat h} = \mathscr{Z}^{-1} (\ln \abs{H(z)}) \qquad z = e^{i \omega}$

### Revisiting the Rational Transfer Function

In Z-transforms we defined the rational transfer function $H(z)$ as a function of its poles and zeros:

$H(z) = b_0 \frac{\prod_{k = 0}^{M-1} (1 - z_k z^{-1})}{\prod_{k = 0}^{N-1} (1 - p_k z^{-1})}$

Recalling that if $z = z_k$ for any $k \in [0, M-1]$ then $H(z) = 0$ and if $z \rightarrow p_k$, then $H(z) \rightarrow \infty$.

Now we wish to rewrite these products such that all roots $z_k$ and $p_k$ have magnitude less or equal to 1. We split each product into two: for $k \in [0, M_i-1]$ for $\abs{z_k} \le 1$ and $k \in [0, M_o-1]$ for $\abs{z_k} > 1$. Note the index $i$ in $M_i$ stands for inside the unit circle and $o$ in $M_o$ as outside. We split the product in the denominator analogously for $N_i$ and $N_o$.

Now for $\abs{z_k} > 1$ we define $z’_k = \frac{1}{z_k}$. We then rewrite $(1 - z_k z^{-1})$ as $(1 - z’_k z)$ since when $z = z_k$, this expression will yield 0 as before. Thus we can rewrite as:

$(4) \qquad H(z) = b_0 \frac{\prod_{k = 0}^{M_i-1} (1 - z_k z^{-1}) \prod_{k = 0}^{M_o-1} (1 - z_k' z)}{\prod_{k = 0}^{N_i-1} (1 - p_k z^{-1}) \prod_{k = 0}^{N_o-1} (1 - p'_k z)}$

Where $\abs{z_k}, \abs{z’_k}, \abs{p_k}, \abs{p’_k} \le 1$.

### Log of the Rational Transfer Function

Let’s apply log to $H(z)$ and replace by (4). We’ll use the fact that given complex numbers $c$ and $d$, $\ln cd = \ln c + \ln d$.

$(5) \quad \ln H(z) = \ln b_0 + \sum_{k = 0}^{M_i-1} \ln(1 - z_k z^{-1}) + \sum_{k = 0}^{M_o-1} \ln(1 - z_k' z) \\ - \sum_{k = 0}^{N_i-1} \ln(1 - p_k z^{-1}) - \sum_{k = 0}^{N_o-1} \ln(1 - p'_k z)$

We can use the Taylor series expansion to compute the natural logarithm of $\ln(1 - x)$ as in (6):

$(6) \qquad \ln(1-x) = - \sum_{n=1}^{\infty} \frac{x^n}{n}$

Then the sum

$\sum_{k = 0}^{M_i-1} \ln(1 - z_k z^{-1})$

becomes

$\sum_{k = 0}^{M_i-1} \sum_{n=1}^{\infty} - \frac{(z_k z^{-1})^n}{n}$

We can swap the order of the sums and move $\frac{z^{-1}}{n}$ out:

$- \sum_{n=1}^{\infty} \frac{z^{-n}}{n} \sum_{k = 0}^{M_i-1} z_k^n$

We do this for all the four sums in (5), so we can group by the outer sum:

$\ln H(z) = \ln b_0 + \sum_{n=1}^{\infty} \frac{1}{n} \left( - z^{-n} \sum_{k = 0}^{M_i-1} z_k^n - z^n \sum_{k = 0}^{M_o-1} {z'}_k^n + z^{-n} \sum_{k = 0}^{N_i-1} p_k^n + z^n \sum_{k = 0}^{N_o-1} {p'}_k^n \right)$

We can group further the sums that have a factor $z^{-n}$ and $z^{n}$, respectively.

$\ln H(z) = \ln b_0 + \sum_{n=1}^{\infty} \frac{1}{n} \left(z^{-n} (\sum_{k = 0}^{N_i-1} p_k^n - \sum_{k = 0}^{M_i-1} z_k^n) + z^n (\sum_{k = 0}^{N_o-1} {p'}_k^n - \sum_{k = 0}^{M_o-1} {z'}_k^n) \right)$

In this form, it now becomes a bit more apparent we have a power series:

$\sum_{t = -\infty}^{\infty} \alpha_t z^{-t}$

We have $\alpha_0 = \ln b_0$. For $t > 0$, $\alpha_t$ are the sums being multiplied by $z^{-t}$, that is the sums multiplied by $z^{-n}$ when $n=t$:

$\alpha_t = \frac{1}{t} (\sum_{k = 0}^{N_i-1} p_k^t - \sum_{k = 0}^{M_i-1} z_k^t)$

Similarly for $t < 0$ we have:

$\alpha_t = \frac{1}{t} (\sum_{k = 0}^{N_o-1} {p'}_k^t - \sum_{k = 0}^{M_o-1} {z'}_k^t)$

It will soon become clear why we went through all this trouble to define $\ln H(z)$ as a power series.

### The Inverse of the Z-transform for Power Series

In the post about Z-transforms we defined it as:

$(7) \qquad \mathscr{Z}(\vec{x}, z) = \sum_{t = -\infty}^{\infty} x_t z^{-t}$

The inverse of the Z-transform is an operation such that when applied to the Z-transform allows us to recover $\vec{x}$:

$x_t = \mathscr{Z}^{-1}(\mathscr{Z}(\vec{x}, z))$

We won’t cover the general definition of the inverse of the Z-transform in this post. We’ll focus on the special case where the result of a Z-transform can be written as a power series of $z$, then we can use (7) to recover $\vec{x}$.

For example, suppose the Z-transform $\mathscr{Z}(\vec{x}, z)$ is:

$(8) \qquad a z^{-2} + b z^{-1} + c + d z + e z^{2}$

If we set $x_t$ to the coefficient corresponding to the power $z^{-t}$, or more explicitly: $x_{2} = a, x_{1} = b, x_{0} = c, x_{-1} = d, x_{-2} = e$, then we can pad the other entries with 0, and we obtain $\vec{x}$ such that $\mathscr{Z}(\vec{x}, z)$ is (8).

Thus, it’s very easy to find the inverse of the Z-transform for this special case.

### Obtaining the Cepstrum of Impulse

By combining the discussions of the prior section, we can finally obtain $\hat h_t$:

$$$\hat h_t=\left\{ \begin{array}{@{}ll@{}} \ln b_0, & \text{if}\ t = 0 \\ \frac{1}{t} (\sum_{k = 0}^{M_i-1} z_k^t + \sum_{k = 0}^{N_i-1} p_k^t), & \text{if}\ t > 0 \\ \frac{1}{t} (\sum_{k = 0}^{M_o-1} {z'}_k^t - \sum_{k = 0}^{N_o-1} {p'}_k^t), & \text{if}\ t < 0 \\ \end{array}\right.$$$

Since we have $\abs{z_k}, \abs{z’_k}, \abs{p_k}, \abs{p’_k} \le 1$, for sufficiently large values of $\abs{t}$, we’ll be able to approximate $\hat h_{\abs{t}}$ to $0$.

Note that we used the definition of complex cepstrum to show this result, but this can be extended for the real cepstrum by the fact we can obtain the real cepstrum from the complex cepstrum via (2), that is, since $\hat h_{\abs{t}} \approx 0$ for large values of $\abs{t}$ then $\hat h_{t} + \hat h_{-t} \approx 0$.

## Cepstrum of Source

In the source-filter model, the source can be either voiced or unvoiced. For voiced sounds, the vocal chords can be modeled as a periodic impulse train, that is at regular intervals we have a peak magnitude.

We can express such signals as a sum of impulse trains (see Reproducing Formula in Discrete Time Filters).

$(9) \quad \vec{e} = \sum_{k = 0}^{\infty} \delta_{t - kN}$

Recall that $\delta_0 = 1$ and 0 elsewhere. We’ll have non-zero values for $x_t$ whenever $t = kN$ for $k \in \mathbb{Z}$, that is, for multiples of $N$. Thus $N$ represents the period of this signal.

Proposition 2. The Cepstrum of the impulse train (9) is

$\vec{\hat e} = \sum_{r = 1}^{\infty} \frac{\delta_{t - rN}}{r}$

Proof. See Appendix.

This shows the Cepstrum of an impulse train is also an impulse train and has 0s for $t < N$. It’s also the case that it’s a decaying sequence due to the denominator $r$, but it decays more slowly than $\vec{\hat h}$.

To get a better sense on why, consider some arbitrary value of $r_0$ of $r$ and $t_0 = r_0N$. The denominator for $\hat e_{t_0}$ is $r_0$ while for $\hat h_{t_0}$ it’s $t_0$, which is $N$ times greater than $r_0$.

## Separating Source and Filter

From the discussions above, for the voiced speech the Cepstrum of the source signal will have peaks for $t > N$, while for the filter, it gets attenuated as $t$ grows. Whether this attenuation drops rapidly enough to allow separating source and filter will depend on the coefficients of the filter.

If we consider the higher end of the human fundamental frequency, 300Hz, we get periods greater than 3.33ms, so we need the attenuation of the filter Cepstrum to happen significantly before this value. This seems to work reasonably well in practice though [5].

## Conclusion

This post has been primarily based on the Spoken: Language Processing book. It’s a bit sparse in the details of the mathematical steps, so I had to complement with other sources like Wikipedia and some homework assignment solutions. Following the even-odd rabbit hole was particularly interesting, which merited a post on its own.

I’m looking forward to implementing this and trying with real instances.

## Appendix

Proof of Proposition 1:

We’ll leverage a result of Hermitian Functions, namely that any function $f: \mathbb{R^n} \rightarrow \mathbb{C}$ has a Hermitian decomposition and it’s unique. Hermitian functions are a general case of even-odd functions so we can use the same results.

According to the even-odd decomposition for $f(t) = x_t^{(C)}$, we can defined the even function:

$f_e(t) = \frac{\hat x_t^{(C)} + \hat x_{-t}^{(C)}}{2}$

and an odd function:

$f_o(t) = \frac{\hat x_t^{(C)} - \hat x_{-t}^{(C)}}{2}$

Such that $x_t^{(C)} = f_e(t) + f_o(t)$.

Thus if we can show that the real cepstrum ($x^{(R)}_t$) is an even function and that the imaginary cepstrum ($x^{(I)}_t$) is an odd function and that adding them together yields the complex cepstrum, this would imply that $x^{(R)}_t = f_e(t)$ and $x^{(I)}_t = f_o(t)$, since even-odd decompositions are unique.

We now show that the real cepstrum is an even function in regards to $t$. In Hermitian Functions, we showed that the modulus of a Fourier transform is an even function:

$\abs{\mathscr{F}(\vec{x}, \omega)} = \overline{\abs{\mathscr{F}(\vec{x}, -\omega)}}$

which is clearly preserved under the logarithm operation:

$\ln \abs{\mathscr{F}(\vec{x}, \omega)} = \ln \abs{\mathscr{F}(\vec{x}, -\omega)}$

Let’s expand $e^{i \omega t} = \cos(\omega t) + i \sin(\omega t)$. We note that

$\ln \abs{\mathscr{F}(\vec{x}, \omega)} \sin(\omega t) = - \ln \abs{\mathscr{F}(\vec{x}, -\omega)} \sin(-\omega t)$

Which means that if we integrate the above over $\omega \in [-\pi, \pi]$, the negative values of $\omega$ will cancel out the positive ones, so:

$\int_{-\pi}^{\pi} \ln \abs{\mathscr{F}(\vec{x}, \omega)} \sin(\omega t) d\omega = 0$

This means the real cepstrum can be written as:

$\frac{1}{2 \pi} \int_{-\pi}^{\pi} \ln \abs{\mathscr{F}(\vec{x}, \omega)} \cos(\omega t) d\omega$

Since $\cos(\omega t)$ is even in regards to $t$ and the sum of even functions is even, we conclude that $x^{(R)}_t$ an even function.

Now let’s show that the imaginary cepstrum, $x^{(I)}_t$, is an odd function. The imaginary cepstrum is the complex Cepstrum by taking the imaginary part of the complex natural logarithm:

$\frac{1}{2 \pi} \int_{-\pi}^{\pi} i \varphi(\omega) e^{i \omega t} d\omega$

In Hermitian Functions we showed that $\varphi(\omega)$ is an odd function, $\varphi(\omega) = - \varphi(-\omega)$. We note that

$\varphi(\omega) \cos(\omega t) = - \varphi(-\omega) \cos(-\omega t)$

Which means that if we integrate the above over $\omega \in [-\pi, \pi]$, the negative values of $\omega$ will cancel out the positive ones, so:

$\int_{-\pi}^{\pi} \varphi(\omega) \cos(\omega t) d\omega = 0$

This means the imaginary cepstrum can be written as:

$\frac{1}{2 \pi} \int_{-\pi}^{\pi} i^2 \varphi(\omega) \sin(\omega t) d\omega = -\frac{1}{2 \pi} \int_{-\pi}^{\pi} \varphi(\omega) \sin(\omega t) d\omega$

Since $\sin(\omega t)$ is odd in regards to $t$ and the sum of odd functions is odd, we conclude that $x^{(I)}_t$ is an odd function.

It’s also clear that $x_t^{(C)} = x^{(R)}_t + x^{(I)}_t$, which means $x^{(R)}_t$ and $x^{(I)}_t$ form an even-odd decomposition, which then proves

$f_e(t) = x^{(R)}_t = \frac{\hat x_t^{(C)} + \hat x_{-t}^{(C)}}{2}$

Note that we have also shown that $x^{(R)}_t, x^{(I)}_t, x_t^{(C)}$ are all real.

QED

Proof of Proposition 2:

To show that the Cepstrum of (9) is

$\vec{\hat e} = \sum_{r = 1}^{\infty} \frac{\delta_{t - rN}}{r}$

we’ll first prove a different result. We’ll compute the Cepstrum of

$\vec{e} = \sum_{k = 0}^{M - 1} \alpha^k \delta_{t - kN}$

For $\alpha < 1$ and some integer $M$. Applying the Z-transform we get:

$\mathscr{Z}(\vec{e}, z) = \sum_{t = -\infty}^{\infty} e_t z^{-t}$

If we consider only the entries where $e_t$ is non-zero, that is, for $t = kN$, $k \in [0, M-1]$, we have:

$\mathscr{Z}(\vec{e}, z) = 1 + \alpha z^{-N} + (\alpha z^{-N})^2 + \cdots + (\alpha z^{-N})^{M-1}$

which is a geometric series and can thus be written as:

$\mathscr{Z}(\vec{e}, z) = \frac{1 - (\alpha z^{-N})^M}{1 - \alpha z^{-N}}$

Applying the log:

$\ln \mathscr{Z}(\vec{e}, z) = \ln (1 - (\alpha z^{-N})^M) - \ln (1 - \alpha z^{-N})$

Using the Taylor expansion,

$\ln \mathscr{Z}(\vec{e}, z) = \sum_{r = 1}^{\infty} \frac{(\alpha^r}{r} z^{-Nr} - \sum_{r = 1}^{\infty} \frac{\alpha^{Mr}}{r} z^{-NMr}$

We can re-arrange the terms so that it looks like a power series on $z^{-1}$:

$\ln \mathscr{Z}(\vec{e}, z) = \sum_{t=0}^{\infty} p^t z^{-t}$

As we discussed in The Inverse of the Z-transform for Power Series, we know that the coefficients of this power series $\vec{p}$ is also the inverse Z-transform:

$\vec{p} = \mathscr{Z}^{-1} (\ln \abs{H(z)})$

Which is exactly $\vec{\hat e}$ from (3).

The non-zero entries for $\hat e_t$ in the first sum are $t = Nr$, while for the second sum is $t = MNr$.

We now assume $M \rightarrow \infty$, so we’ll never really encounter the non-zero entries for the second sum, so we can effectively ignore them. Further we can now assume $\alpha \rightarrow 1$.

Thus $\hat e_t = \frac{1}{r}$ when $t = Nr$ for $r = 1, \cdots$ or in terms of the reproducing formula:

$\vec{\hat e} = \sum_{r = 1}^{\infty} \frac{\delta_{t - rN}}{r}$

QED

## References

• [1] A history of cepstrum analysis and its application to mechanical problems - Robert Randall
• [2] Spoken: Language Processing - X. Huang, A. Acero and H. Hon
• [3] Department of Electrical and Computer Engineering Digital Speech Processing - Homework No. 6 Solutions
• [4] Facts About Speech Intelligibility
• [5] Short-Time Spectrum and “Cepstrum” Techniques for Vocal-Pitch Detection - A. M. Noll
• [6] Mathematics - DTFT of Impulse train is equal to 0 through my equation.


text:
# Studies of the magnetic properties and microstructures of two rare earth-transition metal type magnetic alloys

Bailey, Tony (1985). Studies of the magnetic properties and microstructures of two rare earth-transition metal type magnetic alloys. University of Birmingham. Ph.D.

 Preview
Bailey85PhD1o.pdf
PDF

 Preview
Bailey85PhD2o.pdf
PDF

 Preview
Bailey85PhD3o.pdf
PDF

## Abstract

An investigation into the optimisation of magnetic properties of two types of magnetic alloys based on Sm(Co,Cu,Fe,Zr)$$_z$$ (z = 7.4) and Nd$$_{15}$$Fe$$_{77}$$B$$_8$$ has been carried out. The optimum heat treatment which gave the best magnetic properties for the Sm(Co,Cu,Fe,Zr)$$_z$$ alloy depended primarily on the sintering and solid solution temperatures. After quenching the alloy from the solid solution temperature, and then ageing isothermally, it was found that the intrinsic coercivity, microhardness and electrical resistance changed with ageing time, and the ageing temperature also affected the rate of these changes. The magnetic properties of specimens produced from the Nd-Fe-B type alloy were also shown to be affected by different heat treatments. The microhardness, microstructure and intrinsic coercivity were affected by an isothermal ageing treatment and the temperature of the treatment. Two routes were used for powder preparation 1n the production of the sintered specimens: i. Mechanical ball milling of crushed ingot material. ii. Hydrogenation followed by ball milling. It was found that higher energy products were achieved in the ball milled material for the two alloys investigated. Two reasons for this were proposed: i. The hydrogenated and ball milled powder had a larger size than the ball milled only powder. ii. The surfaces of the hydrogenated powder were highly reactive in air and some oxidation of the surfaces occurred. Optical and electron microscope studies showed that the variations in the ageing behaviour of both the alloys was concurrent with subtle differences in the microstructure between the samples aged at different isothermal ageing temperatures.

Type of Work: Thesis (Doctorates > Ph.D.)
Award Type: Doctorates > Ph.D.
Supervisor(s):
Supervisor(s)EmailORCID
Harris, I .R.UNSPECIFIEDUNSPECIFIED
Licence:
College/Faculty: Faculties (to 1997) > Faculty of Engineering
School or Department: School of Metallurgy and Materials
Funders: None/not applicable
Subjects: T Technology > TN Mining engineering. Metallurgy
URI: http://etheses.bham.ac.uk/id/eprint/196

### Actions

 Request a Correction View Item


text:
## Fast iterative solvers for convection-diffusion control problems

John W. Pearson and Andrew J. Wathen

### Abstract

In this manuscript, we describe effective solvers for the optimal control of stabilized convection-diffusion control problems. We employ the Local Projection Stabilization, which results in the same matrix system whether the discretize-then-optimize or optimize-then-discretize approach for this problem is used. We then derive two effective preconditioners for this problem, the first to be used with MINRES and the second to be used with the Bramble-Pasciak Conjugate Gradient method. The key components of both preconditioners are an accurate mass matrix approximation, a good approximation of the Schur complement, and an appropriate multigrid process to enact this latter approximation. We present numerical results to illustrate that these preconditioners result in convergence in a small number of iterations, which is robust with respect to the step-size $h$ and the regularization parameter $\beta$ for a range of problems.

Full Text (PDF) [409 KB]

### Key words

PDE-constrained optimization, convection-diffusion control, preconditioning, Local Projection Stabilization, Schur complement.

### AMS subject classifications

49M25, 65F08, 65F10, 65N30.

### Links to the cited ETNA articles

 [25] Vol. 34 (2008-2009), pp. 125-135 Andy Wathen and Tyrone Rees: Chebyshev semi-iteration in preconditioning for problems including the mass matrix


text:
Open access

# Multi-User Multimedia Transmission over Cognitive Radio Networks Using Priority Queuing

Written By

Hsien-Po Shiang and Mihaela van der Schaar

Published: November 1st, 2009

DOI: 10.5772/7829

From the Edited Volume

Edited by Wei Wang

Chapter metrics overview

View Full Metrics

## 1. Introduction

The emergence of cognitive radio networks have spurred both innovative research and ongoing standards (Mitola et al., 1999; Haykin, 2005; Cordeiro et al., 2006). Cognitive radio networks have the capability of achieving large spectrum efficiencies by enabling interactive wireless users to sense and learn the surrounding environment and correspondingly adapt their transmission strategies. In this context, there exist three main challenges for multimedia users to efficiently transmit their delay-sensitive traffic over the cognitive radio networks. The first problem is how these multimedia users should sense the spectrum and timely model the behavior of the primary licensees. The second problem is how these users should manage the available spectrum resources and share the resource to the license-exempt users to satisfy their multimedia traffic requirements while not interfering with the primary licensees. The third problem is how to maintain seamless communication during the transition (hand-off) of selected frequency channels. In this chapter, we focus on the second challenge regarding the resource management problem. For the remaining two challenges, one can find relevant discussions in other existing literatures as in Akyildiz et al., 2006 and Brown, 2005, etc.

Due to the informationally-decentralized nature of cognitive radio networks (Shiang & van der Schaar, 2007b), the complexity of the optimal centralized solutions (Zekavat & Li, 2006; Fu & van der Schaar, 2007; van der Schaar & Fu, 2009) for spectrum allocation is prohibitive for large systems. In addition, the centralized solution might require a large amount of time to process and to collect the required information, which induces delay that can be unacceptable for the delay-sensitive applications, e.g. multimedia streaming. Hence, it is important to implement distributed solutions as in (Shiang & van der Schaar, 2009) for dynamic resource management by relying on the wireless users’ capabilities to sense, adapt, and coordinate themselves. Importantly, for the distributed solutions, the coordinated interactions (information exchanges) across the autonomous wireless users are essential, since the decisions of an autonomous wireless user will impact and be impacted by the other users. Without explicit coordinated interactions, the heterogeneous users will consume additional resources and respond slower to the time-varying environment. Such information exchange can rely on a dedicated control channel for all users (Brik et al., 2005), or using a group-based coordination scheme without a common control channel (Zhao et al, 2005).

In recent years, the research focus regarding multimedia transmission in wireless networks has been to adapt existing multimedia compression (Stockhammer et al., 2003), error protection algorithms (Mohr et al., 2000), and rate-distortion optimized transmission (Chou & Miao 2006) to the rapidly varying resources of wireless networks (see van der Schaar & Chou, 2007 for more references). Significant contributions have been made to enhance the separate performance of the various OSI layers, or jointly for the MAC, PHY, and application layers (van der Schaar et al., 2003; Setton et al. 2005). However, these solutions cannot provide an integrated and realistic cross-layer optimization framework in the cognitive radio networks to support delay-sensitive multimedia streaming applications. Importantly, the cross-layer optimization has been performed in an autonomous, selfish and isolated manner, at each multimedia source/user, and does not consider its impact on the overall wireless infrastructure and the interactions with other information streams. As such, existing solutions do not provide adequate support for multi-user multimedia streaming over spectrum agile network.

Based on the priority queuing analysis, each wireless user builds an abstraction of the dynamic wireless environment (e.g. wireless condition) and the competing users’ behaviors using the same frequency channel (including the primary licensees, to which the highest priority is assigned). Note that the abstraction is important in order to enable intelligent wireless users to learn and adapt their cross-layer transmission strategies (Haykin, 2005; Mitola et al., 1999). Additionally, the necessary multi-agent interactions (information exchanges) are also determined for the priority queuing analysis. This chapter focuses on the delay-sensitive applications such as surveillance, multimedia conferencing, and media streaming etc., since these applications are most impacted by inefficient spectrum usage. Moreover, this chapter only focuses on the multimedia transmission over a single-hop network infrastructure. Discussion regarding to multimedia transmission over a multi-hop cognitive radio network can be found in Shiang & van der Schaar, 2009.

The organization of the chapter is as follows. In Section 2, we provide the network settings of the cognitive radio network. Section 3 presents the cross-layer problem formulation for multi-user multimedia streaming over such network through a multi-agent interaction. In Section 4, we show that the multi-user multimedia streaming problem over such network can be analyzed using priority queue modeling and hence, facilitate the optimal cross-layer transmission strategies of the multimedia streaming problem through appropriate information exchange. Finally, Section 5 concludes the chapter.

## 2. Network Settings for Multi-User Multimedia Transmission over Cognitive Radio Networks

### 2.1. Multimedia traffic characteristics

Assume that there are N multimedia applications V 1 ,..., V N with distinct sources destinations. In this chapter, we define the users as the transmission pairs between predetermined source wireless stations and destination wireless stations. Each encoded multimedia stream is separated into a certain number of classes (quality layers) as in van der Schaar et al., 2006. Assume that the packets within each multimedia class have the same delay deadline. The number of priority classes for a multimedia sequence V i equals K i . Assume that the total number of priority classes across all users in the network is K . The priority classes in the network are denoted as C 1 ,..., C K . For the purpose of analysis, we reserve the highest priority class C 1 for the primary users in each frequency channel, i.e. λ 1 λ k ,2 k K . The secondary users can be categorized into the rest of K 1 priority classes ( C 2 ,..., C K ) to access the frequency channels

The prioritization of the secondary users can be determined based on their applications, prices paid for spectrum access, or other mechanism design based rules. In this chapter, we will assume that the prioritization was already performed.

. Hence, the total number of classes across all users in the network equals K = i = 1 N K i + 1 . The users in higher priority classes can preempt the transmission of the lower priority classes to ensure an interference-free environment for the primary users (Kleinrock, 1975). The priority of a user affects its ability of accessing the channel. Each multimedia class C k is characterized by:

1. λ k , the expected quality impact of receiving the packets in the class C k . We prioritize the multimedia classes based on this parameter. In the subsequent part of the chapter, we label the K classes (across all users) in descending order of their priorities, i.e. λ 1 λ 2 ... λ K

2. L k , the average packet lengths of the class C k . The expected quality improvement for receiving a multimedia packet in the class C k is defined as λ k L k (see e.g. Wang & van der Schaar, 2006 for more details).

3. N k , the number of packets in the class C k in one GOP duration of the corresponding multimedia sequence.

4. P k s u c c , the probabilities of successfully receiving the packets in the class C k at the destination. Thus, the expected number of the successfully received packets of the class C k is N k P k s u c c

5. d k , the delay deadlines of the packets in the class C k . Due to the hierarchical temporal structure deployed in 3D wavelet multimedia coders (see Wang & van der Schaar, 2006; van der Schaar & Turaga, 2007), for a multimedia sequence, the lower priority packets also have a less stringent delay requirement. This is the reason why we prioritize the multimedia bitstream in terms of the quality impact. However, if the used multimedia coder did not exhibit this property, we need to deploy alternative prioritization techniques λ k v i d e o ( λ k d k ) that jointly consider the quality impact and delay constraints (see more sophisticated methods in e.g. Jurca & Frossard, 2007; Chou & Miao, 2006).

At the client side, the expected quality improvement for multimedia V i in one GOP can be expressed as:

u i = C k V i λ k L k N k P k s u c c E1

Here, we assume that the client implements a simple error concealment scheme, where the lower priority packets are discarded whenever the higher priority packets are lost (van der Schaar & Turaga, 2007). This is because the quality improvement (gain) obtained from decoding the lower priority packets is very limited (in such embedded scalable multimedia coders) whenever the higher priority packets are not received. For example, drift errors can be observed when decoding the lower priority packets without the higher priority packets (Wang & van der Schaar, 2006). Hence, we can write:

P k s u c c = { 0              , if  P k ' s u c c 1  and  C k ' C k ( 1 P k ) = E [ I ( D k d k ) ]  otherwise E2

where we use the notation in (Chou & Miao, 2006) - C k ' C k to indicate that the class C k depends on C k ' . Specifically, if C k and C k ' are classes of the same multimedia stream, C k ' C k means k ' k due to the descending priority ( λ k ' λ k ). P k represents the end-to-end packet loss probability for the packets of class C k . D k represents the experienced end-to-end delay for the packets of class C k . I ( ) is an indicator function. Note that the end-to-end probability P k s u c c depends on the network resource, competing users’ priorities as well as the deployed cross-layer transmission strategies. In addition, for the multimedia V i , let us assume that the multimedia packets are scheduled in a specific order π i according to the prioritization associated with the multimedia content characteristics.

### 2.3. Cognitive radio network settings

Assume that there are a total of M frequency channels F = { F 1 ,..., F M } in the cognitive radio network and there are M primary users P U = { P U 1 ,..., P U M } , each in a separate frequency channel. These primary users can only occupy their assigned frequency channels. Since the primary users are licensed users, they are provided with an interference-free environment (Haykin, 2005; Akyildiz et al., 2006). Assume that there are N secondary users S U = { S U 1 ,..., S U N } in the system. These secondary users are able to operate their applications across various frequency channels for transmission. Hence, they need to time share the chosen frequency channel. Moreover, these secondary users are usually the license-exempt users, and hence, the resulting impact on the primary users must be eliminated.

Let us further assume that there is a Network Resource Manager (NRM) that coordinates multiple access control scheme for sharing the spectrum resource (by assigning transmission opportunities), while ensuring that the corresponding interference on the primary users is eliminated. The role of the NRM is similar to the coordinator in the current IEEE 802.11e Hybrid Coordination Function (HCF) solutions for multimedia applications (van der Schaar et al., 2006). Note that the NRM will not make decisions for the secondary users, but it will only manage the transmission opportunities of the frequency channels based on the priority classes to avoid interference. In this chapter, we investigate the dynamic resource management problem for the multimedia streaming of the secondary users that are associated with this specific NRM. Primary users in the highest priority class C 1 can always access their corresponding channels at any time. Secondary users, on the other hand, require transmission opportunities from the NRM for transmission based on their priorities.

Multiple users can time share the same frequency channel. Note that even if the same time sharing fractions are assigned to the users choosing the same frequency channel, the experienced channel conditions can be different for the users. A wireless user needs to stream its multimedia over an appropriate frequency channel to minimize the transmission delay D k and thereby, increase the multimedia quality in equation (1). For a certain frequency channel F j , the secondary users can experience various channel conditions for the same frequency channel. Besides, the frequency selections of the secondary users also mutually affect each other. Let us denote T i j and p i j as the resulting physical transmission rate and packet error rate for the secondary user S U i transmitting through a certain frequency channel F j . Let R i j = [ T i j p i j ] be the channel conditions of the channel F j for the secondary user S U i and denote the channel condition matrix as R = [ R i j ] M × N

The effective transmission rate T i j e = T i j ( 1 p i j ) depends on 1) the channel conditions, i.e. Signal-to-Noise-Ratio (SNR) x i j , 2) the modulation and coding scheme θ that is adopted by the user, and 3) the multiple access scheme of sharing the channel. For simplicity, in this chapter, let us assume that the NRM adopts the simplest polling mechanism (Bertsekas & Gallager, 1987) similar to IEEE 802.11e that assigns transmission opportunity to the secondary users from the users in higher priority class to the lower priority class. The users in the same priority class will be polled in a round-robin fashion and have the same chance to transmit their packets. More sophisticated MAC protocols are proposed to deal with the spectrum heterogeneity (such as HD-MAC in Zhao et al., 2005). However, the contention-based MAC protocol are not preferable for delay-sensitive applications. Hence, a simple polling-based MAC similar to that used in IEEE 802.11e is considered in this chapter. The NRM only ensures the priority order among the users, but will not decide the secondary users’ actions. The expected physical transmission rate T i j e and packet error rate p i j can be approximated as sigmoid functions of measured and the adopted modulation and coding scheme as in (Krishnaswamy, 2002):

p i j ( θ i x i j ) = 1 1 + exp ( ζ ( θ i ) ( x i j δ ( θ i ) ) ) E3
T i j e ( θ i x i j ) = T i j ( θ i ) 1 + exp ( ζ ( θ i ) ( x i j δ ( θ i ) ) ) E4

where ζ ( θ i ) and δ ( θ i ) are empirical constants for multimedia user V i using frequency channel F j corresponding to the modulation and coding schemes θ i for a given packet length L k of class C k . Thus, even though coordinated by the same NRM, the expected T i j and p i j of the same frequency channel can be different for various secondary users.

## 3. Cross-Layer Transmission Problem Formulation for Multi-User Multimedia Transmission over Cognitive Radio Networks

### 3.1. Cross-layer transmission problem formulation

The considered actions of a secondary user V i as the following cross-layer transmission strategies a i = [ π i γ i α i θ i ] A t o t = A π × A γ × A α × A θ including:

1. The physical layer modulation and coding scheme θ i A θ

2. The MAC layer retransmission limit γ i A γ

3. The application layer multimedia packet scheduling π i A π

4. The selection of the frequency channel for multimedia transmissions α i A α

Denote the frequency selection of a secondary user S U i using α i = [ a i 1 a i 2 ,..., a i M ] A α = { 0,1 } M , where a i j = 1 represents the fact that the secondary user S U i chooses the frequency channel F j . Otherwise, a i j = 0 . Let α i denote the actions of the other secondary users except S U i . Let A = [ a 1 ,..., a N ] denote the total action set across all secondary users.

As stated in equation (1), each secondary user has its own multimedia quality function as the utility function to maximize. Conventionally, the utility function of a specific user is often modeled solely based on its own action, i.e. u i ( a i ) without modeling the other secondary users (Wang & Pottie, 2002; van der Schaar & Shanker, 2005). However, in fact, the utility function in cognitive radio networks depends on the effective delay and throughput that the secondary user can get from the frequency channel it selects, and this is related to the channel sharing, which is coupled with other secondary users. Hence, the utility function u i is also influenced by the action of other secondary users that select this frequency channel. In other words, the utility function can be regarded as u i ( a i α i ) . Specifically, each autonomous multimedia user selects its optimal action a i o p t by solving the optimization problem with the knowledge of α i :

a i o p t = arg max a i A t o t u i ( a i α i ) E5

Importantly, in an informationally-decentralized cognitive wireless network that consists of decentralized secondary users, the secondary user S U i may not know the exact actions of other secondary users α i . Moreover, even if all the actions are known, it is unrealistic to assume that the exact action information can be collected timely to compute and maximize the actual utility function u i ( a i α i ) . Hence, a more practical solution is to dynamically model the other secondary users’ behavior by updating their probabilistic frequency selection strategy profile based on some available information exchange, and then maximizes the expected utility function of S U i

Hence, we define a frequency selection strategy profile of a secondary user S U i as a vector of probabilities s i = [ s i 1 s i 2 ,..., s i M ] S α = S M , where s i j S ( S [ 0,1 ] ) represents the probability of the secondary user S U i choosing the frequency channel F j ( a i j = 1 ). Hence, the summation over all the frequency channels, j = 1 M s i j = 1 . Note that s i j can also be viewed as the fraction of data from S U i transmitted on frequency channel F j , and hence, multiple frequency channels are selected for a secondary users with s i j 0 . Let S = [ s 1 T ,..., s N T ] S M × N denote the total strategy profile across all the secondary users. The expected utility function, given a fixed strategy profile S = ( s i s i ) is

U i ( a ˜ i ( s i ) s i ) = E ( s i s i ) [ u i ( a i α i ) ] E6

where s i denotes the collected frequency selection profile. a ˜ i ( s i ) = [ π i γ i s i θ i ] A ˜ t o t = A π × A γ × S α × A θ represents the transmission strategy using s i instead of α i . Then, the optimization problem in equation (5) becomes:

a ˜ i o p t = arg max a ˜ i A ˜ t o t U i ( a ˜ i ( s i ) s i ) = arg max a ˜ i A ˜ t o t C k V i λ k L k N k P k s u c c ( a ˜ i ( s i ) s i ) E7

Figure 1 provides the system architecture of the secondary users. In Section 4, we will discuss how to model the strategy (behavior) s i and the impact of the other secondary users using priority queuing analysis.

### 3.2. Cross-layer optimization examples

 Average "Static Assignment -Largest-Bandwidth" "Dynamic Least Interference" "Cross-layer O ptimization" T i j ( θ i o p t ) = 1 Mbps Average Y-PSNR (dB) Y-PSNR Standard Deviation Average Y-PSNR (dB) Y-PSNR Standard Deviation Average Y-PSNR (dB) Y-PSNR Standard Deviation S U 1 29.48 4.94 29.89 4.32 32.42 1.97 S U 2 29.90 4.89 30.35 4.29 32.62 2.42 S U 3 29.69 5.02 30.37 4.41 32.36 2.26 S U 4 30.59 4.98 30.87 4.37 32.75 2.31 S U 5 29.48 4.98 29.87 4.41 32.40 2.33 S U 6 30.01 5.04 30.65 4.46 32.26 2.67

### Table 1.

Comparisons of the channel selection algorithms for video streaming with N = 6, M = 10

 No p rimary users Primary users randomly appear ( ρ i = 0.25 ) Average T i j ( θ i o p t ) = 1 Mbps Average Y-PSNR (dB) Average Y-PSNR (dB) Y-PSNR Standard Deviation "Static Assignment" 33.84 29.69 5.02 "Dynamic Least Interference" 33.90 30.37 4.41 "Cross-layer O ptimization" 35.61 32.36 2.26

### Table 2.

Comparisons of the various resource management schemes for video streaming with N = 6, M = 10

Next, let us take a look at the impact of different numbers of secondary users with video streaming applications. Figure 2 shows the average packet loss rate and the average PSNR over the N video streams (instead of over 100 different channel conditions in the previous simulation). The empirical average T i j ( θ i o p t ) of the frequency channels is shown to be 3 Mbps, instead of 1 Mbps in the previous example. Larger N reduces the available resources that can be shared by the video streams, and hence, increases the application layer packet loss rate (due to the expiration of the delay deadline) and hence, decreases the received video quality. The result shows that the cross-layer optimization using the priority queuing analysis outperforms the other two algorithms for multi-user video streaming applications.

## 4. Priority Queuing Analysis for Multimedia Transmission in Cognitive Radio Networks

In this section, we discuss the priority queuing analysis for the multimedia streaming problem over cognitive radio networks. The goal is to provide an abstraction of the dynamic wireless environment and the competing wireless users’ behaviors that impact the secondary user’s utility. It is important to note that the packets of the competing wireless users are physically waiting at different locations. Figure 3 gives an example of the physical queues for the case of M frequency channels and N secondary users. Each secondary user maintains M physical queues for the various frequency channels, which allows users to avoid the well-known head-of-line blocking effect (Wang et al., 2004).

### 4.1. Traffic models of the users

1. Traffic model for primary users – Assume that the stationary statistics of the traffic patterns of primary users can be modeled by all secondary users. The packet arrival process of a primary user is modeled as a Poisson process with average packet arrival rate r j P U for the primary user P U j using the frequency channel F j . We denote the mth moments of the service time distribution of the primary user P U j in frequency channel F j as E [ ( X j P U ) m ] . Note that this traffic model description is more general than a Markov on-off model (Shanker et al., 2005), which is a sub-set of the introduced queuing model with an exponential idle period and an exponential busy period. As in Shanker et al., 2005, an M/G/1 model is adopted in this chapter for the traffic descriptions.

2. Traffic model for secondary users – Assume that the average rate requirement for the secondary user S U i is B i (bit/s). Let r i j denote the average packet arrival rate of the secondary user S U i using the frequency channel F j . Since the strategy s i j represents the probability of the secondary user S U i taking action a i j (transmitting using the frequency channel F j ), we have r i j = s i j B i / L i ( π i ) , where L i ( π i ) denotes the average packet length of the secondary user S U i depending on which priority class of multimedia packets is chosen in π i . If a certain secondary user S U i can never use the frequency channel F j , we fix its strategy to s i j = 0 , and hence, r i j = 0 . For simplicity, we also model the packet arrival process of the secondary users using a Poisson process.

Since packet errors are unavoidable in a wireless channel, let us assume that packets will be retransmitted, if they are not correctly received. This can be regarded as a protection scheme similar to the Automatic Repeat Request protocol in IEEE 802.11 networks. Hence, the service time of the users can be modeled as a geometric distribution. Let E [ X i j ( π i γ i θ i ) ] and E [ X i j 2 ( π i γ i θ i ) ] denote the first two moments of the service time of the secondary user S U i using the frequency channel F j . For simplicity, we denote E [ X i j ( π i γ i θ i ) ] and E [ X i j 2 ( π i γ i θ i ) ] using E [ X i j ] and E [ X i j 2 ] hereafter in this chapter. Based on the physical layer link adaptation (Krishnaswamy, 2002), R i j = [ T i j p i j ] in equation (3) and (4), we have:

E [ X i j ] = ( L i ( π i ) + L o ) ( 1 p i j ( θ i ) γ i + 1 ) T i j ( θ i ) ( 1 p i j ( θ i ) ) ( L i ( π i ) + L o ) T i j ( θ i ) ( 1 p i j ( θ i ) ) E8
E [ X i j 2 ] ( L i ( π i ) + L o ) 2 ( 1 + p i j ( θ i ) ) T i j ( θ i ) 2 ( 1 p i j ( θ i ) ) 2 E9

where L i is the average packet length of the secondary user S U i and L o represents the effective control overhead including the time for protocol acknowledgement, information exchange, and NRM polling delay, etc.

To describe the traffic model, we define the traffic specification

The traffic specification is similar to the TSPEC in current IEEE 802.11e for multimedia transmission.

for the secondary user S U i as T S i = [ C k B i L i X i X i 2 ]  if  S U i C k , where X i = [ E [ X i j ] | j = 1,..., M ] and X i 2 = [ E [ X i j 2 ] | j = 1,..., M ] are the vectors of the first two moments of service time when user S U i transmitting in each frequency channel. This information needs to be exchanged among the secondary users, which will be discussed in more details in Section 4.4.

### 4.2. Queuing analysis for the secondary users with the same priority

In this subsection, we first consider the case that all packets have the same priority by ignoring the impact of the primary users. In the next subsection, we will generalize these results by considering the impact of the primary users using priority queuing.

In order to solve the dynamic resource management problem, we need to calculate the distribution of the end-to-end delay D i ( a i α i ) for the secondary user S U i to transmit its packets. The expected end-to-end delay E [ D i ] of the secondary user S U i can be expressed as:

E [ D i ( a i α i ) ] = j = 1 M s i j E [ D i j ( R i j ( a i α i ) ) ] E10

where E [ D i j ( R i j ( a i α i ) ) ] is the average end-to-end delay if the secondary user S U i chooses the frequency channel F j . Recall that R i j = [ T i j p i j ] is the channel condition of the channel F j for the secondary user S U i . Note that s i j is the strategy of the action a i j . We use the queuing model in Figure 3 and apply queuing theory to calculate the end-to-end delay.

In Figure 3, for a specific secondary user S U i , each arriving packet will select a physical queue to join (action a i j ) according to the strategy s i j . Assume that once a packet selects a physical queue, it cannot jockey to another queue (change position to the other queues). Thus, a queued packet waits in line to be served on the selected frequency channel.

Note that there are N physical queues from N secondary users for a frequency channel F j . Only one of them can transmit its packets at any time. Hence, we form a “virtual queue” for the same frequency channel (see Figure 4). In a virtual queue, the packets of the different secondary users wait to be transmitted. Importantly, the total sojourn time (queue waiting time plus the transmission service time) of this virtual queue now becomes the actual service time at each of the physical queues. The concept is similar to the “service on vacation” (Bertsekas & Gallager, 1987) in queuing theory, and the waiting time of the virtual queue can be regarded as the “vacation time”.

Since the number of the secondary users in a regular cognitive radio network is usually large, we can approximate the virtual queue using the FIFO (First-In-First-Out) M/G/1 queuing model (i.e. when N , the input traffic of the virtual queue can be modeled as a Poisson process). The average arrival rate of the virtual queue of the frequency channel F j is i = 1 N r i j . Let us denote the first two moments of the service time for the virtual queue of the frequency channel F j as E [ X ˜ j ] and E [ X ˜ j 2 ] . For a packet in the virtual queue of frequency channel F j , we determine the probability of the packet coming from the secondary user S U i as:

f i j = s i j k = 1 N s k j E11

Hence,

E [ X ˜ j ] = i = 1 N f i j E [ X i j ] E [ X ˜ j 2 ] = i = 1 N f i j E [ X i j 2 ] E12

Let W ˜ j and D ˜ j represent the queue waiting time and sojourn time of the virtual queue of the frequency channel F j , respectively. E [ W ˜ j ] can be obtained from the Pollaczek-Khinchin formula (Bertsekas & Gallager, 1987). Then, E [ D ˜ j ] can be obtained as:

E [ D ˜ j ] = E [ W ˜ j ] + E [ X ˜ j ] = i = 1 N r i j E [ X ˜ j 2 ] 2 ( 1 i = 1 N r i j E [ X ˜ j ] ) + E [ X ˜ j ] E13

Then, we apply G/G/1 approximation based on the work of (Abate et al., 1995; Jiang et al., 2001) for the virtual queuing delay distribution:

Prob ( D ˜ j t ) = i = 1 N r i j E [ X ˜ j ] exp ( t i = 1 N r i j E [ X ˜ j ] E [ D ˜ j ] ) E14

This virtual queuing delay distribution is the service time distribution of the physical queues at the secondary users. Since the service time of the physical queue is an exponential distribution (see equation (14)), the average end-to-end delay of the secondary user S U i sending packets through frequency channel F j is approximately:

E [ D i j ] = E [ D ˜ j ] 1 r i j E [ D ˜ j ]  for  r i j E [ D ˜ j ] 1 E15

Strategies ( s i s i ) such that r i j E [ D ˜ j ] 1 will result in an unbounded delay E [ D i j ] , which is undesirable for multimedia streaming. The advantage of this approximation is that once the average delay of the virtual queue E [ D ˜ j ] for a certain frequency channel F j is known by the secondary user S U i , the secondary user can immediately calculate the expected end-to-end delay E [ D i j ] of a packet transmitting using the frequency channel F j

### 4.3. Queuing analysis with the impact of higher priority users

Based on the derivations in the previous subsection, we now consider the impact of primary users. First, let us consider the case that there are only two priority classes (i.e. K = 2 , P U C 1 , S U C 2 ). Note that in the introduced queuing model in Figure 4, the packets from the primary users will not be seen at the physical queues of the secondary users, but only have impact on the virtual queues of the frequency channels. Since the primary users are the first priority in each of the frequency channels, we modeled the virtual queues for a particular frequency channel using a priority M/G/1 queue instead of a FIFO M/G/1 queue. Recall that the average input rate of the primary user P U j is λ j P U , and the first two moments of the service time is E [ X j P U ] and E [ X j P U 2 ] . By applying the Mean Value Analysis (MVA) in queuing theory (Kleinrock, 1975), we modify equation (13) into a priority M/G/1 queuing case:

E [ D ˜ j ] = E [ W ˜ j ] + E [ X ˜ j ]        = r j P U E [ ( X j P U ) 2 ] + i = 1 N r i j E [ X ˜ j 2 ] 2 ( 1 r j P U E [ X j P U ] ) ( 1 i = 1 N r i j E [ X ˜ j ] r j P U E [ X j P U ] ) + E [ X ˜ j ]        = ρ j 2 + μ j 2 2 ( 1 ρ j ) ( 1 ρ j μ j ) + E [ X ˜ j ] E16

ρ j represents the normalized loading of the primary user P U j for the frequency channel F j , and

ρ j = r j P U E [ X j P U ] ρ j 2 = r j P U E [ ( X j P U ) 2 ] E17

μ j represents the summation of the normalized traffic loading of all the secondary users using the frequency channel F j , and

μ j = i = 1 N r i j E [ X ˜ j ] μ j 2 = i = 1 N r i j E [ X ˜ j 2 ] E18

Hence, we substitute the E [ D ˜ j ] of equation (16) into equation (15), and determine the average end-to-end delay E [ D i j ] of the secondary user S U i sending packets using frequency channel F j while considering the impact of the primary user P U j

The derivation can be generalized to K priority classes among users ( K 2 , P U C 1 S U { C 2 ,..., C K } ). Similar to the two priority classes’ case, the priority queuing model only affects the virtual queues for different frequency channels. Since the secondary users now have different priorities, the secondary users in different priority classes will experience different virtual queuing delay. Let E [ D ˜ j k ] represent the virtual queuing delay experienced by the secondary user in class C k in the virtual queue for the frequency channel F j . Let μ j k represent the normalized traffic loading of all the class C k secondary users using the frequency channel F j . Based on the definition in the two priority users’ case, we have:

μ j k = S U i C k r i j E [ X ˜ j ] a n d μ j k 2 = S U i C k r i j E [ X ˜ j 2 ] E19

By applying the Mean Value Analysis (MVA) (Kleinrock, 1975), we have:

E [ D ˜ j k ] = E [ W ˜ j k ] + E [ X ˜ j ] = ρ j 2 + l = 2 k μ j l 2 2 ( 1 ρ j l = 2 k 1 μ j l ) ( 1 ρ j l = 2 k μ j l ) + E [ X ˜ j ] E20

Hence, for a secondary user S U i C k using the frequency channel F j , its end-to-end delay E [ D i j ] and probability of packet loss P i j ( a ˜ i ( s i ) s i ) become:

E [ D i j ] = E [ D ˜ j k ] 1 r i j E [ D ˜ j k ]  for  r i j E [ D ˜ j k ] 1,   S U i C k E21
,
P i j ( a ˜ i ( s i ) s i ) = r i j exp ( r i j ( 1 r i j E [ D ˜ j k ] ) d i E [ D ˜ j k ] )  for  S U i C k E22

Therefore, we can approximate the objective function in equation (7) for the multimedia streaming of the secondary user S U i as (note that j = 1 M s i j = 1 ):

maximize a ˜ i A ˜ t o t C k V i λ k L k N k P k s u c c ( a ˜ i ( s i ) s i ) maximize a ˜ i A ˜ t o t    C k V i λ k L k N k j = 1 M s i j ( 1 P i j ( a ˜ i ( s i ) s i ) ) maximize a ˜ i A ˜ t o t    C k V i λ k L k N k j = 1 M s i j ( 1 r i j exp ( r i j ( 1 r i j E [ D ˜ j k ( a ˜ i ( s i ) s i ) ] ) d i E [ D ˜ j k ( a ˜ i ( s i ) s i ) ] ) ) E23

Note that only E [ D ˜ j k ] depends on the strategies s i of other secondary users.

We provide here an example that considers a simple network with two secondary users and three frequency channels (i.e. N = 2 , M = 3 ). In the simple example, the behavior of the proposed cognitive radio model can be clearly understood. Assume that each secondary user can choose all three frequency channels. The two secondary users are in the same priority class. The simulation parameters of the secondary users are presented in Table 3 including the channel conditions R i j = [ T i j p i j ] , and initial strategies s i ( 0 ) , etc. The normalized traffic statistics of the primary users are given in Table 4.

 Secondary users Physical transmission rate T i j ( θ i o p t ) (Mbps) Physical packet error rate p i j ( θ i o p t ) Rate requirement B i (Mbps) F 1 F 2 F 3 F 1 F 2 F 3 S U 1 1.88 1.27 1.07 0.11 0.17 0.17 0.92 S U 2 1.32 1.68 1.20 0.03 0.05 0.11 0.74

### Table 3.

Considered parameters of the secondary users in the example.

 Primary users Normalized loading ρ j Second moment normalized loading ρ j 2 P U 1 0.2 1 × 10 − 4 P U 2 0.1 1 × 10 − 4 P U 3 0.3 1 × 10 − 4

### Table 4.

Considered parameters of the primary users in the example.

Given the statistics, Figure 5 provides the different strategy pairs ( s 1 j s 2 j ) in the three frequency channels that keep the analytical experienced delays E [ D i j ] (using equation (21)) bounded by the delay deadlines for the two secondary users. Importantly, a strategy pair ( s 1 j s 2 j ) that results in an unbounded E [ D i j ] will make the multimedia quality drop abruptly for the delay-sensitive applications, which is undesirable for these secondary users. Figure 5 clearly shows when the channel conditions become worse (from F 1 to F 3 ), the selectable frequency strategy pairs becomes less. Hence, equation (21) provides the analytical operation points for the frequency selection strategy pairs.

### 4.4. Realistic framework for multimedia transmission over cognitive radio networks using queuing analysis

The priority virtual queue analysis requires the following information to compute μ j l and μ j l 2 in (20):

1. Priority: the secondary users’ priorities.

2. Normalized loading: the secondary users’ normalized loading parameters r i j E [ X ˜ j ] , which not only include the information of s i , but also reflects the input traffic loading and the expected transmission time using a specific frequency channel.

3. Variance statistics: the secondary users’ variance statistics with the normalized parameter r i j E [ X ˜ j 2 ]

Hence, two kinds of information exchange are defined for the priority virtual queue analysis:

1. Other secondary users’ traffic specification T S i

2. The frequency selection information of the other secondary users to model the strategies s i

Figure 6 shows the block diagram of the introduced priority virtual queue interface (Shiang & van der Schaar, 2008) together with the cross-layer optimization approach in Section 3.1. Since the traffic specification T S i only varies when the frequency channels change dramatically, the traffic specification can be exchanged only when a secondary user joins the network. On the other hand, the frequency selection information can be exchanged more frequently (e.g. once per service interval in van der Schaar et al., 2006). Note that since the users in the higher priority classes will not be affected by the users in the lower priority classes, they do not need the information from the users in a lower priority class. Hence, the information exchanges (overheads) and computational complexity will be scalable and will increase as the traffic priority decreases, thereby benefiting the high priority and low-delay traffic.

## 5. Conclusions

In this chapter, we discussed the priority virtual queuing architecture for heterogeneous and autonomous secondary users in cognitive radio networks, based on which they can time share the various frequency channels in a distributed fashion. With the information exchange defined by the proposed interface, the secondary users can build an abstraction of the dynamic wireless environment as well as the competing wireless users’ behaviors and learn how to efficiently adapt their transmission strategies for multimedia streaming. Importantly, unlike conventional channel allocation schemes that select the least interfered channel merely based on the channel estimation, the introduced multi-agent priority queue modeling allows the secondary users to track the other users and adequately adapt their own transmission strategies to the changing multi-user environment. It can be shown that the introduced cross-layer optimization that applies priority queuing analysis significantly outperforms the fixed channel allocation and the current dynamic channel allocation that selects the least interfered channel, in terms of multimedia quality. Finally, we discuss the required information exchange that is required for the queuing analysis and present a realistic framework for the secondary users to transmit multimedia traffic over cognitive radio networks.

## References

1. 1. Abate J. Choudhury G. L. Whitt W. 1995 “Exponential approximations for tail probabilities in queues I: Waiting times”, in Operations Research, 43 5 885 901 , 1995.
2. 2. Akyildiz I. F. Lee W.-Y. Vuran M. C. Mohanty S. 2006NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey,” Computer Networks: The International Journal of Computer and Telecommunication Networking, 50 13 Sep 2006.
3. 3. Bertsekas D. Gallager R. 1987 Data Networks, Prentice Hall, Inc. Upper Saddle River, NJ, 1987.
4. 4. Brik V. . Rozner E. Banarjee S. Bahl P. 2005 “DSAP: a protocol for coordinated spectrum access,” in Proc. IEEE DySPAN 2005, Nov. 2005, 611 614 .
5. 5. Brown T. X. 2005 “An analysis of unlicensed device operation in licensed broadcast service bands,” in Proc. IEEE DySPAN 2005, Nov 2005, 11 29 .
6. 6. Chou P. A. Miao Z. 2006 “Rate-Distortion Optimized Streaming of Packetized Media,” in IEEE Transactions on Multimedia, 8 2 Apr. 2006, 390 404 .
7. 7. Cordeiro C. Challapali K. Birru D. Shankar S. 2006IEEE 802.22: An Introduction to the First Wireless Standard based on Cognitive Radios,” in Journal of Communications, Academy Publishers, 1 1 Apr 2006.
8. 8. Fu F. van der Schaar M. 2007 "Noncollaborative Resource Management for Wireless Multimedia Applications Using Mechanism Design," in IEEE Trans. Multimedia, 9 4 851 868 , Jun. 2007.
9. 9. Haykin S. 2005Cognitive Radio: Brain-Empowered Wireless Communications,” in IEEE Journal on Selected Areas in Communications, 23 2 Feb 2005.
10. 10. Jiang T. Tham C. K. Ko C. C. 2001 “An approximation for waiting time tail probabilities in multiclass systems”, IEEE Communications Letters, 5 4 175 177 . April 2001.
11. 11. Jurca D. Frossard P. 2007 “Packet Selection and Scheduling for Multipath video streaming,” IEEE Transactions on Multimedia, 9 2 Apr. 2007.
12. 12. Kleinrock L. 1975 Queuing Systems Volume I: Theory, NY: Wiley-Interscience Publication, 1975.
13. 13. Krishnaswamy D. 2002 “Network-assisted link adaptation with power control and channel reassignment in wireless networks,” 3G Wireless Conference, 165 170 , 2002.
14. 14. Mitola J. III. Maguire G. Q. Jr. 1999Cognitive radio: Making software radios more personal,” in IEEE Pers. Commun., 6 4 13 18 , Aug. 1999.
15. 15. Mohr A. E. Riskin E. A. Ladner R. E. 2000Unequal loss protection: Graceful degradation of image quality over packet erasure channels through forward error correction,” in IEEE J. Sel. Areas Commun., 18 6 819 829 , Jun. 2000.
16. 16. Setton E. Yoo T. Zhu X. Goldsmith A. Girod B. 2005Cross-layer design of Ad hoc Networks for real-time video streaming,” IEEE Wireless Communications Mag., 59 65 , Aug 2005.
17. 17. Shankar S. Chou C. T. Challapali K. Mangold S. 2005 “Spectrum agile radio: capacity and QoS implementations of dynamic spectrum assignment,” Global Telecommunications Conference, Nov. 2005.
18. 18. Shiang H.-P. van der Schaar M. 2007a “Multi-user video streaming over multi-hop wireless networks: A distributed, cross-layer approach based on priority queuing,” IEEE J. Sel. Areas Commun., 25 4 770 785 , May 2007.
19. 19. Shiang H.-P. van der Schaar M. 2007b “Informationally Decentralized Video Streaming over Multi-hop Wireless Networkss,” in IEEE Trans. Multimedia, 9 6 1299 1313 , Sep 2007.
20. 20. Shiang H.-P. van der Schaar M. 2008 “Queuing-Based Dynamic Channel Selection for Heterogeneous Multimedia Applications over Cognitive Radio Networks,” in IEEE Trans. Multimedia, 10 5 896 909 , Aug. 2008.
21. 21. Shiang H.-P. van der Schaar M. 2009Distributed Resource Management in Multi-hop Cognitive Radio Networks for Delay Sensitive Transmission,IEEE Transactions on Vehicular Technology, 58 2 941 953 , Feb 2009.
22. 22. Stine J. A. 2005 “Spectrum management: the killer application of ad hoc and mesh networking,” in Proc. IEEE DySPAN 2005, Nov. 2005, 184 193 .
23. 23. Stockhammer T. Hannuksela M. M. Wiegand T. 2003 “H. 264/AVC in Wireless Environments,“ in IEEE Transactions on Circuits and Systems for Video Technology, 13 7 July 2003, 657 673 .
24. 24. Tekinay S. Jabbari B. 1991Handover and Channel Assignment in Mobile Cellular Networks,” IEEE Communication Magazine, 29 42 46 , Nov 1991.
25. 25. van der Schaar M. Andreopoulos Y. Hu Z. 2006Optimized Scalable Video Streaming over IEEE 802.11a/e HCCA Wireless Networks under Delay Constraints,” IEEE Trans. On Mobile Computing, 5 6 755 768 , June 2006.
26. 26. van der Schaar M. Chou P. 2007 Multimedia over IP and Wireless Networks, Academic Press, 2007.
27. 27. van der Schaar M. Fu F. 2009 "Spectrum Access Games and Strategic Learning in Cognitive Radio Networks for Delay-Critical Applications," accepted to Proc. of IEEE, Special issue on Cognitive Radio, to appear Early 2009.
28. 28. van der Schaar M. Shankar S. 2005 "Cross-layer wireless multimedia transmission: challenges, principles, and new paradigms," IEEE Wireless Commun. Mag., 12 4 50 58 , Aug. 2005.
29. 29. van der Schaar M. Turaga D. S. 2007Cross-layer Packetization and Retransmission Strategies for Delay-sensitive wireless Multimedia Transmission,” IEEE Transactions on Multimedia, 9 1 185 197 , Jan 2007.
30. 30. Wang C. C. Pottie G. J. 2002Variable Bit Allocation for FH-CDMA Wireless Communication Systems,” in IEEE Transactions on Communications, 50 6 Oct 2002.
31. 31. Wang M. van der Schaar M. 2006Operational Rate-Distortion Modeling for Wavelet Video Coders,” in IEEE Transactions on Signal Processing, 54 9 3505 3517 , Sep. 2006.
32. 32. Wang J. Zhai H. Fang Y. 2004 “Opportunistic packet scheduling and media access control for wireless LANs and multi-hop ad hoc networks,” in IEEE Wireless Communications and Networking Conference, 2 1234 1239 , Mar 2004.
33. 33. Zekavat S. A. Li X. 2006Ultimate Dynamic Spectrum Allocation via User-central Wireless Systems,” Journal of Communications, Academy Publishers, 1 1 60 67 , Apr 2006.
34. 34. Zhao J. Zheng H. Yang G.-H. 2005 “Distributed coordination in dynamic spectrum allocation networks,” in Proc. IEEE DySPAN 2005, Nov 2005, 259 268 .

## Notes

• The prioritization of the secondary users can be determined based on their applications, prices paid for spectrum access, or other mechanism design based rules. In this chapter, we will assume that the prioritization was already performed.
• The traffic specification is similar to the TSPEC in current IEEE 802.11e for multimedia transmission.

Written By

Hsien-Po Shiang and Mihaela van der Schaar

Published: November 1st, 2009