# Finite Groups With Two Irredundant Covers

Jonathan Cohen and Kyle Rosengartner

###### Abstract.

An irredundant cover of a finite group $G$ is a collection of proper subgroups
whose union is $G$ and which contains no smaller subcover. We classify finite
groups which possess exactly two irredundant covers, thereby initiating an
answer to a question of Brodie, who classified finite groups with one
irredundant cover.

##  1\. Introduction

Let $G$ be a group. A collection $\\{H_{i}\\}_{i=1}^{n}$ of proper subgroups
of $G$ is called a cover if $G=\bigcup\limits_{i=1}^{n}H_{i}$. The smallest
possible $n$ is called the covering number of $G$, typically denoted
$\sigma(G)$. There has been significant progress in the understanding of
covering numbers and their structural significance. For a nice survey of many
of these and related results, see [Bh].

In this article we consider a variation on this theme, in which the quantity
of interest is not the size of the cover but the number of distinct covers. To
be more precise, we say that a cover $\\{H_{i}\\}_{i=1}^{n}$ of $G$ is
irredundant if it contains no proper subcover. In other words,
$\bigcup\limits_{i\neq j}H_{i}\neq G$ for all $1\leq j\leq n$. Let $\beta(G)$
denote the number of distinct irredundant covers of a finite group $G$ (we
will only consider finite groups).

In [B], a classification of finite groups with $\beta(G)=1$ is obtained. At
the end of that paper, the question is posed of extending such a determination
for larger values of $\beta(G)$. The main result of this paper is such a
classification for $\beta(G)=2$. To state it, we first give some basic
notation: the group $\mathbb{Z}_{n}$ is the cyclic group of order $n$, $Q_{8}$
is the quaternion group of order $8$, and $K\rtimes H$ is a semidirect product
of the groups $K$ and $H$.

######  Theorem 1.1.

Suppose that $G$ is a finite group with exactly two irredundant covers.

A) If $G$ is nilpotent then $G$ is one of the following groups:

i) $(\mathbb{Z}_{p^{2}}\rtimes\mathbb{Z}_{p})\times\mathbb{Z}_{n}$ where
$(p,n)=1$ and $p>2$ is prime.

ii) $\mathbb{Z}_{4}\times\mathbb{Z}_{2}\times\mathbb{Z}_{n}$ where $n$ is odd.

B) If $G$ is not nilpotent then $G$ is one of the following groups:

iii) $\mathbb{Z}_{p^{t}}\rtimes\mathbb{Z}_{n}$ where $p$ is prime, $(p,n)=1$,
$\mathbb{Z}_{n}$ centralizes $\mathbb{Z}_{p^{t-1}}$, and $\mathbb{Z}_{n}$ acts
on $\mathbb{Z}_{p^{t}}$ by an automorphism of order $q^{2}$ for a prime $q$.

iv) $\mathbb{Z}_{p}^{2}\rtimes\mathbb{Z}_{n}$ where $p$ is prime, $(p,n)=1$,
and $\mathbb{Z}_{n}$ acts irreducibly on $\mathbb{Z}_{p}^{2}$ by an
automorphism of prime order.

v) $Q_{8}\rtimes\mathbb{Z}_{n}$ where $n$ is odd and $\mathbb{Z}_{n}$ acts on
$Q_{8}$ by an automorphism of order 3.

We remark that case iii) can occur if and only if $p-1$ is not square-free,
while case iv) can occur if and only if $p+1$ is not a power of 2. We now
outline the contents of this article. In section 2 we prove some preliminary
results about irredundant covers. In section 3 we begin the classification of
groups $G$ with $\beta(G)=2$, showing that it naturally breaks into two cases.
In section 4 we handle the first case, which includes all nilpotent $G$, and
in section 5 we handle the second case, which ends up including all
nonnilpotent $G$. In section 6 we consider some possibilities for future work.

##  2\. Preliminaries

Let $G$ be a finite group and let $\beta(G)$ denote the number of irredundant
covers of $G$. We write $\beta(G)=0$ if $G$ is cyclic. If $N\leq G$ then we
say $N$ is cyclically embedded in $G$ if $\langle N,x\rangle$ is cyclic for
all $x\in G$. Clearly any such $N$ is contained in $Z(G)$. A cyclic subgroup
$C\leq G$ is a maximal cyclic subgroup if $C$ is not contained in any larger
cyclic subgroup, and is a cyclic maximal subgroup if $C$ is not contained in
any larger proper subgroup. Note that maximal cyclic subgroups always exist
but cyclic maximal ones may not.

######  Lemma 2.1.

Let $G$ be a finite noncyclic group and $N$ a normal subgroup.

a) A subgroup appears in some irredundant cover of $G$ if and only it contains
a maximal cyclic subgroup of $G$. In particular, any cyclic maximal subgroup
appears in all irredundant covers.

b) We have $\beta(G)\geq\beta(G/N)$, with equality if and only if $N$ is
cyclically embedded.

c) If $(|G|,n)=1$ then $\beta(G\times\mathbb{Z}_{n})=\beta(G)$.

###### Proof.

a) Let $x_{1},\ldots,x_{n}$ be generators of the distinct maximal cyclic
subgroups of $G$. Clearly $G=\bigcup\limits_{i=1}^{n}\langle x_{i}\rangle$,
and $\\{\langle x_{i}\rangle\\}_{i=1}^{n}$ is an irredundant cover. If
$K_{1},\ldots,K_{m}$ is a cover of $G$ then $G$ is the union of those $K_{j}$
that contain some $x_{i}$. So if the cover is irredundant then all $K_{j}$
contain some $x_{i}$. Conversely, if $H\supset\langle x_{i}\rangle$ for some
$i$ then $G=H\cup\bigcup\limits_{x_{i}\not\in H}\langle x_{i}\rangle$ and this
gives an irredundant cover since $x_{i}\in H\setminus\bigcup\limits_{i\neq
j}\langle x_{j}\rangle$.

b) If $\\{K_{i}/N\\}_{i=1}^{n}$ is an arbitrary irredundant cover of $G/N$
then $\\{K_{i}\\}_{i=1}^{n}$ is an irredundant cover of $G$. This determines a
function $f$ from the set of irredundant covers of $G/N$ to those of $G$.
Since $f$ is clearly injective, we have $\beta(G/N)\leq\beta(G)$. The image of
$f$ is those irredundant covers $\\{K_{i}\\}_{i=1}^{n}$ of $G$ with
$K_{i}\supset N$ for $1\leq i\leq n$. We claim $f$ is surjective if and only
if $N$ is cyclically embedded.

Suppose first that $N\leq G$ is cyclically embedded. If $\langle x\rangle$ is
a maximal cyclic subgroup then $\langle x,N\rangle$ is a cyclic subgroup
containing $\langle x\rangle$, so $N\subset\langle x\rangle$. Thus $N$ is
contained in all maximal cyclic subgroups, hence in every subgroup that
appears in an irredundant cover by a). Thus $f$ is surjective and
$\beta(G)=\beta(G/N)$.

Suppose now that $\beta(G)=\beta(G/N)$. Therefore if $\\{K_{i}\\}_{i=1}^{n}$
is an irredundant cover of $G$ then $K_{i}\supset N$ for $1\leq i\leq n$. In
particular this holds if the $K_{i}$ are the maximal cyclic subgroups of $G$.
Let $g\in G$, and choose $x\in G$ so that $\langle x\rangle$ is a maximal
cyclic subgroup containing $g$. Since $N\subset\langle x\rangle$ we have
$\langle g,N\rangle\subset\langle x,N\rangle=\langle x\rangle$, and thus $N$
is cyclically embedded.

c) The factor $\mathbb{Z}_{n}$ is cyclically embedded in $G$ so this follows
from b). ∎

##  3\. Groups with Two Irredundant Covers

Suppose $\beta(G)=2$. If $\\{\langle x_{i}\rangle\\}_{i=1}^{n}$ are the
distinct maximal cyclic subgroups of $G$, this gives one irredundant cover. As
proved above, if some $\langle x_{i}\rangle$ is a maximal subgroup of $G$ then
it must be included in every irredundant cover. Since $\beta(G)>1$, we may
assume without loss of generality that $\langle x_{1}\rangle$ is not maximal.
Let $H\leq G$ with $\langle x_{1}\rangle\subsetneq H\subsetneq G$. Then
$\\{H\\}\cup\\{\langle x_{i}\rangle:x_{i}\not\in H\\}$ is an irredundant cover
since $x_{1}\in H\setminus\bigcup\limits_{i=2}^{n}\langle x_{i}\rangle$. This
therefore is the second irredundant cover of $G$. Since $H$ is the unique
noncyclic subgroup that appears in an irredundant cover of $G$, $H$ is a
characteristic subgroup of $G$. In particular, both covers of $G$ are normal
covers: all conjugates of the subgroups appearing are also present. Since $H$
is maximal, being the unique proper subgroup containing $\langle
x_{1}\rangle$, the index $[G:H]$ is prime. By symmetry, $H$ contains all the
nonmaximal $\langle x_{i}\rangle$, so $\langle x_{i}\rangle\not\subset H$ if
and only if $\langle x_{i}\rangle$ is a cyclic maximal subgroup. Thus $G$
contains cyclic (hence abelian) maximal subgroups, and in particular, $G$ is
solvable.

