Phase encoding with Gold codes for wave-equation migration

Gold codes

Before describing Gold codes it is useful to define maximum length sequences.

Linear feedback shift registers (LFSR) (Moon and Stirling, 2000) are called state machines, whose components and functions are:

• the shift register - shifts the bit pattern and registers the output bit; and
• the feedback function - computes the input bit according to the tap sequence and inserts the computed bit into the input bit position.

The output sequence of bits form pseudo-random binary sequences, which are completely controlled by the tap sequence. A tap sequence defines which bits in the current state will be combined to determine the input bit for the next state. The combination is generally performed using module-2 addition ( $\it exclusive or$ - XOR). This means that adding the selected bit values defined by the tap sequence, if the sum is odd the output of the function is one; otherwise the output is zero. Table 1 shows the internal states and the output sequence of a 4-bit LFSR with tap sequence $[4,1]$. For the current state, the input bit (bit 1) is computed by the sum module-2 of the bits defined by the tap sequence(bits 1 and 4). The rest of the bits in the register (bits 2, 3 and 4) are obtained by shifting the bit values in the previous state to the right. For example, bit 2 of the current state is bit 1 of the previous state. The output bit of the current state is the last bit (bit 4) in the register from the previous state.

Table 1: Internal states and the output sequence of a 4-bit LFSR with tap sequence [4,1].

Register States
bit1	bit2	bit3	bit4	Output
(Tap)			(Tap)	Sequence
1	1	0	1
0	1	1	0	1
0	0	1	1	0
1	0	0	1	1
0	1	0	0	1
0	0	1	0	0
0	0	0	1	0
1	0	0	0	1
1	1	0	0	0
1	1	1	0	0
1	1	1	1	0
0	1	1	1	1
1	0	1	1	1
0	1	0	1	1
1	0	1	0	1
1	1	0	1	0

In number theory, Galois fields (${\bf GF}$) are finite fields in which all operations result in an element of the field (Lidl and Niederreiter, 1994). Addition, subtraction and multiplication of polynomials are defined in a finite field. Module 2 arithmetic forms the basis of ${\bf GF}(2)$ (Galois field of order 2). Addition and multiplication operations in GF(2) can be represented by bitwise operators XOR and AND, respectively. Table 2 synthesizes the possible output values of addition and multiplication over ${\bf GF}(2)$.

Table 2: ${\bf GF}(2)$ addition and multiplication possible outcomes.

+	0	1		$\times$	0	1
0	0	1		0	0	0
1	1	0		1	0	1

If a polynomial can not be represented as the product of two or more polynomials, it is called an irreducible polynomial. For instance, $x^2+x+1$ is irreducible over ${\bf GF}(2)$ because it can not be factored. However, $x^2+1$ is not irreducible over ${\bf GF}(2)$ because, using normal algebra, $(x+1)(x+1)=x^2+2x+1$, and after reduction module-2, is $x^2+1$ (the term $2x$ is dropped). So, in ${\bf GF}(2)$, $x^2+1 \equiv x^2+2x+1$.

The importance of studying irreducible polynomials ${\bf GF}(2)$ is that they are used to represent tap sequences. Considering an irreducible polynomial, the corresponding tap sequence is given by the exponents of the terms with coefficients of 1 (Dinan and Jabbari, 1998). Special tap sequences can be used to generate particular pseudo-random binary sequences. They are called maximum length sequences (m-sequences) and, by definition, are the largest codes that can be generated by a LFSR for a given tap sequence. Their length is $(b^n-1)$, where $n$ is the number of elements of the tap sequence, and $b=2,3 or 5$.

The autocorrelation function of an m-sequence, $\Phi_{\it mls}(k)$, is given by

$$\Phi_{\it mls}(k) = \left\{ \begin{array}{r} b^n-1 \qquad\hbox{for}\quad k = 0, \cr -1 \qquad\hbox{for}\quad k \neq 0, \end{array} \right.$$ (A-11)

where $k$ is the lag of correlation. In spite of the good autocorrelation properties, m-sequences, in general, are not immune to cross-correlation problems, and they may have large and unpredictable cross-correlation values. However, the so-called preferred pairs of m-sequences have cross-correlation functions which might assume the predicted values, $-1, -1+p$, and $-1-p$, where $p=2^{(n+1)/2}$ for $n$ odd or $p=2^{(n+2)/2}$ for $n$ even. Given a $(2^{n}-1)$-length m-sequence, $a(k)$, and $gcd\{n,4\} = 1$ (greatest common divisor of $n$ and $4$), its preferred pair is the result of decimation computed by applying on $a(k)$ a circular shift of $q$ samples, where $q=2m+1$ and $gcd\{m,n\}=1$. Figure 1 shows the cross-correlation of m-sequences that form a preferred pair computed with $m=5$.

prefpairs
Figure 1. Cross-correlation of a m-sequences that form a preferred pair. $\bf {[ER]}$

The number of possible preferred pairs of m-sequences is limited, when compared to the requirements of practical applications of wireless communication. Preferred pairs of m-sequences, however, are used to generate Gold codes (Dinan and Jabbari, 1998).

In CDMA, Gold codes are used as chipping sequences that allow several callers to use the same frequency, resulting in less interference and better utilization of the available bandwidth. Originally proposed by Gold (1967), Gold codes can be computed by module-2 addition ( $\it exclusive or$) of circularly shifted preferred pairs of m-sequences of length $2^{n}-1$. The autocorrelation function of a Gold code, $\Phi_{\it gc}(k)$, is given by

$$\Phi_{\it gc}(k) = \left\{ \begin{array}{r} \pm 2^{n}-1 \qquad\hbox{for}\quad k = 0, \cr \pm 1 \qquad\hbox{for}\quad k \neq 0. \end{array} \right.$$ (A-12)

More interestingly, the two valued cross-correlation function of Gold sequences, $\Psi_{\it gc}(k)$, is given by

$$\Psi_{\it gc}(k) = \left\{ \begin{array}{r} \pm (2^{n}-1) \qquad\... ... = \lambda, \cr \mp 1 \qquad\hbox{for}\quad k \neq \lambda. \end{array} \right.$$ (A-13)

where the correlation lag $\lambda$ is given by the difference between the number of circular shifts applied to the m-sequence to compute the Gold codes.

Figure 2 illustrates the correlation properties of the Gold codes. The left part shows the autocorrelation of the Gold code generated with one circular shift of the preferred pair of m-sequence. The right part shows the cross-correlation of the Gold code generated with one circular shift of the preferred pair of m-sequence with the Gold code generated with 84 circular shifts. Note that the peak of the cross-correlation occurs at lag 84. For comparison, we show the correlation functions of conventional random codes in Figure 3. The autocorrelation function presents nearly periodic side lobes with additive low-amplitude random variations. The peak-to-side lobe ratio is around 30. The cross-correlation function is pseudo-random, and its amplitudes are of the same order of magnitude as those of the non-zero lags of the autocorrelation function.

gold184
Figure 2. Correlation functions of Gold codes. a) Autocorrelation of Gold code generated with one circular shift of the preferred pair of m-sequence. b) Cross-correlation of the Gold code generated with one circular shift of the preferred pair of m-sequence with that generated with 84 circular shifts. The peak of the cross-correlation occurs at lag -84. $\bf {[ER]}$

rand
Figure 3. Correlation functions of conventional random codes. a) Autocorrelation of the conventional random code. b) A cross-correlation. $\bf {[ER]}$

After computing Gold codes, we use their phase information to encode the modeling experiments.

Phase encoding with Gold codes for wave-equation migration