Iterative detection of pseudo-random sequences
Détection itérative des séquences pseudo-aléatoires
Résumé
Pseudo-random binary sequences are very common in wireless transmission systems and ciphering mechanisms. More specifically, they are used in direct sequence spread spectrum transmission systems like UMTS or GPS, or to construct preamble sequences for synchronization and channel estimation purpose like in LTE. It is always required to synchronize the receiver with the transmitted sequence. The usual way consists in correlating the received signal with a replica of the sequence. If the correlation exceeds a predefined threshold, the synchronization is declared valid.This thesis addresses a different approach: the binary sequence is detected with a forward error correction decoding algorithm. This allows for instance to detect very long sequences.In this thesis, we show that decoding a pseudo-random sequence is a problematic of the kind ‘detect and decode'. The decoder detects the presence of the transmitted sequence and simultaneously estimates its initial state. In conventional detection theory, this corresponds to a GLRT detector that uses a decoder to estimate the unknown parameter which is the transmitted sequence. For pseudo-random sequences, the decoder implements an iterative message-passing algorithm. It uses a parity check matrix to define the decoding graph on which the algorithm applies. Each parity check equation has a weight t, corresponding to the number of variables in the equation.Parity check equations are thus an essential component of the decoder. The decoding procedure is known to be sensitive to the weight t of the parity check equations. For m-sequences, the number of parity check equations is already known. It is given by the number of codewords of weight t of the corresponding Hamming dual code. For Gold sequences, the number of parity check equations of weight t = 3 and 4 has already been evaluated by Kasami. In this thesis we provide an analytical expression for the number of parity check equations of weight t = 5 when the degree of the generator polynomial r is odd. Knowing this number is important because there is no parity check equation of weight t < 5 when r is odd. This enumeration is also used to provide an estimation of the least degree of parity check equations of weight t.We have then addressed the problem of selecting the parity check equations used by the decoder. We observed the probability of false alarm is very sensitive to this selection. It is explained by the presence or absence of absorbing sets which block the convergence of the decoder when it is fed only with noise. These sets are known to be responsible for error floor of LDPC codes. We give a method to identify these sets according to the parity check equations used by the decoder. The probability of false alarm can increase dramatically if these absorbing sets are destroyed. Then we propose an algorithm for selecting these parity check equations. It relies on the minimization of the number of cycles of length 6 and 8. Simulation show that the algorithm allows to improve significantly the probability of false alarm and the average acquisition time.Eventually, we propose 2 algorithms for the detection of the scrambling codes used in the uplink of UMTS-FDD and CDMA2000 systems. They highlights a new vulnerability of DSSS transmission systems. It is now conceivable to detect these transmission if the sequence's generator is known.
Les séquences binaires pseudo-aléatoires sont couramment employées par les systèmes de transmissions numériques ou des mécanismes de chiffrement. On les retrouve en particulier dans les transmissions par étalement de spectre par séquence direct (e.g. 3G ou GPS)) ou pour construire des séquences d'apprentissage pour faciliter la synchronisation ou l'estimation du canal (e.g. LTE). Un point commun à toutes ces applications est la nécessité de se synchroniser avec la séquence émise. La méthode conventionnelle consiste à générer la même séquence au niveau du récepteur et la corréler avec le signal reçu. Si le résultat dépasse un seuil pré-défini, la synchronisation est déclarée acquise. On parle alors de détection par corrélation.Cette thèse aborde une autre voie : la détection des séquences binaires pseudo-aléatoire par des techniques de décodage canal. Ceci permet par exemple de détecter des séquences longues (e.g. de période 242), contrairement aux techniques par corrélation qui sont trop complexes à implémenter. Cela nécessite néanmoins que le récepteur connaisse au préalable le polynôme générateur de la séquence.Nous avons montré que le décodage d'une séquence pseudo-aléatoire est une problématique du type 'détecte et décode'. Le récepteur détecte la présence de la séquence et simultanément estime son état initial. Ceci correspond dans la théorie classique de la détection à un détecteur de type GLRT qui ne connaît pas la séquence émise, mais qui connaît sa méthode de construction. L'algorithme implémente alors un GLRT qui utilise un décodeur pour estimer la séquence reçue. Ce dernier est implémenté avec un algorithme de décodage par passage de messages qui utilise une matrice de parité particulière. Elle est construite avec des équations de parités différentes, chacune ayant un poids de Hamming valant t.Il correspond au nombre de variables participants à l'équation.Les équations de parité sont un constituant indispensable du décodeur. Nous avons donné leur nombre pour les m-séquences et les séquences de Gold. Pour le cas particulier des séquences de Gold, nous avons calculé le nombre d'équations de parité de poids t=5 lorsque le degré du polynôme générateur r est impair. Ce calcul est important car il n'y a pas d'équations de parité de poids t < 5 lorsque r est impair. Le nombre d'équations de parité est aussi utilisé pour estimer le degré minimal des équations d'un poids t donné. Nous avons montré que le modèle de prédiction estime correctement la valeur moyenne du degré minimal de l'ensemble des séquences de Gold. Nous avons néanmoins mis en évidence une grande variabilité du degré minimal des séquences autour de cette valeur moyenne.Nous avons ensuite identifié les ensembles absorbants complets de plus petite taille lorsque le décodeur emploie plusieurs polynômes de parité. Ces ensembles bloquent la convergence du décodeur lorsque celui-ci est alimenté avec du bruit. Ceci évite les fausses alarmes lors du processus de détection. Nous avons montré que des cycles 'transverses' détruisent ces ensembles absorbants, ce qui génère des fausses alarmes. Nous en avons déduit un algorithme qui minimise le nombre de cycles transverses de longueur 6 et 8, ce qui minimise la probabilité de fausse alarme lorsque le poids des équations de parité vaut t=3. Notre algorithme permet de sélectionner les équations de parité qui minimisent la probabilité de fausse alarme et ainsi réduire notablement le temps d'acquisition d'une séquence de Gold.Nous avons enfin proposé deux algorithmes de détection du code d'embrouillage pour les systèmes WCDMA et CDMA2000. Ils exploitent les propriétés des m-séquences constituant les séquences de Gold, ainsi que les mécanismes de décodage par passage de messages. Ces algorithmes montrent les vulnérabilités des transmissions par étalement de spectre.
Origine : Version validée par le jury (STAR)
Loading...