Fix $\langle x_{i}\rangle\not\subset H$. Since $\langle x_{i}\rangle$ is a
maximal subgroup of the solvable group $G$, the index $[G:\langle
x_{i}\rangle]=p^{m}$ for some prime $p$. Thus $\langle x_{i}\rangle$ contains
a conjugate of each Sylow subgroup except the $p$-Sylows. In particular, all
Sylow subgroups of $G$, with the possible exception of the $p$-Sylows, are
cyclic. Let $A\subset\langle x_{i}\rangle$ be the maximal Hall subgroup of
$\langle x_{i}\rangle$ with index a power of $p$. Then $A$ is also a Hall
subgroup of $G$. By the proof of [[PK], Theorem 1], either $G=A\rtimes P$ or
$G=P\rtimes A$, where $P$ is some $p$-Sylow subgroup of $G$.

Before proceeding to these two cases, we prove a useful fact about $D_{2n}$,
the dihedral group of order $2n$.

######  Lemma 3.1.

Let $n\geq 2$.

a) If $n$ is prime then $\beta(D_{2n})=1$.

b) If $n$ is not prime then $\beta(D_{2n})>2$.

###### Proof.

a) This follows from the classification given in [B], or from the fact that,
when $n$ is prime, every nontrivial proper subgroup of $D_{2n}$ is a cyclic
maximal subgroup.

b) Write $D_{2n}=\langle a,b:a^{n}=b^{2}=baba=1\rangle$ and let $d$ be a
proper divisor of $n$. The subgroups $\langle b\rangle$ and $\langle
ba\rangle$ are maximal cyclic subgroups (of order 2) and are contained in the
distinct proper subgroups $\langle b,a^{d}\rangle$ and $\langle
ba,a^{d}\rangle$, respectively. Both of these noncyclic subgroups occur in
some irredundant cover, so $\beta(G)>2$. ∎

##  4\. The case $G=A\rtimes P$

We first consider the simplest case $G=A\times P$. Equivalently, $G$ is
nilpotent. Note $A$ is cyclically embedded in $G$ so $\beta(G)=\beta(P)=2$ by
Lemma 2.1.

######  Proposition 4.1.

Suppose that $G$ is nilpotent and $\beta(G)=2$. Then $G=P\times\mathbb{Z}_{m}$
where $(|P|,m)=1$ and either $P=\mathbb{Z}_{p^{2}}\rtimes\mathbb{Z}_{p}$ for
an odd prime $p$, or else $P=\mathbb{Z}_{4}\times\mathbb{Z}_{2}$.

###### Proof.

From the above remarks, we must show that $\beta(P)=2$ if and only if $P$ is
one of the listed $p$-groups. If $\beta(P)=2$ then $P$ has cyclic maximal
subgroups, and such $p$-groups have been classified. In particular, either $P$
is a generalized quaternion group or
$P=\mathbb{Z}_{p^{n-1}}\rtimes\mathbb{Z}_{p}$ for some $n\geq 3$ (if $n=2$
then $\beta(P)=1$ by [B]) with semidirect product structures considered below.

First, suppose $P=\langle x,y:x^{2^{k}}=1,\ y^{2}=x^{2^{k-1}},\
yxy^{-1}=x^{-1}\rangle$ is a generalized quaternion group of order $2^{k+1}$.
If $k=2$ then $P=Q_{8}$ and $\beta(Q_{8})=1$ by [B], so we may assume $k\geq
3$. In this case $\langle y\rangle\subsetneq\langle y,x^{2}\rangle$ and
$\langle xy\rangle\subsetneq\langle xy,x^{2}\rangle$. Since $y$ and $xy$
generate maximal cyclic subgroups of $P$ and $\langle
y,x^{2}\rangle\neq\langle xy,x^{2}\rangle$, we have $\beta(P)>2$.

If $P=D_{2^{n}}$ then $\beta(P)\neq 2$ by Lemma 3.1.

Next, suppose $P=\langle a,b:a^{2^{n-1}}=b^{p}=1,\
bab^{-1}=a^{-1+2^{n-2}}\rangle$ with $n\geq 4$. Then $\langle b\rangle$ is a
maximal cyclic subgroup and $\langle b\rangle\subsetneq\langle
a^{2^{n-2}},b\rangle\subsetneq\langle a^{2^{n-3}},b\rangle$, so $\beta(P)>2$.

It was shown in [[B], example 4.6.] that
$\beta(\mathbb{Z}_{p^{n-1}}\times\mathbb{Z}_{p})=n-1$, so in the abelian case
we must have $n=3$ as claimed.

Finally, suppose $P=\langle a,b:a^{p^{n-1}}=b^{p}=1,\
bab^{-1}=a^{1+p^{n-2}}\rangle$. Thus $a^{p}\in Z(G)$. If $n\geq 4$ then
$\langle b\rangle\subsetneq\langle b,a^{p^{2}}\rangle\subsetneq\langle
b,a^{p}\rangle$, and $\langle b\rangle$ is a maximal cyclic subgroup of $P$,
so $\beta(P)>2$. So assume $n=3$. If $p=2$ then $P=D_{8}$ which was already
ruled out. If $p>2$ then $\langle a^{p},b\rangle$ is the unique noncyclic
proper subgroup of $P$ and contains $\langle b\rangle$. Hence $\beta(P)=2$. ∎

Now consider the case where $G=A\rtimes P$ and is not nilpotent. We will show
that $\beta(G)\neq 2$. Recall $\langle x_{i}\rangle\supset A$ is a cyclic
maximal subgroup of $G$. Since $G\supsetneq C_{G}(A)\supset\langle
x_{i}\rangle$, the subgroup $C_{G}(A)=\langle x_{i}\rangle$ is a maximal
subgroup of $G$. Since $A\not\subset Z(G)$, $A$ is not cyclically embedded in
$G$. By Lemma 2.1, $\beta(P)=\beta(G/A)<\beta(G)=2$. By [B], either $P$ is
cyclic, $P=\mathbb{Z}_{p}^{2}$, or $P=Q_{8}$.

If $P=Q_{8}$ then, since $\operatorname{Aut}(A)$ is abelian,
$Z(Q_{8})=[Q_{8},Q_{8}]$ centralizes $A$. Thus $Z(Q_{8})$ is cyclically
embedded in $G$. By Lemma 2.1 it therefore suffices to consider the cases
where $P$ is cyclic or $P=\mathbb{Z}_{p}^{2}$. For such $P$ we see that
$A\supset[G,G]$ hence the maximal subgroup $C_{G}(A)$ is normal and so has
index $p$. If $P$ is cyclic then its unique index-$p$ subgroup centralizes
$A$, and is therefore cyclically embedded. By Lemma 2.1, we may then assume
$P=\mathbb{Z}_{p}$ or $\mathbb{Z}_{p}^{2}$. Let $n=|A|$.

Assume first that $P$ is a 2-group so $n$ is odd and $P\in\\{\mathbb{Z}_{2},\
\mathbb{Z}_{2}^{2}\\}$. If $n$ is a prime power then the only order-2
automorphism of $A$ is inversion. Let $g\in P\setminus C_{G}(A)$ and write
$A=A^{+}\times A^{-}$ where $A^{\pm}:=\\{a\in A:gag^{-1}=a^{\pm 1}\\}$; these
subgroups do not depend on the choice of $g$. It is easy to see that $A^{+}$
and $A^{-}$ are Hall subgroups of $A$. Since $A^{+}$ is cyclically embedded in
$G=A\rtimes P=(A^{-}\rtimes P)\times A^{+}$, we may assume $A=A^{-}$. If
$P=\mathbb{Z}_{2}$ then $G=D_{2n}$ and $\beta(D_{2n})\neq 2$. by Lemma 3.1. If
$P=\mathbb{Z}_{2}^{2}$ then
$G=D_{2n}\times\mathbb{Z}_{2}=(\mathbb{Z}_{n}\rtimes\mathbb{Z}_{2})\times\mathbb{Z}_{2}$.
The middle $\mathbb{Z}_{2}$ factor is a maximal cyclic subgroup contained in
the two distinct subgroups $D_{2n}$ and $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$,
so $\beta(G)=\beta(D_{2n}\times\mathbb{Z}_{2})>2$.

Now suppose $p>2$ and $P\in\\{\mathbb{Z}_{p},\ \mathbb{Z}_{p}^{2}\\}$. As
above, we may assume that no Sylow subgroup of $A$ is centralized by $P$,
since any such subgroup would have been a cyclically embedded direct factor of
$G$.

