A Novel Approach to Construct Huffman Sequences with Low PAPR

Wenjian WANG, Zhi GU, Avik Ranjan ADHIKARY, Rong LUO

Summary :

The auto-correlation property of Huffman sequence makes it a good candidate for its application in radar and communication systems. However, high peak-to-average power ratio (PAPR) of Huffman sequence severely limits its application value. In this paper, we propose a novel algorithm to construct Huffman sequences with low PAPR. We have used the roots of the polynomials corresponding to Huffman sequences of length M + 1 to construct Huffman sequences of length 2M + 1, with low PAPR.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.7 pp.1003-1010
• Publication Date: 2024/07/01
• Publicized: 2023/10/31
• Online ISSN: 1745-1337
• DOI: 10.1587/transfun.2023EAP1062
• Type of Manuscript: PAPER
• Category: Communication Theory and Signals

1.  Introduction

Sequences with impulsive auto-correlation performance are desired in signal synchronization [1], compressed sensing [2], active sensing systems for medical [3], short-message communication, FIR system identification [4] and other application scenarios [5]. Due to the cost limitation of hardware, constant modulus sequences are generally used. However, it has been proved that constant modulus sequences with zero aperiodic auto-correlation sidelobe do not exist [6]. Huffman [7] proposed a non-constant modulus sequence in 1962, whose aperiodic auto-correlation sidelobes are zeros except for two time-shifts at both ends. Although the Huffman sequences have good correlation performance, the non-constant modulus property drastically reduces their applications to various communication systems. Finding a Huffman sequence whose energy distribution is as uniform as possible (close to constant modulus) has always been a subject of widespread concern.

Ackroyd [8] proposed a Huffman sequence generation method based on Schroeder phase stationary principle [9]. In [10], Ojeda and Tacconi proposed a method, commonly known as OT method, to obtain low peak-to-average power ratio (PAPR) Huffman sequences by selecting the roots of the polynomials corresponding to the sequences. However, OT method mostly generates real Huffman sequences. To the best of the authors’ knowledge, the problem of designing Huffman sequences with low PAPR, remains open, till date.

Motivated by the works of Ojeda and Tacconi [10], we present a method to generate Huffman sequences of large lengths, using Huffman sequences of smaller lengths, by exploiting the roots of the polynomials corresponding to the short Huffman sequences. To be more specific, using a Huffman sequence of length \(M+1\), we have designed a Huffman sequence of length \(2M+1\). We have defined roots pair (see Sect. 2) and modified the existing OT method [10] by making it more flexible in terms of distributing the roots in outer and inner circles. The PAPR of sequences generated by our method is significantly low as compared to the existing results.

The rest of the paper is organized as follows. In Sect. 2, we fix some notations, revisit some definitions and analyze the properties of a special class of Huffman sequences. In Sect. 3, we give a method of generating low PAPR Huffman sequence and its corresponding algorithm. In Sect. 4, we verify the effectiveness of the proposed method through numerical experiments.

2.  Preliminaries

We use the following notation throughout the paper:

• \(\mathbf{a}\) denotes sequence.
• \(j\) denotes the imaginary unit (i.e., \(j=\sqrt{-1}\)).
• \((x)^*\) denotes the conjugate of \(x\).
• arg denotes the phase of complex number.
• \(\setminus\) denotes set difference.
• \(\left\lfloor \cdot \right\rfloor\) denotes floor function.
• \(\textbf{a} \circ \textbf{b}\) denotes Hadamard product of vector \(\textbf{a}\) and \(\textbf{b}\).

PAPR is generally used to measure the energy distribution performance of a sequence \(\mathbf{s}=( {s_0}, {s_1}, \cdots , {s_N})\), and is given as follows

\[\begin{equation*} {PAPR}_{\mathbf{s}} = \frac{{(N + 1) \cdot \mathop {\max }\limits_{{s_k} \in \mathbf{s}} {{\left| {{s_k}} \right|}^2}}}{{\sum\limits_{k = 0}^{N} {{{\left| {{s_k}} \right|}^2}} }}. \tag{1} \end{equation*}\]

Let \(\textbf{a} = ({a_0},{a_1}, ... ,{a_{N - 1}},{a_N})\), \(\textbf{b} = ({b_0},{b_1}, ... ,{b_{N - 1}},{b_N})\) be complex sequences of length \(N+1\). The aperiodic correlation function of \(\textbf{a}\) and \(\textbf{b}\) at a shift of \(\tau\) is given by