Assume first that $P=\mathbb{Z}_{p}$, so $P\cap C_{G}(A)=1$. Then
$C_{G}(P)=Z(G)P$ is a maximal cyclic subgroup of $G$ that contains no Sylow
subgroup of $A$. We will proceed by cases on $n$. Suppose $n$ is not a prime
power. If $Q_{1}$ and $Q_{2}$ are distinct Sylow subgroups of $A$ then
$Q_{1}C_{G}(P)$ and $Q_{2}C_{G}(P)$ are distinct proper subgroups containing
$C_{G}(P)$, so $\beta(G)>2$. So assume $n$ is a power of a prime $q$. Clearly
$Z(G)$ is cyclically embedded and $Z(G/Z(G))=1$. We have
$G/Z(G)=\mathbb{Z}_{q^{s}}\rtimes\mathbb{Z}_{p}$. If $s=1$ then
$\beta(G)=\beta(G/Z(G))=1$ by [B]. Suppose $s>1$ and let $a$ and $y$ denote
generators for $\mathbb{Z}_{q^{s}}$ and $\mathbb{Z}_{p}$, respectively. Then
$\langle y\rangle$ and $\langle ay\rangle$ are maximal cyclic subgroups of
order $p$, and are respectively contained in the distinct subgroups $\langle
y,a^{q}\rangle$ and $\langle ay,a^{q}\rangle$. Thus
$\beta(G)=\beta(G/Z(G))>2$.

Finally, suppose that $P=\mathbb{Z}_{p}^{2}$. If $P_{1}=C_{G}(A)\cap P$ then
$P_{1}$ is a central subgroup of order $p$ but is not cyclically embedded.
Thus $2=\beta(G)>\beta(G/P_{1})=\beta(A\rtimes\mathbb{Z}_{p})$ by Lemma 2.1.
From above, $\beta(A\rtimes\mathbb{Z}_{p})>1$ unless $n$ is a power of a
prime, so we may assume this is the case. Then $\operatorname{Aut}(A)$ is
cyclic, so if $y\in P\setminus C_{G}(A)$ then $C_{A}(y)=Z(G)\cap A$. So
$\langle y,Z(G)\cap A\rangle$ is a maximal cyclic subgroup of $G$ and is
contained in the two proper subgroups $A\rtimes\langle y\rangle$ and $Z(G)P$.
Therefore $\beta(G)>2$.

##  5\. The case $G=P\rtimes A$

Suppose $G=P\rtimes A$ and is not nilpotent. Observe that $C_{G}(A)=\langle
x_{i}\rangle$ is a cyclic maximal subgroup as in the previous case. Clearly
$C_{G}(A)=C_{P}(A)\times A$. Let $\Phi(P)$ denote the Frattini subgroup of
$P$. We claim first that $\Phi(P)C_{P}(A)\neq P$. For otherwise $C_{P}(A)$
surjects onto $P/\Phi(P)$, and if $P/\Phi(P)$ is cyclic then $P$ is cyclic.
But then $\Phi(P)$ is the unique maximal subgroup of $P$, and since
$C_{P}(A)\neq P$ we obtain a contradiction.

Since $\Phi(P)$ is a characteristic subgroup of $P$, it is normal in $G$ and
$\Phi(P)C_{P}(A)\times A$ is a subgroup of $G$ containing $C_{G}(A)$. Since it
is proper by our previous claim, we must have $\Phi(P)\subset C_{P}(A)$, so
$C_{P}(A)$ is normal in $G$. In the next two propositions we classify those
nonnilpotent $G=P\rtimes A$ with $\beta(G)=2$ such that $\Phi(P)$ is trivial
and nontrivial, respectively. This will complete the proof of our final
classification.

######  Proposition 5.1.

Let $p$ be a prime, $P=\mathbb{Z}_{p}^{k}$, and $n>1$ with $(p,n)=1$. Suppose
$G=P\rtimes\mathbb{Z}_{n}$ is not nilpotent, where
$C_{P}(\mathbb{Z}_{n})\times\mathbb{Z}_{n}$ is a cyclic maximal subgroup of
$G$ and $C_{P}(\mathbb{Z}_{n})$ is normal in $G$. Then $\beta(G)=2$ if and
only if either

a) $k=2$ with $Z(G)=\mathbb{Z}_{n/d}$ for some prime divisor $d$ of $n$, and
no proper subgroup of $P$ is normalized by $\mathbb{Z}_{n}$, or

b) or $k=1$ with $Z(G)=\mathbb{Z}_{n/q^{2}}$ for a prime divisor $q$ of $n$.

###### Proof.

We first prove these conditions imply $\beta(G)=2$. In both cases $Z(G)$ is
cyclically embedded so we can replace $G$ by $G/Z(G)$ and note that
$Z(G/Z(G))=1$ for the given groups. So if a) holds then we may take $n$ to be
prime and if b) holds we may take $n$ to be the square of the prime $q$. In
case a) let $H=\mathbb{Z}_{p}\times\mathbb{Z}_{p}$, and in case b) let
$H=\mathbb{Z}_{p}\rtimes\mathbb{Z}_{q}$. In both cases, the maximal cyclic
subgroups of $G$ which are not maximal subgroups are all of order $p$, are
contained in $H$, and are in no other proper subgroup, so $\beta(G)=2$.

Now suppose that $\beta(G)=2$. Let $U=C_{P}(\mathbb{Z}_{n})$. Since $(p,n)=1$,
there is a subgroup $W\subset P$ with $P=UW$, $U\cap W=1$, and
$W\mathrel{\unlhd}G$ (consider $P$ as a vector space over the field with $p$
elements, and decompose it as a representation of $\mathbb{Z}_{n}$). Then
$W\neq 1$ since $G$ is nonabelian. If $W^{\prime}\subset W$ is a normal
subgroup of $G$ then $UW^{\prime}\rtimes\mathbb{Z}_{n}\supset
U\times\mathbb{Z}_{n}$. Since $U\times\mathbb{Z}_{n}$ is a maximal subgroup,
we must have $W^{\prime}=W$ or $W^{\prime}=1$. Let $1\neq x\in W$. Since
$C_{G}(x)\supset P$, it follows that $C_{G}(x)=P\rtimes\mathbb{Z}_{n/d}$ for
some divisor $d$ of $n$. Let $C$ be a maximal cyclic subgroup of $G$
containing $x$. Since $C\subset C_{G}(x)$ and $C\cap P=\langle x\rangle$, we
have $C=\langle x\rangle\times\mathbb{Z}_{n/d}$.

We claim $\mathbb{Z}_{n/d}\subset Z(G)$. To see this, let $a$ generate
$\mathbb{Z}_{n}$. Then $a^{d}\in C_{G}(a^{i}xa^{-i})$ for all
$i\in\mathbb{Z}$. However, the group generated by all $a^{i}xa^{-i}$, for
$i\in\mathbb{Z}$, is a nontrivial normal subgroup of $G$ contained in $W$.
Hence $a^{d}$ commutes with $W$. Since $a^{d}$ obviously commutes with $U$, we
have $a^{d}\in Z(G)$ as claimed.

Now suppose $k\geq 3$. Let $y_{1}\in P\setminus\langle x\rangle$ and $y_{2}\in
P\setminus\langle x,y_{1}\rangle$. If $H_{i}=\langle
y_{i},x,a^{d}\rangle\cong\mathbb{Z}_{p}\times\mathbb{Z}_{p}\times\mathbb{Z}_{n/d}$
then $H_{i}\supsetneq C$ and $H_{1}\neq H_{2}$. This implies $\beta(G)>2$, so
$1\leq k\leq 2$.

Suppose $k=2$. If $e$ is a proper divisor of $d$ then $C\subsetneq
P\times\mathbb{Z}_{n/d}\subsetneq P\times\mathbb{Z}_{ne/d}$, so $\beta(G)>2$.
Thus $d$ is prime. Now suppose $U\neq 1$, so $U\cong W\cong\mathbb{Z}_{p}$ and
$W=\langle x\rangle$. Then $C\subsetneq P\times\mathbb{Z}_{n/d}$ and
$C\subsetneq W\times\mathbb{Z}_{n}$, forcing $\beta(G)>2$. Thus $U=1$, no
proper subgroup of $P=W$ is normal in $G$, and $Z(G)=\mathbb{Z}_{n/d}$.

Finally, suppose $k=1$. Then $P=W=\langle x\rangle$ and $C$ is normal in $G$.
If $C$ is a maximal subgroup then $[G:C]=d$ is prime. Clearly
$G/Z(G)\cong\mathbb{Z}_{p}\rtimes\mathbb{Z}_{d}$ and $Z(G)$ is cyclically
embedded. By [B], this implies $\beta(G)=1$. Therefore $C$ is not a maximal
subgroup. Since $\beta(G)=2$ there is a unique proper subgroup containing $C$.
It follows that $G/C=\mathbb{Z}_{d}=\mathbb{Z}_{q^{2}}$ for some prime divisor
$q$ of $n$. The conclusion follows. ∎

######  Proposition 5.2.

Let $P$ be a $p$-group and $(p,n)=1$. Suppose $G=P\rtimes\mathbb{Z}_{n}$ is
not nilpotent, where $C_{P}(\mathbb{Z}_{n})\times\mathbb{Z}_{n}$ is a cyclic
maximal subgroup of $G$, $C_{P}(\mathbb{Z}_{n})\supset\Phi(P)\neq\\{1\\}$, and
$C_{P}(\mathbb{Z}_{n})$ is normal in $G$. Then $\beta(G)=2$ if and only if
either

a) $P=\mathbb{Z}_{p^{t}}$ with $t>1$ and
$Z(G)=\mathbb{Z}_{p^{t-1}}\times\mathbb{Z}_{n/q^{2}}$ for a prime divisor $q$
of $n$, or

b) $G=(Q_{8}\rtimes\mathbb{Z}_{3^{k}})\times\mathbb{Z}_{m}$ where $(m,6)=1$.

###### Proof.

Write $P/\Phi(P)=\mathbb{Z}_{p}^{k}$ for some $k\geq 1$. We consider cases
based on $k$.

If $k=1$ then $P$ is cyclic. Since $\Phi(P)\subset C_{P}(A)$, it follows that
$\Phi(P)$ is cyclically embedded in $G$. This shows that $G/\Phi(P)$ must a
group of the kind considered in part b) of the previous proposition.

Now suppose that $k\geq 2$. Let $K:=P/\Phi(P)=\mathbb{Z}_{p}^{k}$ so
$G/\Phi(P)=K\rtimes\mathbb{Z}_{n}$. The image $I$ of the cyclic maximal
subgroup $C_{G}(\mathbb{Z}_{n})=C_{P}(\mathbb{Z}_{n})\times\mathbb{Z}_{n}$ of
$G$ in $G/\Phi(P)$ is still cyclic and maximal. Clearly $I$ is contained in
$C_{K}(\mathbb{Z}_{n})\times\mathbb{Z}_{n}\subset G/\Phi(P)$. If
$I=C_{K}(\mathbb{Z}_{n})\times\mathbb{Z}_{n}$ then $G/\Phi(Q)$ is a group of
the type described by the Proposition 5.1. If $k\geq 3$ then the proof of that
proposition showed $\beta(\mathbb{Z}_{p}^{k}\rtimes\mathbb{Z}_{n})>2$. Thus
$\beta(G)\geq\beta(G/\Phi(P))>2$ and we can conclude that $k=2$. If
$I\subsetneq C_{K}(\mathbb{Z}_{n})\times\mathbb{Z}_{n}$ then maximality of $I$
forces $C_{K}(\mathbb{Z}_{n})\times\mathbb{Z}_{n}=G/\Phi(P)$. This implies
$G/\Phi(P)=K\times\mathbb{Z}_{n}$ is nilpotent. By Proposition 4.1 and [B], if
$k\geq 3$ this forces $\beta(G)\geq\beta(G/\Phi(P))>2$. Thus $k=2$ again.

Lastly, we consider the case $k=2$. The $p$-groups $P$ with cyclic Frattini
subgroup have been classified in [BKN]. Those with
$P/\Phi(P)=\mathbb{Z}_{p}^{2}$ are a substantially more restricted family.
Since such $P$ can be generated by two elements, it follows from remark (4) of
[BKN] that either $P$ is abelian or $|P|=p^{3}$.

If $P$ is abelian then $P=\mathbb{Z}_{p^{t}}\times\mathbb{Z}_{p}$ for some
$t\geq 2$. Clearly $\Phi(P)=\mathbb{Z}_{p^{t-1}}\subset Z(G)$ but is not
cyclically embedded. Thus $\beta(G)>\beta(G/\Phi(P))$ and
$G/\Phi(P)=\mathbb{Z}_{p}^{2}\rtimes\mathbb{Z}_{n}$ is nonnilpotent since $G$
is. The nonnilpotent case in [B] implies $\beta(G/\Phi(P))>1$, so
$\beta(G)>2$.

So assume $|P|=p^{3}$. If $P=\mathbb{Z}_{p^{2}}\rtimes\mathbb{Z}_{p}$ is
nonabelian, then $\Phi(P)\subset Z(G)$ is not cyclically embedded and the same
argument as in the abelian case shows $\beta(G)>2$. If $P$ is the Heisenberg
group of order $p^{3}$, with $p>2$, then the exact same argument again shows
$\beta(G)>2$. Finally, if $P=Q_{8}$ then $\operatorname{Aut}(Q_{8})=S_{4}$ and
so $G=Q_{8}\rtimes\mathbb{Z}_{3^{k}}\times\mathbb{Z}_{m}$ where $(6,m)=1$ and
$\mathbb{Z}_{3^{k}}$ acts on $Q_{8}$ by an automorphism of order 3. Note
$Z(G)=\mathbb{Z}_{2}\times\mathbb{Z}_{3^{k-1}}\times\mathbb{Z}_{m}$ is
cyclically embedded and
$G/Z(G)=(\mathbb{Z}_{2}\times\mathbb{Z}_{2})\rtimes\mathbb{Z}_{3}$ is a group
of the kind considered in Proposition 5.1 a), so $\beta(G)=\beta(G/Z(G))=2$. ∎

##  6\. Further work

There a various directions that one could take to strengthen or extend the
above results. We consider a few of them here.

The most obvious step would be a classification of $G$ with given
$\beta(G)>2$. We outline a beginning of how this might be achieved for
$\beta(G)=3$. If $H_{1},\ldots,H_{m}$ are distinct noncyclic subgroups of $G$
that appear in some irredundant cover, and $\\{\langle
x_{i}\rangle\\}_{i=1}^{n}$ are the maximal cyclic subgroups of $G$, then for
each $1\leq j\leq m$ there is an irredundant cover $\\{H_{j}\\}\cup\\{\langle
x_{i}\rangle:x_{i}\not\in H_{j}\\}$. Every irredundant cover of $G$ has the
form $\\{H_{j_{k}}\\}\cup\\{\langle x_{i}\rangle:x_{i}\not\in\bigcup
H_{j_{k}}\\}$ for a (possibly empty) subcollection $\\{H_{j_{k}}\\}$ of
$\\{H_{j}\\}_{j=1}^{m}$. So

$m+1\leq\beta(G)\leq 2^{m}.$

Clearly $\beta(G)=m+1$ if and only if, for every pair $\\{H_{j},H_{k}\\}$ with
$j\neq k$, the cover $\\{H_{j},H_{k}\\}\cup\\{\langle
x_{i}\rangle:x_{i}\not\in H_{j}\cup H_{k}\\}$ is not irredundant. So if
$\beta(G)=3$ then $m=2$, and since $G\neq H_{1}\cup H_{2}$, it follows that
$G$ contains cyclic maximal subgroups and hence is solvable.

It is shown in [B] that $\beta(G)$ can take on any possible integer, since
$\beta(\mathbb{Z}_{p^{n}}\times\mathbb{Z}_{p})=n$ if $p$ is prime. It should
be possible to determine $\beta(G)$ for any abelian $G$ in an explicit
fashion. More ambitiously, one may ask what structural information $\beta(G)$
determines when $G$ is a $p$-group, or nilpotent. Indeed, if $|H|$ and $|K|$
are coprime then

$\beta(H\times K)=\beta(H)+\beta(K)+\beta(H)\beta(K).$

This holds because all covers have the form $\\{H_{i}\times K\\}_{i\in I}$,
$\\{H\times K_{j}\\}_{j\in J}$, or $\\{H_{i}\times K_{j}\\}_{i\in I,j\in J}$
where $\\{H_{i}\\}_{i\in I}$ and $\\{K_{j}\\}_{j\in J}$ are covers of $H$ and
$K$, respectively. In particular, this reduces the computation of $\beta(G)$
for nilpotent groups to the case of $p$-groups.

One might similarly ask for a determination of $\beta(G)$ for other worthwhile
classes of $G$. For example, it is not hard to show directly from the lattice
of subgroups that $\beta(D_{8})=4$. One may reasonably seek the value of
$\beta(D_{2n})$, or more ambitiously $\beta(A_{n})$ and $\beta(S_{n})$.

We saw above that if $\beta(G)\leq 3$ then $G$ is solvable. It is natural to
seek the smallest value $M$ such that there exists a nonsolvable $G$ with
$\beta(G)=M$. Consideration of the case $G=A_{5}$ suggests $M$ may be
substantially larger than 3. One may also ask whether every integer larger
than $M$ can be $\beta(G)$ for some nonsolvable $G$, or if there are natural
obstructions.

In another direction, one could constrain the types of irredundant covers that
are permitted. For example, one might define the invariant $\beta_{N}(G)$ to
be the number of normal irredundant covers of $G$, meaning those covers
preserved by conjugation. Clearly $\beta_{N}(G)\leq\beta(G)$. As a consequence
of the work above, if $\beta(G)\leq 2$ then $\beta_{N}(G)=\beta(G)$. It is
unclear if the converse holds: if $1\leq\beta_{N}(G)\leq 2$ then may we have
$\beta(G)>\beta_{N}(G)$? Under what conditions on $G$ do we have
$\beta(G)=\beta_{N}(G)$? Can we classify $G$ with small $\beta_{N}(G)$?

## References

  * [B] Brodie, Marc A. “Uniquely covered groups.” Algebra Colloq. 10 (2003), no. 1, 101–108.
  * [Bh] Bhargava, Mira. “Groups as unions of proper subgroups.” The American Mathematical Monthly 116.5 (2009): 413-422.
  * [BKN] Berger, T. R., L. G. Kovács, and M. F. Newman. “Groups of prime power order with cyclic Frattini subgroup.” Indagationes Mathematicae (Proceedings). Vol. 83. No. 1. North-Holland, 1980.
  * [PK] Pylaev, V. V.; Kuzennyĭ, N. F. “Finite groups that have a cyclic maximal subgroup.” (Russian) Ukrain. Mat. Ž. 28 (1976), no. 5, 646–-654, 717.