\[\begin{equation*} {C _{\textbf{a}\textbf{b}}}(\tau ) = \left\{ \begin{gathered} \sum\limits_{i = 0}^{N - \tau } {{a_i}{b_{i + \tau }^*} } ; \quad \quad \tau \geqslant 0, \hfill \\ \sum\limits_{i = 0}^{N + \tau } {{a_{i - \tau }}{b_i^* } } ; \quad \quad \tau < 0. \hfill \\ \end{gathered} \right. \tag{2} \end{equation*}\]

When \(\textbf{a}=\textbf{b}\), \({C_{\textbf{a}\textbf{b}} }(\tau )\) is aperiodic auto-correlation function, otherwise it is aperiodic cross-correlation function of \(\textbf{a}\) and \(\textbf{b}\).

Definition 1 (polynomial of sequence): Let \(N\) be a positive integer and \(\mathbf{a} = ({a_0}, {a_1}, \cdots , {a_N})\). The polynomial of \(\mathbf{a}\) is \(\mathbf{a}(x) = {a_0}{x^N} + {a_1}{x^{N - 1}} + \cdots + {a_{N - 1}}x + {a_N}\). Sequence \(\mathbf{a}\) is called the sequence of polynomial \(\mathbf{a}(x)\).

Lemma 1: ([11]) Let \(\mathbf{c} = ( {c_0}, {c_1}, \cdots , {c_N})\), \(\mathbf c(x)\) is the polynomial of \(\mathbf {c}\) and \(\overline{\mathbf{c}}(x) = c_N^* {x^N} + {c_{N - 1}^*} {x^{N - 1}} + \cdots + {c_1^*} x + {c_0^*}\). The coefficients of \(\mathbf{c}(x) \cdot \overline{\mathbf{c}}(x)\) are the values of the auto-correlation function \(C _{\mathbf{c}\mathbf{c}}(\tau )\) at shifts \(\tau\).

Let \(\mathbf{s}\) be a Huffman sequence [7] of length \(N+1\), then the auto-correlation values of \(\mathbf{s}\) are \(0\) except for the shifts of zero and \(\pm N\), i.e.,

\[\begin{equation*} {C _{\textbf{s}\textbf{s}}}(\tau ) = \begin{cases} {E};\quad &\tau = 0, \\ \epsilon;\quad &\tau = \pm N , \\ 0;\quad &else. \\ \end{cases} \tag{3} \end{equation*}\]

Here \(E\) is energy of \(\mathbf{s}\). We call it a quasi-Huffman squence if the auto-correlation of \(\mathbf{s}\) have a non-zero value \(\delta\) at \(\tau=\pm N/2\), i.e.,

\[{C _{\textbf{s}\textbf{s}}}(\tau ) = \begin{cases} {E};\quad &\tau = 0, \\ \delta; &\tau=\pm N/2,\\ \epsilon;\quad &\tau = \pm N , \\ 0;\quad &else. \\ \end{cases}\]

Definition 2 (generation roots set): For \(R>0\), consider \(2N\) points \(\{ {x_{R, 1}}, \cdots , {x_{R, N}},{x_{{R^{ - 1}}, 1}}, \cdots {x_{{R^{ - 1}}, N}}\}\) in concentric circles of radius \(R\) and \(R^{-1}\) respectively on the complex plane, where \(\textbf{arg} ({x_{R, k}}) = \textbf{arg} ({x_{{R^{ - 1}}, k}}) = 2\pi k/N\), then \(\textbf{r}_k=\{ {x_{R, k}}, {x_{{R^{ - 1}}, k}}\} = \{ R \cdot {e^{\frac{{j2\pi k}}{N}}}, {R^{ - 1}} \cdot {e^{\frac{{j2\pi k}}{N}}}\}, k = 1, 2, \cdots , N\) is called the \(k\)-th generation roots set.

Example 1: Let \(R=1.25, k=1, N=6\), then \(\textbf{r}_1 =\{ 1.25 \cdot {e^{\frac{{j2\pi }}{6}}}, 0.8 \cdot {e^{\frac{{j2\pi }}{6}}}\}\) (without loss of generality, we assume that \(R > {R^{ - 1}}\)).

Based on Definition 2, Lemma 2 below gives a general method to construct Huffman sequences.

Lemma 2: ([7]) Let us select one element \({x_{\tilde R, k}} (\tilde R = R\) or \({R^{ - 1}}, k=1,2,\cdots , N)\) from each generation roots set \(\textbf{r}_k\), and compute a degree \(N\) polynomial \(\mathbf{s}(x) = {s_0}{x^N} + {s_1}{x^{N - 1}} + \cdots + {s_{N - 1}}x + {s_N}\) by these \({x_{\tilde R, k}}\). The sequence \(\mathbf{s}\), corresponding to \(\mathbf{s}(x)\) is a Huffman sequence of length \(N+1\).

Proof: After selecting from generation roots sets, let us consider a set \(\Omega\), consisting of \(N\) points, as follows:

\[\begin{equation*} \begin{aligned} \Omega &= \{ {x_{\tilde R, 1}}, {x_{\tilde R, 2}}, \cdots , {x_{\tilde R, N}}\}\\ &= \{ {R_1}{e^{\frac{{j2\pi }}{N}}}, {R_2}{e^{\frac{{j2 \cdot 2\pi }}{N}}}, \cdots , {R_N}{e^{\frac{{jN \cdot 2\pi }}{N}}}\}, \end{aligned} \tag{4} \end{equation*}\]

where \({R_k} \in \{ R, {R^{ - 1}}\}\) is the radius of the \(k\)-th element of \(\Omega\). Taking the elements of \(\Omega\) as roots, we can construct a polynomial \(\mathbf{s}(x)= {s_0}{x^N} + {s_1}{x^{N - 1}} + \cdots + {s_{N - 1}}x + {s_N}\). The sequence of \(\mathbf{s}(x)\) is \(\mathbf{s} =( {s_0}, {s_1}, \cdots , {s_N})\). Let \(\hat \Omega = {\bigcup\limits_{k = 1}^N {{\textbf{r}_k}} } \setminus \Omega\), then \(\hat \Omega\) can be written as

\[\begin{gathered} \begin{aligned} \hat \Omega &= \{ R_1^{ - 1}{e^{\frac{{j2\pi }}{N}}}, R_2^{ - 1}{e^{\frac{{j2 \cdot 2\pi }}{N}}}, \cdots , R_N^{ - 1}{e^{\frac{{jN \cdot 2\pi }}{N}}}\} \\ &= \{ {(x_{\tilde R, 1}^*)^{ - 1}}, {(x_{\tilde R, 2}^*)^{ - 1}}, \cdots , {(x_{\tilde R,N }^*)^{ - 1}}\}. \\ \end{aligned} \end{gathered}\]

Using the elements of \(\hat \Omega\), we can compute a polynomial \(\overline{\mathbf{s}}(x) = s_N^*{x^N} + s_{N - 1}^*{x^{N - 1}} + \cdots + s_1^*x + s_0^*\), after that, we will have

\[\begin{aligned} &{\mathbf{s}}(x)\overline{\mathbf{s}}(x)\\ =& ({s_0}{x^N} + \cdots + {s_N})(s_N^*{x^N} + \cdots + s_0^*)\\ =& {s_0}(x - {R_1}{e^{\frac{{j2\pi }}{N}}})(x - {R_2}{e^{\frac{{j2 \cdot 2\pi }}{N}}}) \cdots (x - {R_N}{e^{\frac{{jN \cdot 2\pi }}{N}}})\\ \;& \cdot s_N^*(x - R_1^{ - 1}{e^{\frac{{j2\pi }}{N}}})(x - R_2^{ - 1}{e^{\frac{{j2 \cdot 2\pi }}{N}}}) \cdots (x - R_N^{ - 1}{e^{\frac{{jN \cdot 2\pi }}{N}}}) \nonumber\\ =&{s_0}s_N^*{x^{2N}} - {s_0}s_N^*(R^N + {R^{ - N}}){x^N} + {s_0}s_N^*. \end{aligned}\]

By Lemma 1, the aperiodic auto-correlation function of \(\mathbf{s}\) is

\[{{ \mathcal{C}}_{{\mathbf{s}}{\mathbf{s}}}}(\tau ) = \begin{cases} {- {s_0}s_N^*(R^N + {R^{ - N}})}; &\tau = 0, \\ {s_0}s_N^*; &\tau = -N, N , \\ 0; &else. \blacksquare \\ \end{cases}\]

Since \(- {s_0}s_N^*(R^N + {R^{ - N}})\) is the total energy of \(\mathbf{s}\), \(R\) is a positive number, \({s_0}s_N^*\) here must be a negative real number.

In the following let us revisit the OT method [10] along with some relevant definitions.

Definition 3 (roots pair) For an even \(N\), partitioning the set \(\Omega\) mentioned in \((4)\) into \(\frac{N}{2}\) subsets, each subset \(\tilde \Omega\) can be written as

\[\begin{equation*} {\tilde \Omega _n} = \{ {R_n}{e^{\frac{{jn \cdot 2\pi }}{N}}}, {R_{n + \frac{N}{2}}}{e^{\frac{{j(n + \frac{N}{2}) \cdot 2\pi }}{N}}}\}, \tag{5} \end{equation*}\]

where \(n=1, 2, \cdots, \frac{N}{2}\). Then \({\tilde \Omega _n}\) is called the \(n\)-th roots pair of Huffman sequence \(\mathbf{s}\).

It is clear that \(\bigcup\limits_{n = 1}^{N/2} {{{\tilde \Omega }_n}} = \Omega\).

For OT method, \(N\) better be an even integer which can not be divided by 4, and there are half of the elements in \(\Omega\) come from circles of radius \(R\) and \(R^{-1}\) respectively. Specifically, here \(\Omega_{OT}\) should be

\[\begin{align*} & {\Omega _{OT}} = \left\{ {R \cdot {e^{\frac{{j(N - \left\lfloor {\frac{N}{4}} \right\rfloor ) \cdot 2\pi }}{N}}}, \cdots ,R \cdot {e^{\frac{{j(N - 1) \cdot 2\pi }}{N}}},R \cdot {e^{\frac{{jN \cdot 2\pi }}{N}}},R \cdot {e^{\frac{{j2\pi }}{N}}}, \cdots ,R \cdot {e^{\frac{{j(\left\lfloor {\frac{N}{4}} \right\rfloor ) \cdot 2\pi }}{N}}}} \right\} \hfill \\ & \cup \left\{ {{R^{ - 1}} \cdot {e^{\frac{{j(\left\lfloor {\frac{N}{4}} \right\rfloor + 1) \cdot 2\pi }}{N}}},{R^{ - 1}} \cdot {e^{\frac{{j(\left\lfloor {\frac{N}{4}} \right\rfloor + 2) \cdot 2\pi }}{N}}}, \cdots ,{R^{ - 1}} \cdot {e^{\frac{{j(N - \left\lfloor {\frac{N}{4}} \right\rfloor - 1) \cdot 2\pi }}{N}}}} \right\}. \hfill \\ \tag{6} \end{align*}\]

Let a Huffman sequence generated by OT method based on \((6)\) be \(\tilde{\mathbf{ s}} = ({\tilde s_0}, {\tilde s_1}, \cdots , {\tilde s_N})\), where \(N\) is an even integer that can not be divided by 4. The polynomial of \(\tilde{\mathbf{ s}}\) is

\[\begin{equation*} \tilde{\mathbf{ s}}(x) = {\tilde s_0}{x^N} + {\tilde s_1}{x^{N - 1}} + \cdots + {\tilde s_{N - 1}}x + {\tilde s_N}. \tag{7} \end{equation*}\]

Then the \(n\)-th roots pair of \(\tilde{\mathbf{ s}}\) will be

\[\begin{equation*} \begin{aligned} &\tilde \Omega _n^{OT} \\ &= \left\{ \begin{array} \{\{ R \cdot {e^{\frac{{jn \cdot 2\pi }}{N}}}, {R^{ - 1}} \cdot {e^{\frac{{j(n + \frac{N}{2}) \cdot 2\pi }}{N}}}\} ; \quad n = 1, \cdots ,\left\lfloor {\frac{N}{4}} \right\rfloor, \hfill \\ \{ {R^{ - 1}} \cdot {e^{\frac{{jn \cdot 2\pi }}{N}}}, R \cdot {e^{\frac{{j(n + \frac{N}{2}) \cdot 2\pi }}{N}}}\} ; \quad n = \left\lfloor {\frac{N}{4}} \right\rfloor + 1, \cdots ,\frac{N}{2} \hfill . \nonumber\\ \end{array} \right. \end{aligned} \end{equation*}\]

To make this more intuitive, an example of \(\Omega_{OT}\) (roots of \((7)\)) and \(\tilde \Omega _1^{OT}\) of a Huffman sequence generated by OT method is given here when \(N=18\), \(R=1.25\). \(C_1\) and \(C_2\) are concentric circles on complex plane with radius \(R\) and \(R^{-1}\).

Fig. 1  Roots distribution when \(N=18\) (OT method).

In this case, \(\tilde{\mathbf{ s}}\) is a real sequence. The sequence \(\tilde{\mathbf{ s}}\) obtained by OT method still has an another interesting property which is useful later on. We rearrange the elements in \(\Omega_{OT}\) in order of phase value

\[\begin{equation*} \begin{gathered} \begin{aligned} {\Omega _{OT}} =& \{ {R_1} {e^{j{\varphi _1}}}, {R_2} {e^{j{\varphi _2}}}, \cdots , {R_N} {e^{j{\varphi _N}}}\} \\ =& \{ {\rho _1}, {\rho _2}, \cdots , {\rho _N}\}, \end{aligned} \end{gathered} \tag{8} \end{equation*}\]

where \(R_k, {\varphi _k} = \frac{2\pi k}{N},\,k = 1,2, \cdots ,N\) stand for the radius (\(R\) or \(R^{-1}\)) and phase of the \(k\)-th element of rearranged \(\Omega_{OT}\). Let us divide \((8)\) into 2 subsets, the first is \({\mu_1} = \{ {\rho_1}, {\rho_3}, \cdots \, {\rho_{N-1}}\}\) (all with odd subscripts) and the second is \({\mu_2} = \{ {\rho_2}, {\rho_4}, \cdots ,{\rho_N}\}\) (all with even subscripts). The polynomials corresponding to \(\mu_1\) and \(\mu_2\) are

\[\begin{eqnarray*} &&\!\!\!\!\! {\mathbf{a}}(x) = {a_0}{x^{\frac{N}{2}}} + {a_1}{x^{\frac{N}{2} - 1}} + \cdots + {a_{^{\frac{N}{2} - 1}}}x + {a_{\frac{N}{2}}}, \tag{9} \\ &&\!\!\!\!\! {\mathbf{b}}(x) = {b_0}{x^{\frac{N}{2}}} + {b_1}{x^{\frac{N}{2} - 1}} + \cdots + {b_{^{\frac{N}{2} - 1}}}x + {b_{\frac{N}{2}}}. \tag{10} \end{eqnarray*}\]

The sequences of \({\mathbf{a}}(x)\) and \({\mathbf{b}}(x)\) are \({\mathbf{a}} = ({a_0}, {a_1}, \cdots , {a_{\frac{N}{2}}})\) and \({\mathbf{b}} = ({b_0}, {b_1}, \cdots , {b_{\frac{N}{2}}})\).

Let \({\mu _3} = \{ {(\rho _2^*)^{ - 1}}, {(\rho _4^*)^{ - 1}}, \cdots , {(\rho _N^*)^{ - 1}}\}\), the polynomial corresponding to \(\mu_3\) is

\[\begin{equation*} {\mathbf{\overline{b}}(x) = b_{\frac{N}{2}}^*{x^{\frac{N}{2}}} + b_{\frac{N}{2} - 1}^*{x^{\frac{N}{2} - 1}} + \cdots + b_1^*x + b_0^*}, \tag{11} \end{equation*}\]

the sequence of \({\mathbf{\overline{b}}}(x)\) is \((b_{\frac{N}{2}}^*, b_{\frac{N}{2} - 1}^*, \cdots , b_0^*)\).

These polynomials will satisfy \(\tilde{\mathbf{ s}}(x) = {\mathbf{a}}(x){\mathbf{b}}(x)\). Note that \({\mathbf{{a}}}\), \({\mathbf{{b}}}\), \({\mathbf{\overline{b}}}\) are still Huffman sequences. These three sequences have an important relationship, as stated in Theorem 1. The proof is not given here due to space limitations. By multiplicating the polynomials corresponding two length \(M+1\) sequences, we construct a long sequence of length \(2M+1=N+1\), here \(M=N/2\).

Theorem 1: Let \({\mathbf{\overline{b}}}\) be as defined above. Then the element \({{b_{\frac{N}{2} - i}^*}}\) of \({\mathbf{\overline{b}}}\) is a constant multiple of \(\left[ {{{( - 1)}^i}{a_i}} \right]\). That is

\[\begin{equation*} \frac{{b_{\frac{N}{2} - i}^*}}{{{{( - 1)}^i}{a_i}}} = \alpha , \quad i = 0, 1, 2, \cdots ,\frac{N}{2}. \tag{12} \end{equation*}\]

Through analysis, it can be shown that the sequence \(\tilde{\mathbf{ s}}\) obtained by OT method can be constructed only by one of the two short sequences it divides into, i.e. \(( {a_0}, {a_1}, \cdots , {a_{\frac{N}{2} - 1}}, {a_{\frac{N}{2}}})\). Because \(\mathbf{a}, \mathbf{b}\) have an equivalent property given in \((12)\) after finite transformations.

3.  A Method to Find Low PAPR Huffman Sequences

In fact for any Huffman sequence whose polynomial has \(N\) (\(N\) is even and can not be divided by 4) roots, it can be found that if the radius \({R_n}, {R_{n + \frac{N}{2}}}\) in each roots pair \({\tilde \Omega _n}\) are reciprocals of each other, such sequence will satisfiy the property \((12)\) and can also be constructed by short sequences it divides into, just like we analyzed in last section. Reversing this process, we present a method for generating Huffman sequences with excellent performance in this section.

In Fig. 2 we have depicted the difference of the proposed method with the OT method, with an example. Let us have three roots pairs \((l_1,o_1)\), \((l_2,o_2)\) and \((l_3,o_3)\). In OT method, \(l_1\), \(l_2\), and \(l_3\), should always be placed on the right side of the outer circle, and \(o_1\), \(o_2\), and \(o_3\) should be placed \(180^\circ\) opposite to \(l_1\), \(l_2\), and \(l_3\), respectively, in the left side of the inner circle. However, we have removed the restriction of OT method in the proposed method. In the proposed method, \(l_1\), \(l_2\), and \(l_3\) can be placed in either side of the outer or inner circle. If \(l_i\) is placed in the outer circle, corresponding \(o_i\) should be placed \(180^\circ\) opposite \(l_i\) in the inner circle. If \(l_i\) is placed in the inner circle, corresponding \(o_i\) should be placed \(180^\circ\) opposite \(l_i\) in the outer circle.

Fig. 2  Roots distribution of OT method (left) vs proposed method (right).

Construction 1: Let \(M\) be an integer, and for a given \(R\), let

\[\begin{equation*} ({\xi _0}, {\xi _1}, \cdots , {\xi _{M-1}}, {\xi _M}), \tag{13} \end{equation*}\]

be an arbitrary Huffman sequence obtained through Lemma 2.

By calculating

\[(1, - 1, \cdots, (- 1)^{M-1}, (- 1)^M) \circ ({\xi _0}, {\xi _1}, \cdots , {\xi _M}),\]

and after few transformations, we will have

\[\begin{equation*} \left\{ {{{( - 1)}^{M - i}}\xi _{M - i}^*} \right\},i = 0,1, \cdots ,M. \tag{14} \end{equation*}\]

The polynomials corresponding to \((13)\) and \((14)\) are

\[\begin{equation*} \begin{aligned} {f_1}(x) &= {\xi_0}{x^M} + {\xi_1}{x^{M - 1}} + \cdots + {\xi_{M - 1}}x + {\xi_M},\\ {f_2}(x) &= (-1)^M {\xi_M^*} {x^M} + (-1)^{M-1}{\xi_{M-1}^*} {x^{M - 1}} + \cdots + {\xi_0^*}. \end{aligned} \tag{15} \end{equation*}\]

\((14)\) is still a Huffman sequences which can be verified by Lemma 1. Let the roots sets of \({f_1}(x)\) and \({f_2}(x)\) be \({\Omega _{{f_1}}}\) and \({\Omega _{{f_2}}}\), respectively. A polynomial \({\bf U}(x)\) of degree \(2M\) can be computed by the roots in the large roots set

\[\begin{aligned} {\Omega _{{f_1}, {f_2}}} = {\Omega _{{f_1}}} + {\Omega _{{f_2}}} = \{ {R_1}{e^{\frac{{j2\pi }}{M}}},\,{R_2}{e^{\frac{{j2 \cdot 2\pi }}{M}}}, \cdots ,{R_M}{e^{\frac{{jM \cdot 2\pi }}{M}}},\\ - R_1^{ - 1}{e^{\frac{{j2\pi }}{M}}}, - R_2^{ - 1}{e^{\frac{{j2 \cdot 2\pi }}{M}}}, \cdots , - R_1^{ - 1}{e^{\frac{{jM \cdot 2\pi }}{M}}}\}, \end{aligned}\]

the sequence corresponding to \({\bf U}(x)\) is

\[\begin{equation*} \mathbf{U} = (u_0, u_1, \cdots, u_M, u_{M+1},\cdots, u_{2M-1}, u_{2M}). \tag{16} \end{equation*}\]

Theorem 2: Let \(M\) be an odd integer, and \(\mathbf{U}\) be a sequence, constructed according to Construction 1. Then \(\bf U\) is a Huffman seqeuence of length \(2M+1\).

Proof: When \(M\) is odd, the step before \((14)\) is

\[\begin{equation*} (1, - 1, \cdots , 1, - 1) \circ ({\xi _0}, {\xi _1}, \cdots , {\xi _{M-1}}, {\xi _{M}}), \tag{17} \end{equation*}\]

the roots set of \({\bf U}(x)\) is \(\Omega _{{f_1}, {f_2}}\), let \(\bar{\mathbf{U}}(x) = u_{2M}^*{x^{2M}} + \cdots + u_1^*x + u_0^*\), similar to lemma 2, it can be verified that

\[\begin{split} & \mathbf{U}(x) \cdot \bar{\mathbf{U}}(x)\\ &= \varsigma ({x^{2M}} - {R^{2M}})({x^{2M}} - {R^{ - 2M}})\\ &= \varsigma {x^{4M}} - \varsigma ({R^{2M}} + {R^{ - 2M}}){x^{2M}} + \varsigma , \end{split}\]

where \({u_0}u_{2M}^* = \varsigma\). Hence, According to Lemma 1, \(\bf {U}\) is a Huffman sequence. \(\blacksquare\)

Theorem 3: Let \(M\) be an even integer, and \(\mathbf{V}\) be a sequence, constructed according to Construction 1. Then \(\mathbf{V}\) is a quasi-Huffman sequence of length \(2M+1\).

Proof: When \(M\) is even, the step before \((14)\) is

\[\begin{equation*} (1, - 1, \cdots , 1, - 1, 1) \circ ({\xi _0}, {\xi _1}, \cdots , {\xi _{M-1}}, {\xi _{M}}), \tag{18} \end{equation*}\]

following the above method we will have

\[\begin{equation*} \mathbf{V} = (v_0, v_1, \cdots, v_M, v_{M+1},\cdots, v_{2M-1}, v_{2M}), \tag{19} \end{equation*}\]

let \(\mathbf{V}(x)\) be the polynomial corresponding to the sequence \(\mathbf{V}\). The roots set of \({\bf V}(x)\) is \(\Omega _{{f_1}, {f_2}}\), let \(\bar{\mathbf{V}}(x) = v_{2M}^*{x^{2M}} + \cdots + v_1^*x + v_0^*\), then it can be verified that

\[\begin{equation*} \begin{split} & \mathbf{V}(x) \cdot \bar{\mathbf{V}}(x)\\ &= {\left( {({x^M} - {R^M})({x^M} - {R^{ - M}})} \right)^2}\\ &= \lambda {x^{4M}} - 2\lambda ({R^M} + {R^{ - M}}){x^{3M}}\\ &+ \lambda \left[ {{{({R^M} + {R^{ - M}})}^2} + 2} \right]{x^{2M}} - 2\lambda ({R^M} + {R^{ - M}}){x^M} + \lambda , \end{split} \tag{20} \end{equation*}\]

where \({v_0}v_{2M}^* = \lambda\).

According to Lemma 1, the coefficient \(\lambda\) represents aperiodic autocorrelation value at \(\tau=\pm 2M\), the coefficient \(- 2\lambda ({R^M} + {R^{ - M}})\) represents additional sidelobe value, and the sidelobe will appear at \(\tau=\pm M\), the coefficient \(\lambda \left[ {{{({R^M} + {R^{ - M}})}^2} + 2} \right]\) represents mainlobe value, i.e., the magnitude at \(\tau=0\), the energy of sequence \(\mathbf{V}\). Hence, \(\mathbf{V}\) displays a zero-correlation zone width of \(M-1\). \(\blacksquare\)

Although these sequences have additional sidelobes, the sidelobes are far from the mainlobe. Therefore, such low PAPR sequences still have application value in scenarios such as CDMA [12].

Figure 3 and Fig. 4 show the root distribution of \({\Omega _{{f_1}, {f_2}}}\), when \((13)\) is an arbitrary Huffman sequence of \(R = 1.25\), \(M = 19\) and \(18\). \(C_1\) and \(C_2\) are same as above. Figure 5 and Fig. 6 show the auto-correlation function of \(\bf U\) and \(\bf V\).

Fig. 3  Roots distribution when \(M=19\).

Fig. 4  Roots distribution when \(M=18\).

Fig. 5  Auto-correlation of sequence \(\mathbf{U}\) when \(M=19\).

Fig. 6  Auto-correlation of sequence \(\mathbf{V}\) when \(M=18\).

Both \(\bf U\) and \(\bf V\) have a property of approximate symmetry about the central element. The low PAPR sequence design algorithm when \(M\) is odd is summarized in Algorithm 1. Since the work of this paper is based on OT method, it can also be seen as improved OT method.

Note that when \(M\) is even, based on \((14)\), \((15)\) and \((18)\), \(f_2(x)\) in step 3 will become

\[\begin{equation*} \begin{aligned} {f_2}(x) &= {\xi_M^*} {x^M} - {\xi_{M-1}^*} {x^{M - 1}} + \cdots - {\xi_1^*} x + {\xi_0^*}, \end{aligned} \tag{21} \end{equation*}\]

and we can construct \(\bf V\) as shown in \((19)\).

4.  Numerical Simulations

Consider \(t\) random Huffman sequences, and \(t\) sequences of length \(2M+1\) constructed using Algorithm 1. Here “random” refers to the random selection of elements in each generation roots set \(\textbf{r}_k\) when the Huffman sequence is generated according to Lemma 2, during this process, we use a total of \(t\) different random binary arrays of specific length to make random selections, and generate a total of \(t\) different Huffman sequences. It can be seen from the analysis in the previous section that \(t\) number of long sequences constructed using Algorithm 1 are also generated by their corresponding \(t\) number of short sequences. When selecting short sequences, the above “random” rules are also followed to ensure that \(t\) number of long sequences are not the same. Let \(t=1000\), \(R=1.25\). According to [13], \(R\) is usually between \(1\) and \(2\). Although it has not been proven yet, \(R=1.25\) makes PAPR as low as possible for most sequences. We show the optimal PAPR in \(1000\) random Huffman sequences with different \(R\) and different lengths in Table 1. Besides, we also compare them with same length OT sequences and Huffman sequences in [14], which we called TS sequences. The length of TS sequences are limited to \(p+1\) (\(p\) is prime and \(p \equiv 1\bmod 4\)). The minimum PAPR of five different schemes in \(t\) experiments are compared under different \(M\) in Fig. 7.

Table 1  PAPR comparison under different \(R\) and lengths.

Fig. 7  PAPR comparison under different \(M\).

Figure 7 shows that, the real sequences generated by Algorithm 1 perform better than those generated by OT method at almost all lengths, meanwhile, complex sequences generated by Algorithm 1 have lower PAPR than random complex Huffman sequences, same length OT sequences and most TS sequences. Besides, because the length of TS sequence is limited to a part of prime numbers, it is not as flexible as the proposed sequence in length selection.

We also made a comparison with the method proposed by Shao and Tanada [15]. Experiments show that the maximum length of the real sequences with PAPR less than 6dB proposed in [15] is \(33\), and the PAPR of real sequences proposed in this paper is still less than 6dB when the length is \(71\) under the same parameters. This shows that the sequences proposed in our paper have better performance.

Table 2 and Table 3 show some specific cases of odd and even \(M\). \(Min_1\), \(Min_2\), \(Min_3\) denote the lowest PAPR of real and complex sequences generated by Algorithm 1, the lowest PAPR of random sequences in \(t\) experiments. \(H\) denotes the “OT sequence” PAPR, which are all measured in dB.

Table 2  Performance comparison under odd \(M\).

Table 3  Performance comparison under even \(M\).

Next we consider same \(M\), \(R\) and \(t\) for \(t\) experiments. To show the overall performance, the cumulative distribution function (CDF) diagrams of PAPR are plotted in Figs. 8-13 for four different schemes. \({CDF_A}\), \({CDF_B}\), \({CDF_C}\) and \({CDF_D}\) denote PAPR distribution of complex, real sequences obtained by Algorithm 1, OT method, and random Huffman sequences.

Fig. 8  CDF comparison when \(M=15\).

Fig. 9  CDF comparison when \(M=23\).

Fig. 10  CDF comparison when \(M=27\).

Fig. 11  CDF comparison when \(M=14\).

Fig. 12  CDF comparison when \(M=22\).

Fig. 13  CDF comparison when \(M=26\).

It can be seen from the above results that, overall, most complex Huffman sequences generated by Algorithm 1 also have lower PAPR than those generated by OT method and random Huffman sequences.

In addition, some real Huffman sequences with quite good PAPR performance can also be generated by Algorithm 1.

Note that the optimal selection of parameter \(R\) has not yet been studied, which may be an interesting problem.

5.  Conclusion

In this paper, we have analyzed the mathematical properties of Huffman sequences and proposed a method to generate Huffman sequences and quasi-Huffman sequences of larger lengths with low PAPR properties using Huffman sequences of shorter lengths. As future work, it might be interesting to apply the proposed low PAPR Huffman sequences in various communication applications.

Acknowledgments

The authors are very grateful to the editor and the anonymous reviewers for their valuable comments and suggestions that improved the quality of this paper. This work was supported in part by the National Natural Science Foundation of China (NSFC) under Grants 12001450 and 12371524, in part by the Sichuan Provincial Fund for Distinguished Young Scholars under Grant 2023NSFSC1912, in part by Natural Science Foundation of Sichuan Under Grants 2022NSFSC0906, in part by projects of central government to guide local scientific and technological development under Grant 2022ZYD0004, and also in part by the Fundamental Research Funds for the Central Universities of China under Grants 2682023GF013 and 2682023CG007.

References

[1] N. Suehiro, “A signal design without co-channel interference for approximately synchronized CDMA systems,” IEEE J. Sel. Areas Commun., vol.12, no.5, pp.837-841, June 1994. doi: 10.1109/49.298057.

[2] L. Zegov, R. Pribić, and G. Leus, “Optimal waveforms for compressive sensing radar,” 21st European Signal Processing Conference (EUSIPCO 2013), Marrakech, Morocco, pp.1-5, 2013.

[3] S. Gupta, M. Zapf, H. Krauß, and N.V. Ruiter, “Design of Huffman sequences with limited bandwidth,” 2014 IEEE International Ultrasonics Symposium, Chicago, IL, USA, pp.1089-1092, 2014. doi:10.1109/ULTSYM.2014.0267.

[4] P. Walk, P. Jung, and B. Hassibi, “Short-message communication and FIR system identification using Huffman sequences,” 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, pp.968-972, 2017. doi:10.1109/ISIT.2017.8006672.

[5] P. Fan and L. Hao, “Generalized orthogonal sequences and their applications in synchronous CDMA systems,” IEICE Trans. Fundamentals, vol.E89-A, no.11, pp.2054-2066, Nov. 2000.

[6] D.J. White, J.N. Hunt, and L.A.G. Dresel, “Uniform Huffman sequences do not exist,” Bull. London Mathe. Soc., vol.9, no.2, pp.193-198, July 1977.

[7] D. Huffman, “The generation of impulse-equivalent pulse trains,” IRE Trans. Inf. Theory, vol.8, no.5, pp.10-16, Sept. 1962. doi: 10.1109/TIT.1962.1057778.

[8] M.H. Ackroyd, “Synthesis of efficient Huffman sequences,” IEEE Trans. Aerosp. Electron. Syst., vol.AES-8, no.1, pp.2-8, Jan. 1972. doi: 10.1109/TAES.1972.309459.

[9] M. Schroeder, “Synthesis of low-peak-factor signals and binary sequences with low autocorrelation,” IEEE Trans. Inf. Theory, vol.16, no.1, pp.85-89, Jan. 1970. doi: 10.1109/TIT.1970.1054411.

[10] R. Ojeda and E.J. Tacconi, “Huffman sequences with uniform time energy distribution,” Signal Processing, vol.37, no.1, pp.141-146, May. 1994.

[11] M. Ackroyd, “Huffman sequences with approximately uniform envelopes or cross-correlation functions,” IEEE Trans. Inf. Theory, vol.23, no.5, pp.620-623, Sept. 1977. doi: 10.1109/TIT.1977.1055761.

[12] Z. Zhou, D. Zhang, T. Helleseth, and J. Wen, “A construction of multiple optimal ZCZ sequence sets with good cross correlation,” IEEE Trans. Inf. Theory, vol.64, no.2, pp.1340-1346, Feb. 2018. doi:10.1109/TIT.2017.2756845.

[13] K. Anand, Y.L. Guan, X. Liu, Z. Liu, Y. Yang, Z. Zhou, P. Fan, and E. Gunawan, “Pilot design for BEM-based channel estimation in doubly selective channel,” IEEE Trans. Veh. Technol., vol.69, no.2, pp.1679-1694, Feb. 2020. doi: 10.1109/TVT.2019.2958976.

[14] Y. Tanada and K. Sato, “Long Huffman sequences derived from even functional quadratic residues,” The Sixth International Workshop on Signal Design and Its Applications in Communications, Tokyo, Japan, pp.56-59, 2013. doi: 10.1109/IWSDA.2013.6849061.

[15] P. Shao and Y. Tanada, “Real-valued self-orthogonal finite-length sequences with maximum absolute value less than 2,” 2006 8th International Conference Advanced Communication Technology, Phoenix Park, Korea (South), pp.5-387, 2006. doi: 10.1109/ICACT.2006.205991.

Authors

Wenjian WANG
  Southwest Jiaotong University

Zhi GU
  Southwest Jiaotong University

Avik Ranjan ADHIKARY
  Southwest Jiaotong University

Rong LUO
  Southwest Jiaotong University

Keyword

auto-correlation,  Huffman sequence,  peak-to-average power ratio (PAPR)