11institutetext: Jerrin Thomas Panachakel22institutetext: Dept. of Electrical
Engineering
Indian Institute of Science
Bangalore
22email<EMAIL_ADDRESS>33institutetext: Anurenjan P.R.44institutetext:
Dept. of Electronics and Communication Engineering
College of Engineering
Trivandrum
44email<EMAIL_ADDRESS>
# High Resilience Diverse Domain Multilevel Audio Watermarking with Adaptive
Threshold

Jerrin Thomas Panachakel  Anurenjan P.R

###### Abstract

A novel diverse domain (DCT-SVD & DWT-SVD) watermarking scheme is proposed in
this paper. Here, the watermark is embedded simultaneously onto the two
domains. It is shown that an audio signal watermarked using this scheme has
better subjective and objective quality when compared with other watermarking
schemes. Also proposed are two novel watermark detection algorithms viz., AOT
(Adaptively Optimised Threshold) and AOTx (AOT eXtended). The fundamental idea
behind both is finding an optimum threshold for detecting a known character
embedded along with the actual watermarks in a known location, with the
constraint that the Bit Error Rate ($BER$) is minimum. This optimum threshold
is used for detecting the other characters in the watermarks. This approach is
shown to make the watermarking scheme less susceptible to various signal
processing attacks, thus making the watermarks more robust.

##  1 Introduction

The earliest reference in literature about audio watermarking is a patent
titled, “Identification of sound and like signals,” filed by Emil Hembrooke of
the Muzac Corporation in the year 1954 1 ,2 . Ever since then, many
watermarking algorithms have been developed and deployed. Interestingly, the
field of application of watermarking itself witnessed a gradual change. Today,
watermarking finds wider applications such as transaction tracking, copyright
protection, access control, broadcast monitoring etc. A good description of
these applications can be found in 5 . Recently, watermarking has been used
for patient identification, tampering detection etc. in wirelessly transmitted
biomedical data such as ECG 6 . All these applications requires the watermark
to have one or more of the following properties,

  1. 1.

Robustness: A watermark is said to be robust if it can survive common signal
processing operations (commonly referred contextually as signal processing
attacks) such as compression, re-sampling etc. 5 . A resourceful pirate can
defeat a watermarking scheme by making it impossible to detect a watermark or
making the scheme unreliable (i.e., a watermark is detected when no watermark
is actually embedded) 7  both of which should be prevented. Some applications
do not require the watermark to be robust and the watermarking schemes used in
these applications are referred to as fragile watermarking schemes 3 .

  2. 2.

Tamper Resistance: Tamper resistance refers to the watermark’s ability to
resist hostile attacks such as,

     * •

Passive attacks where the hacker tries to determine whether a watermark is
present i.e. is trying to identify a covert communication.

     * •

Active attacks where the hacker tries to remove the watermark.

     * •

Forgery attack where the hacker tries to embed a new watermark 11 .

Collusion attack is a special type of active attack where the hacker uses
several copies of a work to produce a copy with no watermark 8 .

  3. 3.

Fidelity: A watermarking technique is said to have high fidelity if it causes
only imperceptible degradation on the host signal. For instance, if the host
signal is an audio data, it should be difficult to distinguish by hearing the
original audio and the audio signal with the watermark embedded. This
criterion is often referred to as the perpetual transparency requirement.

  4. 4.

Payload: Payload refers to the amount of information that can be embedded into
the given host signal. We require high payload while maintaining high
perceptual transparency.

  5. 5.

Erasability: In applications such as watermarking ECG signals in wireless
transmission of biomedical signal, we require that the original host signal be
recovered from the watermark signal.

Many watermarking schemes can be found in literature. These schemes can be
broadly classified into two groups,

  1. 1.

Transform domain watermarking where the watermark is embedded into the
coefficients of the host in a transformed domain, like Discrete Wavelet
Transform (DWT) 12 , 13 , 14 , 15 , Discrete Cosine Transform (DCT), 17 , 18 ,
Discrete Fourier Transform (DFT) 19 , 20 , 21 , 22 , DWT-SVD (Singluar Value
Decomposition) 23 , etc., and

  2. 2.

Spatial mode watermarking where embedding is done in the spatial domain
itself, like the schemes given in 25  and 26 .

Based on the host signal, the watermarking can be audio watermarking, image
watermarking, biomedical signal watermarking etc.

Depending on the applications, the requirements on the watermarking scheme
varies. This paper proposes a watermarking scheme in which one watermark in
embedded in the DWT-SVD domain and the other watermark in the DCT-SVD domain.
The watermarking in the DWT-SVD domain follows 23  but a novel watermarking
scheme is followed in the DCT-SVD domain. Two different domains need to be
used to avoid the interference between the two watermarks 28 . Also, two novel
generic watermark extraction algorithms viz. , AOT (Adaptively Optimised
Threshold) and AOTx (AOT eXtended) are also proposed, which can be combined
with any watermarking scheme that uses the ratio between a derived value
(value obtained after applying transformation, decompositions, etc.) of the
watermarked signal and the key (which is again a derived value but of the
original host signal) as a threshold for extracting the watermark. It is shown
that for the same payloads, the proposed diverse domain watermarking schemes
outperforms conventional watermarking schemes in terms of imperceptibility.
Also, it is shown that the use of AOT and AOTx at the detector side improves
the robustness of the algorithm to various signal processing operations.

The rest of this paper is organised as follows, Section 2 gives an overview of
the watermarking scheme; Subsections 2.2 and 2.3 discusses the embedding and
extraction algorithms respectively. The performance metrics used for
comparison are discussed briefly in Section 3. Finally, the results of the
comparison of the proposed watermarking scheme with other watermarking schemes
in terms of Bit Error Rate ($BER$) when the transmitted signal is corrupted by
varying amounts of Additive White Gaussian Noise (AWGN), Mean Opinion Score
($MOS$) criterion for different genres and $BER$ when subjected to various
signal processing attacks are given in Section 4.

##  2 Proposed Watermarking Scheme

###  2.1 Overview

Most of the multilevel watermarking algorithms found in literature are for
either image watermarking 27 , 28  or for audio watermarking 29 , 29 ,
although a few works discuss about watermarking in other signals such as ECG
signal 6 . M. Butman et al. propose a three level watermarking scheme in 28
in which spatial domain, DCT domain and wavelet domain are used for embedding
watermarks in three levels. The primary purpose of this scheme is to detect
tampering 28 . Contrary to this approach, S. Naveen et.al. 29  use wavelet
domain for multiple embedding with the primary purpose of increasing the
payload. The primary disadvantage of the scheme by S. Naveen et al. is that
the secondary and further watermarks can be recovered only under ideal
conditions (noise free conditions) 29 . But in the proposed watermarking
scheme, the primary and secondary watermarks can be recovered even under non-
ideal conditions. The use of Singular Value Decomposition (SVD) improves the
imperceptibility (transparency) and robustness of the watermark 23 , 29 .

In almost all non-blind or informed watermarking schemes 5 , the watermark
extraction involves the comparison of the derived value of the embedded signal
received at the receiver with a key generated at the embedding stage. But due
to noise or some signal processing attacks, the derived value of the embedded
signal obtained at the receiver may vary from its actual value i.e., the value
just before the transmission stage (it is assumed that the corruption with
noise, signal processing attacks, etc. occur in the transmission stage). This
alters the ratio between the derived value and the key and this in turn will
result in wrong decisions in the extraction stage. Adaptively Optimised
Threshold (AOT) and AOTx (AOT eXtended) aim to minimise, if not eliminate
completely, the error caused in this manner. The fundamental idea behind both
AOT and AOTx is to embed a known character at a known location in the host
signal, along with the original watermarks. At the receiver, the threshold of
the detector is optimised so that $BER$ of the detected watermark character at
the location where the known character is embedded is minimum and this
threshold is used for detecting the other characters in the watermarks. AOTx
is superior to AOT in terms of the ability to determine the optimum threshold
but has a cyclomatic complexity which is $6$ times higher than that of the
latter, thus making it computationally infeasible to apply AOTx at both
levels.

###  2.2 Embedding Algorithm

Figure 1: HLD of multilevel watermarking scheme.

The high level diagram of the embedding process of the proposed watermarking
scheme is given in Fig.1. Practically, there is only little significance in
which watermarking is done first, whether it is the DCT-SVD or DWT-SVD, even
though the watermarking is not strictly linear. In this work, DWT-SVD domain
watermarking was done first followed by DCT-SVD domain watermarking. The two
watermarking algorithms are discussed below.

#### DWT-SVD Domain

The watermarking scheme developed by Ali Al-Haj et al. described in 23  is
used in this level, the only difference being that instead of binary image,
the watermark is a text. Nevertheless, for the completeness of the discussion,
the steps in the DWT-SVD watermarking scheme by Ali Al-Haj et al. are given
below,

  * •

STEP 1: The data to be watermarked, say $W$ is converted into its equivalent
ASCII numbers and these ASCII numbers are converted to binary. Let the number
of bits in the binary representation be $N$.

  * •

STEP 2: The host audio signal is divided into $N$ frames. It is assumed that
there are sufficient number of samples in the audio signal for this division.
If the length of the audio signal, denoted as $L$ is not a multiple of $N$
sufficient zeroes are padded to the audio signal such that the new length
$L^{\prime}$ is a multiple of $N$.

  * •

STEP 3: Four level DWT is performed on each frame to obtain the details sub-
bands $D_{1}$, $D_{2}$, $D_{3}$ and $D_{4}$ and approximate sub-band $A_{4}$.

  * •

STEP 4: Arrange the details sub-bands as shown in Fig. 2.

Figure 2: Matrix formulation of X.

  * •

STEP 5: Perform SVD operation on $X$ to obtain the orthogonal matrix $U,$
diagonal matrix $S$ and the unitary matrix $V,$ all of which are real $4\times
4$ matrices as given by the following equation,

$SVD(X)=USV^{T}$ (1)

  * •

STEP 6: Let the non-zero elements in the $n^{th}$ diagonal matrix $S_{n}$,
corresponding to the $n^{th}$ frame be denoted as $S_{11}$, $S_{22}$, $S_{33}$
and $S_{44}$. Modify the value of the diagonal element $S_{11}$ as follows,

$S_{11}=S_{11}\times(1+\alpha\times w(n))$ (2)

where $\alpha$ is the watermark intensity, $w(n)$ is the $n^{th}$ watermark
bit which is either $0$ or $1$. Higher the value of $\alpha$, more perceptible
will the watermarking be. Lower values of $\alpha$ will make the detection
more prone to errors. The original value of $S_{11}$, corresponding to each
frame is stored as the “key”.

  * •

STEP 7: Perform the inverse operations using the modified diagonal matrix to
obtain the watermarked frame.

  * •

STEP 8: Combine all frames to obtain the watermarked signal.

Figure 3: HLD of DWT-SVD watermarking.

The high level diagram of DWT-SVD watermarking is given in Fig. 3.

#### DCT-SVD Domain

The embedding in the DCT-SVD domain follows a novel approach and is performed
as follows:

  * •

STEP 1: The data to be watermarked, say $W$ is converted into its equivalent
ASCII numbers and these ASCII numbers are converted to binary. Let the number
of bits in the binary representation be $N$.

  * •

STEP 2: The host audio signal is divided into $N$ frames. It is assumed that
there are sufficient number of samples in the audio signal for this division.
If the length of the audio signal, denoted as $L$ in not a multiple of $N$,
sufficient zeroes are padded to the audio signal such that the new length
$L^{\prime}$ is a multiple of $N$.

  * •

STEP 3: Apply DCT transformation on each frame.

  * •

STEP 4: Form the matrix $X$ for each frame by using the first three, middle
three and last three elements of each transformed frame as shown in Fig.4.

Figure 4: Formation of matrix $X$ in DCT-SVD watermarking.

  * •

STEP 5:  Perform Singular Value Decomposition (SVD) operation on $X$ to obtain
the orthogonal matrix $U,$ diagonal matrix $S,$ and the unitary matrix $V,$
all of which are real $3\times 3$ matrices as given by the following equation,

$SVD(X)=USV^{T}$ (3)

  * •

STEP 6: Let the non-zero elements in the $n^{th}$ diagonal matrix $S_{n}$ be
denoted as $S_{11}$, $S_{22}$ and $S_{33}$. Modify the value of the diagonal
element $S_{11}$ as follows,

$S_{11}=S_{11}\times(1+\alpha\times w(n))$ (4)

where $\alpha$ is the watermark intensity, $w(n)$ is the $n^{th}$ watermark
bit which is either $0$ or $1$. The original value of $S_{11}$ is stored as
the “key”. Let the modified $S$ matrix be denoted as $S^{\prime}$.

  * •

STEP 7: Obtain matrix $X^{\prime}$ as,

$X^{\prime}=US^{\prime}V^{T}$ (5)

  * •

STEP 8: $X^{\prime\prime}$ is obtained by applying inverse DCT on
$X^{\prime}$. Apply the inverse of the operation performed in STEP 4 to obtain
the watermarked frame.

  * •

STEP 7: Combine the $N$ watermarked frames to obtain the watermarked audio
signal.

Figure 5: HLD of DCT-SCD watermarking.

The high level diagram of DCT-SVD watermarking is given in Fig. 5.

###  2.3 Extraction

For extraction, the inverse of the operations performed in the watermarking
stage is performed. The watermark embedded last is extracted first and the one
embedded first is extracted last. Though it may not be a necessary step in
many watermarking schemes, here we require the audio signal onto which the
embedding was done should be recovered at least after the first extraction
since this proves critical in extracting the next watermark with least error.
The algorithm for extracting the watermark if a static threshold (threshold
determined during the embedding stage) is used is as follows;

Performs STEPS 1-5 described in Subsection 2.2 and in Subsection 2.2 for
extracting the watermark embedded in the DWT-SVD domain and DCT-SVD domain
respectively. Let the first element in the diagonal matrix obtained after
applying Singluar Value Decomposition (SVD) be denoted as $S^{\prime}_{11}$
and the same obtained in case of the original audio signal be denoted as
$S_{11}$. It may be noted that it was these original values that were stored
as the “key” in both domains. Theoretically, we detect the watermarked bit
using the following rule,

$\displaystyle if\ (\frac{S^{\prime}_{11}}{S_{11}}\ ==\ th),\ then\ w(n)=1$
$\displaystyle else\ w(n)=0$

where $w(n)$ is the $n^{th}$ watermarked binary bit and $th$ is the threshold
which is equal to $(1+\alpha)$ where $\alpha$ is the watermark intensity.
Practically, we do not go for a stringent condition as above, instead, we give
an allowance to accommodate errors by replacing the equality condition with a
comparative condition like,

$\displaystyle if\ (\frac{S^{\prime}_{11}}{S_{11}}\ \geq\ th^{\prime}),\ then\
w(n)=1$ $\displaystyle else\ w(n)=0$

where $th^{\prime}$ may be less than $th$ by a fraction of the value of $th$.

Now, when the transmitted signal gets modified due to some reasons such as
addition of noise, signal processing operations, etc., the value of
$S^{\prime}{11}$ varies. Unless and otherwise a similar change in incorporated
in either the “key” or the “threshold”, the detections in the receiver side
can go wrong. AOT and AOTx modifies the “threshold” to what we refer to as the
optimum threshold so that the detection errors are minimised.

AOT is used for DCT-SVD watermark extraction and AOTx is used for DWT-SVD
watermark extraction. Once the optimum threshold is determined for each
domain, these optimum thresholds are used for detecting the other characters
embedded in the host signal in the respective domains. How AOT and AOTx are
used for obtaining the optimum thresholds is as follows.

#### Adaptively Optimised Threshold (AOT)

Both AOT and AOTx are used for determining the optimum threshold that will
minimise the $BER$ at the detector. AOT and AOTx requires a known character to
be embedded in a known location. The character “U” is chosen as the “known
character” because the ASCII of “U” is $85$, which in binary notation is
$1010101$, i.e., it has ‘1’s and ‘0’s in alternate locations, making the
software programming easier. Also, it is the best go for a character having
equal number of ‘1’s and ‘0’s in the binary of its ASCII equivalent.

Consider an audio signal in which a watermark in embedded along with the
character “U” which in embedded as the first character in the watermark.
Perform STEPS 1 to 5 given in Subsection 2.2. Let the non-zero elements in the
$n^{th}$ diagonal matrix $S_{n}$ be denoted as $S_{11}$, $S_{22}$ and
$S_{33}$. Also, let the $n^{th}$ watermark bit be denoted as $w(n)$. Note that
in this case, $w(0)=1$, $w(1)=0$, $w(2)=1$, $w(3)=0$, $w(4)=1$, $w(5)=0$ and
$w(6)=1$. Let $k(n)$ denote the original value of the top left element in the
diagonal matrix obtained by performing SVD on the DCT applied frame, which can
be obtained from the “key”. We define the following $6$ thresholds,

$\displaystyle thd_{0}=w(0)/k(0)$ (6) $\displaystyle thd_{1}=w(1)/k(1)$ (7)
$\displaystyle thd_{2}=w(2)/k(2)$ (8) $\displaystyle thd_{3}=w(3)/k(3)$ (9)
$\displaystyle thd_{4}=w(4)/k(4)$ (10) $\displaystyle thd_{5}=w(5)/k(5)$ (11)
$\displaystyle thd_{6}=w(6)/k(6)$ (12)

Note that $thd_{0}$, $thd_{2}$, $thd_{4}$ and $thd_{6}$ correspond to bit $1$
and $thd_{1}$, $thd_{3}$ and $thd_{4}$ corresponds to bit $0$. The optimum
threshold, $th_{opt}$ is given by,

$th_{opt}=max(th0)+\frac{min(th1)-max(th0)}{2}$ (13)

where $th0$ is a vector formed using $thd_{1}$, $thd_{3}$ & $thd_{5}$ and
$th1$ is a vector formed using $thd_{0}$, $thd_{2}$, $thd_{4}$ and $thd_{6}$.

Figure 6: Optimum threshold in AOT.

Determination of optimum threshold $th_{opt}$ is shown graphically in Fig. 6.

#### Adaptively Optimised Threshold eXtended (AOTx)

AOTx has $3$ stages; the first stage is exactly similar to AOT. The threshold
obtained from this stage is denoted as $th$. We define two variables $ze$ and
$oe$. $ze$ is the ratio of number of ‘1’s detected as ‘0’s to the total number
of ‘1’s and $oe$ is the ratio of number of ‘0’s detected as ‘1’s to the total
number of ‘0’s. Clearly, the $BER$ is a linear combination of $ze$ and $oe$.
For the character “U”, $ze$, $oe$ and $SNR$ are related as,

$SNR=\frac{oe\times 4+ze\times 3}{7}$ (14)

What we are trying to achieve in AOTx is to minimise the sum of $ze$ and $oe$;
i.e. we are actually minimising the $BER$.

If $ze$ is greater than $oe$, it means that the threshold is set at a lower
value and therefore should be raised. Similarly, if $oe$ is greater than $ze$,
it means that the threshold is set at a higher value and therefore should be
lowered. If both $ze$ and $oe$ are $0$, it means that $th$ is the optimum
threshold and there is no need for further optimisation.

In the actual implementation, the updating rule is as follows:

$\displaystyle if\ (ze>oe),\ then\ th=th+\frac{th}{2}$ $\displaystyle if\
(ze==0\ and\ oe==0),\ then\ th_{opt}=th;\ flag=1;$ $\displaystyle else\
th=th-\frac{th}{2}$

Figure 7: AOTx: Level 2.

This is shown graphically in Fig. 7. $flag$ is set when the optimum threshold
is identified so that the final level of optimisation can be skipped to
improve the computational time. In level 2, the change in threshold is rather
coarse and during the implementation, we encountered situations where the
thresholds determined in each subsequent iterations where oscillating between
two values and the actual optimum threshold was between these two values. It
is this observation that motivated us to design a third level in AOTx.

If the $flag$ is set in level 2, level 3 is skipped. If it isn’t set, the
updating rule is similar to that of level 2 except that instead of having a
coarse variation, we now have a fine variation as shown below,

$\displaystyle if\ (flag\ =\ 0),\ then\ th{opt}=th;\ break$ $\displaystyle if\
(ze>oe),\ then\ th=th+\frac{th}{10}$ $\displaystyle else\ th=th-\frac{th}{10}$

##  3 Performance Metrics

The performance of the proposed watermarking scheme is compared with other
watermarking techniques viz. DWT-SVD watermarking 23 , simple multilevel
watermarking with static threshold, multilevel watermarking with AOT in DCT-
SVD domain and AOTx in DWT-SVD domain, double embedding (multilevel)
watermarking proposed by S. Naveen et al. in 29  (referred to hereafter as
“Double Embedding”) and DCT-SVD domain watermarking with static threshold
(referred to hereafter as “DCT-SVD based watermarking”). The static thresholds
are decided at the watermark embedding stage itself. It may be noted that the
DWT-SVD domain watermarking proposed by Ali Al-Haj et al. has been shown in 23
to surpass the STFT-SVD based watermarking proposed by H. Ozer. et al. 30  and
DCT based watermarking 31  proposed by I. Cox et al..

Three criteria are used for performance analysis,

Table 1: MOS Grading Scale MOS | Description
---|---
5 | Imperceptible
4 | Perceptible but not annoying
3 | Slightly annoying
2 | Annoying
1 | Very annoying

  1. 1.

Mean Opinion Score ($MOS$): $MOS$ gives a numerical value for the perceived
quality of a signal. $MOS$ was used in this work to analyse the perceivable
difference of the audio quality, i.e. it is a measure of the transparency of
the watermarking algorithm. $5$ scale $MOS$ is usually used with $5$ being the
best value and $1$ being the worst value. The $MOS$ grading scale is given in
Table I. Conventionally, $MOS$ is calculated by conducting listening test 23 .
Contrary to this, we used “AQuA - Audio Quality Analyzer” developed by Sevana
Oy (a Finnish limited company founded in 2003, providing software development
and services including a voice quality assessment software) for performing
audio quality tests.

  2. 2.

BIT Error Rate ($BER$): $BER$ was used to evaluate the watermark detection
accuracy when the host signal is subjected to signal processing attacks,
corrupted by noise etc. BER is defined as 32 , 23 ,

$BER(W,\tilde{W})=\frac{\sum\limits_{i=1}^{siz}W(i)\oplus\tilde{W}(i)}{siz}$
(15)

For the watermarking schemes that doesn’t support two simultaneous watermarks,
the two watermarks are concatenated and $W$ denotes the concatenated watermark
and $\tilde{W}$ denotes the watermark recovered at the detector. $siz$
corresponds to the size of the concatenated watermark, i.e. $W$. For the
watermarking schemes that support multiple watermarks, $BER$ corresponding to
both watermarks are calculated using the method described above and the
average of the two is taken as the actual $BER$.

  3. 3.

Signal to Noise Ratio ($SNR$):  $SNR$ is used to measure the objective quality
of the watermarked signal 33 . According to the recommendations of
International Federation on Phonographic Industry (IFPI), the $SNR$ of a
watermarked audio signal should be at least $20dB$.

$SNR$ is formulated in 32  as:

$SNR(X,\tilde{X})=10\log_{10}\frac{\sum\limits_{l=1}^{L}X(i)^{2}}{\sum\limits_{l=1}^{L}(X(i)-\tilde{X}(i)^{2})}dB$
(16)

where $L$ is the number of samples in the original host signal $X(i)$ and the
watermarked signal $\tilde{X(i)}$.

##  4 Results

Figure 8: (a) Waveform of original host audio signal (b) Waveform of the
watermarked audio signal Table 2: $BER$ of various watermarking schemes when
subjected to different signal processing attacks.

Type of Attack Watermarking Scheme | Double Embedding | Multilevel | Multilevel with AOT | DCT-SVD Domain | DWT-SVD Domain
---|---|---|---|---|---
Power Supply Hum | 0.00 | 0.00 | 0.00 | 0.36 | 0.36
Amplification | 0.21 | 0.42 | 0.00 | 0.42 | 0.42
Delay | 0.21 | 0.14 | 0.14 | 0.42 | 0.42
Inversion | 0.00 | 0.00 | 0.00 | 0.00 | 0.00
Linear Transform and Sparsification | 0.35 | 0.14 | 0.00 | 0.35 | 0.50

The proposed watermarking scheme was simulated in MATLAB® 2012a (7.14). The
waveform of the original host audio signal, which was of instrumental genre
and the watermarked audio signal are given in Fig.8. The watermark text in the
DCT-SVD domain was “Jerrin Thomas Panachakel” and that in the DWT-SVD domain
was “College of Engineering, Trivandrum, India”. There were $24$ characters in
the first watermark and the number of binary bits was $168$. Similarly, the
number of characters in the second watermark was $41$ and the number of binary
bits was $287$. The character ’U’ was embedded in the first frame of both
domains for facilitating the use of AOT and AOTx. The watermark intensity used
was $\alpha=0.05$.

h!

Figure 9: $BER$ v/s $SNR$ for different genres. (a) Carnatic (b) Instrumental

h!

Figure 10: $BER$ v/s $SNR$ for different genres. (a) Ballad (b) Pop Rock (c)
Speech

###  4.1 Bit Error Rate (BER)

#### AWGN Channel

Watermarking was performed on several genres on audio signal and this audio
signal was corrupted with Additive While Gaussian Noise (AWGN) with varying
Signal to Noise Ratio ($SNR$). The $SNR$ was varied linearly from $0dB$ to
$100dB$ in steps of $10dB$. This is assumed to model an AWGN channel through
which the signal may pass during transmission. This assumption is supported by
the central limit theorem and hence can be considered fair. Plots between
$BER$ and $SNR$ for various genres are given in Fig. 9. and Fig. 10. It is
evident from the figure that Multilevel Watermarking with $AOT$ has the lowest
$BER$ when the watermark signal is corrupted by AWGN noise. The plots are not
monotonic in nature due to the randomness associated with the addition of
noise.

###  4.2 Signal processing attacks

The host signal was watermarked using various watermarking schemes with two
random watermarks if the scheme supports multiple watermarks or with the
watermark obtained by concatenating the two random watermarks if the scheme
supports only a single watermark. The watermarked signals were subjected to
various signal processing attacks such as:

  * •

Power supply hum: A $0.25V_{pp}$ sine wave of $50Hz$ is added to the
watermarked audio signals to simulate the effect of addition of power supply
hum. The corrupted watermarked signal was then processed for recovering the
watermarks.

  * •

Amplification: Each of the watermarked signals is amplified by $14dB$.

  * •

Delay: The watermarked signals are delayed by $100ms$.

  * •

Inversion: All the samples in the watermarked signals are inverted.

  * •

Linear Transformation and Sparsification: Discrete Cosine Transform (DCT) was
applied on the watermarked signals and the DCT coefficients whose absolute
magnitude was less than $0.05$ was made zero. In our work, a speech signal was
used as the host signal and $68\%$ of the DCT coefficients were less than
$0.05$ and was hence made zero. These operations were done to model the
effects of a lossy compression.

After applying the above signal processing operations, the resultant
watermarked signal was processed for recovering the watermark signal. Contrary
to the approach by Naveen et al. in 29  where filtering was done prior to
extraction, we attempted the recovery of the watermark without filtering the
corrupted watermarked signal. The $BER$ between the original signal and the
watermarked signal of various watermarking schemes when subjected to the above
signal processing attacks is given in Table II. In all the cases, the proposed
watermarking scheme has comparative, if not better performance, i.e. lowest
$BER$.

###  4.3 Mean Opinion Score ($MOS$) and Signal to Noise Ratio ($SNR$)

Table 3: $MOS$ and $SNR$ values for $\alpha=0.05$ Watermarking Technique | MOS | SNR (dB)
---|---|---
Double Embdedding | 4.55 | 27.00
Multilevel Watermarking | 4.58 | 33.20
DCT-SVD | 4.33 | 60.24
DWT-SVD | 4.33 | 30.45
Table 4: $MOS$ and $SNR$ values for $\alpha=0.1$ Watermarking Technique | MOS | SNR (dB)
---|---|---
Double Embdedding | 4.37 | 20.76
Multilevel Watermarking | 4.55 | 27.18
DCT-SVD | 4.26 | 54.11
DWT-SVD | 4.24 | 24.42

The $MOS$ and $SNR$ values were calculated for different watermark intensities
$\alpha=0.05$ & $\alpha=0.1$ for a speech signal sampled at $8KHz$ and is
shown in Table III & IV. Clearly, the proposed technique has better $MOS$
values, proving our argument that watermarking on two diverse domains has
better subjective quality than watermarking on a single domain. The values
obtained for $SNR$ satisfies the International Federation on Phonographic
Industry (IFPI) recommendations. It is interesting to note that although the
DCT-SVD domain based watermarking is vulnerable to signal processing attacks,
it has an $SNR$ greater than the value specified by IFPI for a watermarked
audio signal, $60.24dB$ and $54.11dB$ for $\alpha$ values $0.05$ and $0.1$
respectively. These values are highest when compared to the values of other
watermarking schemes discussed. Also, the $MOS$ values for DCT-SVD domain
watermarking is comparable to multilevel watermarking.

##  5 Conclusion

Novel multilevel watermarking in diverse domains, DCT-SVD domain based
watermarking and two generic watermark extraction algorithms viz., Adaptively
Optimised Threshold (AOT) and AOT eXtended (AOTx) are discussed. The proposed
watermarking algorithm has better subjective and objective quality, which is
evident from the higher $SNR$ and $MOS$ values. The use of AOT and AOTx at the
detection stage makes the watermarking schemes less susceptible to various
signal processing attacks although the proposed technique fails for geometric
signal processing attacks such as cropping, addition of delay etc. This
demerit can be addressed and resolved by using synchronisation codes. The fact
that AOT and AOTx are generic algorithms which can be incorporated in several
existing watermarking schemes to improve their susceptibility towards signal
processing attacks opens up a wide range of applications for both. Also, the
developed DCT-SVD domain based watermarking has the highest $SNR$ eventhough
it is more susceptible to signal processing attacks. Hence, this can be used
as a “fragile watermarking scheme”.

## Acknowledgement

We would like to place on record our deepest gratitude to

  * •

Mr. Valeri Sitnikov of “Sevana Oy” for providing us a free evaluation version
of their product, “AQuA - Audio Quality Analyzer” for this work.

## References

  * (1) Cox, I.J., Miller, M.L.:  The first 50 years of electronic watermarking.  EURASIP J. Appl. Signal Process. 2002 (2002) 126–132
  * (2) Frank, H.E.:  Identification of sound and like signals (1961)
  * (3) Cox, I.J., Miller, M.L., Bloom, J.A.:  Watermarking applications and their properties.  In: International Conference on Information Technology: Coding and Computing. (2000) 6–10
  * (4) Kaur, S., Farooq, O., Singhal, R., Ahuja, B.:  Digital watermarking of ecg data for secure wireless commuication.  In: Recent Trends in Information, Telecommunication and Computing (ITC), 2010 International Conference on. (2010) 140–144
  * (5) Swanson, M.D., Zhu, B., Tewfik, A.H., Boney, L.:  Robust audio watermarking using perceptual masking.  Signal Process. 66 (1998) 337–355
  * (6) Cvejic, N.:  Algorithms for Audio Watermarking and Steganography.  Acta Universitatis Ouluensis: Technica. Oulun yliopisto (2004)
  * (7) Craver, S., Memon, N., Yeo, B.L., Yeung, M.:  Resolving rightful ownerships with invisible watermarking techniques: limitations, attacks, and implications.  Selected Areas in Communications, IEEE Journal on 16 (1998) 573–586
  * (8) Cox, I.J., Kilian, J., Leighton, F., Shamoon, T.:  Secure spread spectrum watermarking for multimedia.  Image Processing, IEEE Transactions on 6 (1997) 1673–1687
  * (9) Podilchuk, C., Zeng, W.:  Image-adaptive watermarking using visual models.  IEEE J. Select. Areas Commun. 16 (1998) 525–539
  * (10) Kaewamnerd, N., Rao, K.:  Wavelet based image adaptive watermarking scheme.  Electronics Letters 36 (2000) 312–313
  * (11) Piva, A., Bartolini, F., Boccardi, L., Cappellini, V., De Rosa, A., Barni, M.:  Watermarking through color image bands decorrelation.  In: Multimedia and Expo, 2000. ICME 2000. 2000 IEEE International Conference on. Volume 3. (2000) 1283–1286 vol.3
  * (12) Luo, L., Chen, Z., Chen, M., Zeng, X., Xiong, Z.:  Reversible image watermarking using interpolation technique.  Information Forensics and Security, IEEE Transactions on 5 (2010) 187–193
  * (13) Shih, F.Y., Wu, Y.T.:  Decomposition of binary morphological structuring elements based on genetic algorithms.  Computer Vision and Image Understanding 99 (2005) 291 – 302
  * (14) Wei, Z., Ngan, K.:  Spatio-temporal just noticeable distortion profile for grey scale image/video in dct domain.  Circuits and Systems for Video Technology, IEEE Transactions on 19 (2009) 337–346
  * (15) Tsui, T.K., Zhang, X.P., Androutsos, D.:  Color image watermarking using multidimensional fourier transforms.  Information Forensics and Security, IEEE Transactions on 3 (2008) 16–28
  * (16) Shih, F.Y.:  Digital Watermarking and Steganography: Fundamentals and Techniques. 1st edn.  CRC Press, Inc., Boca Raton, FL, USA (2007)
  * (17) Tsui, T.K., Zhang, X.P., Androutsos, D.:  Quaternion image watermarking using the spatio-chromatic fourier coefficients analysis.  In: Proceedings of the 14th annual ACM international conference on Multimedia. MULTIMEDIA ’06, New York, NY, USA, ACM (2006) 149–152
  * (18) Bas, P., le Bihan, N., Chassery, J.M.:  Color image watermarking using quaternion fourier transform.  In: Acoustics, Speech, and Signal Processing, 2003. Proceedings. (ICASSP ’03). 2003 IEEE International Conference on. Volume 3. (2003) III–521–4 vol.3
  * (19) Al-Haj, A., Mohammad, A.:  Digital audio watermarking based on the discrete wavelets transform and singular value decomposition.  European Journal of Scientific Research 39 (2010) 6–21
  * (20) Kalker, T., Haitsma, J.:  Efficient detection of a spatial spread-spectrum watermark in mpeg video streams.  In: Image Processing, 2000. Proceedings. 2000 International Conference on. Volume 1. (2000) 434–437 vol.1
  * (21) Hernández, J., Rodrı́guez, J., Pérez-González, F.:  Improving the performance of spatial watermarking of images using channel coding.  Signal Processing 80 (2000) 1261 – 1279
  * (22) Butman, M., Hel-Or, H.:  Multi-level watermarking with independent decoding.  In: Image Processing, 2001. Proceedings. 2001 International Conference on. Volume 2. (2001) 514–517 vol.2
  * (23) Shaikh, M., Dote, Y.:  A robust multilevel watermarking method for digital images using multiresolution wavelet decomposition.  In Roy, R., Köppen, M., Ovaska, S., Furuhashi, T., Hoffmann, F., eds.: Soft Computing and Industry.  Springer London (2002) 363–370
  * (24) Naveeen, S., Shiras, S., Nithin, N., Tony, J., Gayathri, K.:  Multiple audio marking using discrete wavelets transform and singular value decomposition.  In: Emerging Technologies, 2012. Proceedings. First National Conference on. Volume 1. (2012) 6–12
  * (25) Özer, H., Sankur, B., Memon, N.:  An svd-based audio watermarking technique.  In: Proceedings of the 7th workshop on Multimedia and security. MM&Sec ’05, New York, NY, USA, ACM (2005) 51–56
  * (26) Cox, I.J., Kilian, J., Leighton, F., Shamoon, T.:  Secure spread spectrum watermarking for multimedia.  Image Processing, IEEE Transactions on 6 (1997) 1673–1687
  * (27) K, V.B., Sengupta, I., Das, A.:  An adaptive audio watermarking based on the singular value decomposition in the wavelet domain.  Digital Signal Processing 20 (2010) 1547 – 1558
  * (28) Erçelebi, E., Batakçı, L.:  Audio watermarking scheme based on embedding strategy in low frequency components with a binary image.  Digital Signal Processing 19 (2009) 265 – 277