Jiang Yuan 1,2, Shen Pei 2, 2 au nom de Ji Yang, Chen Zhen 3
(1. Laboratoire clé de traitement d'image et la reconnaissance des formes, province de Jiangxi, Nanchang 330063, Chine 2 École d'ingénierie de l'information, Université de Nanchang aéronautique, Nanchang 330063, Chine; 3. Laboratoire clé de contrôle non destructif, Ministère de l'Education, Université de Nanchang aéronautique, Nanchang 330063, Chine)
: L'algorithme de reconstruction de comprimé pour l'algorithme de poursuite correspondant orthogonale (OMP) ne peut pas sélectionner le meilleur problème atomique à chaque itération de l'algorithme OMP pour optimiser la conception afin d'assurer que la marge minimum de courant de signal observé pour chaque itération, et fait OMP un algorithme d'optimisation pour la conception de matériel basé sur FPGA. Dans la décomposition de la matrice de correction en utilisant la partie de Cholesky (la Cholesky) de la méthode de décomposition, pour éviter une opération de racine, pour réduire le calcul du retard, il est facile à mettre en uvre FPGA. Le système utilise le calcul parallèle, les ressources de multiplexage, ce qui réduit l'utilisation des ressources tout en améliorant la vitesse de fonctionnement. Dans l'environnement de développement Quartus II pour une description de la conception au niveau de RTL et de la simulation sur une plate-forme d'émulation FPGA. Les résultats de simulation vérifier l'exactitude de la conception.
: TN911.2 Code du document: ADOI: 10,16157 / j.issn.0258-7998.2015.10.020
: Jiang Yuan, Shen Pei, au nom de Ji Yang, et un autre type d'optimisation de la conception d'algorithmes de matching pursuit orthogonale sur FPGA basée Technologie électronique, 2015,41 (10): 73-76,80.
Anglais format de référence :. Jiang Yuan, Shen Pei, Dai Jiyang, et al Un plan orthogonal d'optimisation de l'algorithme de recherche correspondant basé sur la mise en uvre FPGA .Application Technique électronique, 2015,41 (10): 73-76,80.
acquisition de signal de Legacy et le traitement principalement de Nyquist théorème d'échantillonnage pour obtenir, et le théorème d'échantillonnage de Nyquist exige que la fréquence d'échantillonnage doit être au moins deux fois la plus haute fréquence du spectre du signal analogique, qui fait une acquisition de signal à haute fréquence pour obtenir extrêmement limitée . Avec le développement rapide des technologies de l'information, une forte augmentation de la bande passante du signal, l'industrie dans l'ère des grandes données, de sorte que les capacités de traitement du signal et les exigences matérielles augmentent également, aux données énormes de traitement des défis .
La compression de détection ayant une acquisition de données et de traitement tout en comprimant l'avantage, avec moins de données peuvent être récupérer avec précision le signal d'origine, de sorte que l'objet au théorème d'échantillonnage de Nyquist de la fréquence d'échantillonnage est possible de se libérer, le plus bas la fréquence d'échantillonnage peut être réalisé. théorie de détection comprimé comprend trois aspects: représentation clairsemée de signal, la configuration matrice de mesure, la conception de l'algorithme de reconstruction du signal. étude de conception du signal est l'algorithme de reconstruction Compressed Sensing de la théorie critique et de l'algorithme d'optimisation basée sur l'adéquation algorithme de recherche itération avide. Orthogonal Matching Pursuit opérateur à (Orthogonal Matching Pursuit, OMP) algorithme glouton et sa classe améliorée représente a par rapport à d'autres méthodes de la vitesse de reconstitution de signaux rapides et les petits avantages de calcul.
À l'heure actuelle, le signal de détection comprimé conception matérielle reconfigurable est encore aux étapes préliminaires, il y a encore beaucoup de questions à explorer, des universitaires à cet égard, une série de travaux. Document algorithme de reconstruction du signal de détection comprimé pour la conception VLSI (intégration à très grande échelle, VLSI). algorithme OMP dans un ordre spécifique pour effectuer la conception de matériel de multiplexage des ressources, une meilleure utilisation des ressources, rythme plus rapide course . Document sont PRÉSENTÉES méthode de décomposition de LU basée sur FPGA, une bonne performance d'accélération peut être obtenue sur la plate-forme informatique, cependant, une grande multiplication de matrices de nombre et de la division dans le processus de calcul de la décomposition LU, le besoin FPGA d'occuper une grande quantité de ressources matérielles, entraînant une opération de retard. Section ici par la méthode de décomposition Cholesky de la matrice modifiée de décomposition afin d'éviter l'opération de racine, ce qui réduit le nombre de multiplications, de sorte que l'opération est plus rapide.
1 Orthogonal Matching Pursuit
Détecter la compression du processus d'échantillonnage, le signal d'origine xRN faible densité de K (K < < N), la conception d'un M x N (M < < N) matrice de mesure aléatoire, le vecteur colonne matrice de mesure aléatoire fl (l = 1,2, ..., n) est appelée atomes. La détection de la compression, le signal est clairsemée projection matrice de mesure aléatoire, afin d'obtenir beaucoup plus petite que la longueur du signal original de M observation de l Le vecteur yRN. L'idée de base de l'algorithme de recherche de correspondance est la matrice de mesure aléatoire à partir de la N ième itération? Atomes vertébrales sélectionné qui correspond le mieux le solde courant du signal observé R & lt (initialisé au signal observé y). Le candidat choisi atomique a augmenté à un sous-ensemble? Je souhaite former un nouveau sous-ensemble candidat. Le sous-ensemble de candidats, et calcule une nouvelle estimation signal r nouvelle marge de signal d'observation, la prochaine itération se poursuit avec les atomes restants de signaux observés sélectionnés meilleur candidat d'adaptation pour former un nouveau sous-ensemble pour calculer jusqu'à la fin de l'itération r.
2 Orthogonal Matching Pursuit conception algorithmique
2,1 atomes Orthogonal Matching Pursuit critères de sélection
Utilisation Reference conclusions dérivées des valeurs de mesure y en projection orthogonale Vn + 1 est la suivante:
Dans la formule (3) obtenu sur la base des coefficients de projection orthogonale y sur Vn + 1 est (dans laquelle K = 1,2, ..., n):
Après l'itération n + 1, + 1 || rn || 2 = || y || 2- valeur mesurée y est fixé, faire la plus petite marge de signal r observé, est équivalent à maximisée par la formule (1) à (4) peuvent être obtenus:
calcul algorithme étape 2.2 Orthogonal Matching Pursuit
Orthogonal analysé après l'algorithme correspondant à l'étape de calcul de l'algorithme de suivi atomes de critères de sélection de l'algorithme de reconstruction OMP optimisée de la manière suivante:
Etape 1: Initialiser = 0, r0 = 0, n = 1.
Étape 2: sélectionner le signal observé en cours rn-1 atomes restants meilleur indice de correspondance n = argmaxl = 1,2, ..., N Cl.
Etape 3: à mettre à jour un sous-ensemble candidat n = n-1 posture de coeur n, la matrice de détection atomes d'enregistrement reconstruits ensemble n = ??? .
Etape 4: à l'aide d'un indice de concentration atomique classique approximation du signal original: n = argminy-n.
Étape 5: Mise à jour résiduelle:
Etape 6: n = n + 1, si n < k, le processus retourne à l'étape 2, jusqu'à ce que le dernier signal d'approximation, sinon l'itération est arrêtée.
2.3 Orthogonal Matching conception matérielle Pursuit
OMP algorithme d'optimisation peut être divisé en quatre modules, l'étape de calcul de l'algorithme correspondant à un premier module de reconstruction 2, par l'intermédiaire atomique sélectionné en utilisant l'équation (1) à (5) correspond le mieux aux atomes résiduels est obtenue.
Le second module correspond à une étape de calcul de l'algorithme de reconstruction 3, en mettant à jour le sous-ensemble candidat? Souhaitez générer matrice augmentée n.
Le module d'algorithme de reconstruction troisième correspond à l'étape 4, le modèle de l0 norme minimum pour résoudre le problème, pour résoudre le problème des moindres carrés, le signal original, pour obtenir une valeur estimée. Procédé de matrice augmentée pour la résolution inverse pour dériver la valeur estimée initiale. Cependant, la matrice est la matrice non carrée, pour trouver une matrice non carrée est généralement utilisé pseudo-inverse méthodes (Moore-Penrose) pour la résolution de systèmes, la matrice pseudo-inverse peut être exprimée sous la forme:
Dans la formule (7), de telle sorte que G = T ×, le problème ci-dessus est directement converti en un inverse G résolu. GRt × t est un instant symétrique définie positive, par exemple directement résolu facilement mis en oeuvre sur le FPGA, peut d'abord une décomposition de matrice de la matrice G, puis inversion.
Matrice de factorisation QR-décomposition , décomposition en valeurs singulières, la décomposition LU, la décomposition de Cholesky . QR décomposition, et le processus de calcul de la décomposition en valeurs singulières est complexe et difficile à réaliser dans le FPGA, la décomposition LU de la matrice ont un grand nombre d'opérations de calcul de la multiplication et de la division dans le processus de décomposition, qui d'une part occupe des ressources matérielles FPGA, d'autre part, affectent l'efficacité de calcul. Bien que, dans le calcul de décomposition Cholesky génère un retard de calcul de la racine carrée et les opérations de division, mais la complexité relative de la décomposition LU est moins. décomposition Cholesky pour le problème de retard est généré dans le calcul de l'opération de racine carrée, en utilisant la décomposition de Cholesky, pour éviter un problème de retard causé par le fonctionnement des racines. DÉTAILLÉE correction de décomposition de Cholesky est calculée comme suit:
Le quatrième module d'algorithme de reconstruction correspond à l'étape 5, calcule un résidu r, pour se préparer à l'itération suivante. 3 algorithme d'optimisation de OMP basée sur FPGA
circuit matériel se compose de quatre modules, divisé en deux parties. schéma de circuit spécifique représenté sur la Fig.
La première partie des données entrées, respectivement deux l'observation de la matrice de mesure vecteur y, observation yRN vecteur par l'entrée r résiduel est initialisé. Chaque vecteur de longueur de la colonne de la matrice N, N multiplicateurs conception et N-1 additionneurs traitement parallèle, ce qui peut fonctionner dans un cycle d'horloge, la matrice de mesure? R et la vertèbre résiduelle tout en achevée dans une horloge . vecteur d'observation y est stocké avec une pluralité d'ensembles de registres, une pluralité de mémoire RAM avec la matrice de valeurs de mesure. les critères de sélection Atom optimisés en utilisant la formule (1) à (6) indice des atomes obtenu? Zi n, par l'étape consistant à mettre à jour le sous-ensemble de trois candidats pour obtenir une matrice de reconstruction, la matrice obtenue G.
La seconde partie du processus d'inversion de la matrice G, par le circuit de matériel de circuit matériel de décomposition de Cholesky, l'inversion de la matrice L circuits matériels et le circuit de multiplication de matériel. Utilisation de la matrice de factorisation de Cholesky modifié G, les exigences sont décomposés matrice G L matrice triangulaire inférieure et la matrice diagonale D. Puis en multipliant, tel que G = L × P × LT, contournant ainsi le fonctionnement carré. Dans lequel L entre la matrice et la matrice D sont interdépendants, lesquels éléments doivent être calculés dans un ordre spécifique. Enfin Solution G-1, G-1 = (L-1) T × D-1 × L-1, peut Shilling O = (L-1) T × D-1, pour calculer O, alors commodément calcul de G-1 = O × L-1.
4 simulation
Comparer algorithme de reconstruction et de l'optimisation expérimentale OMP algorithme OMP par un signal unidimensionnel. En supposant que le signal clairsemée de longueur x de N = 256, le coefficient clairsemée k = 6, OMP, algorithme de OMP d'optimisation utilise une matrice de mesure aléatoire gaussienne RM × N, algorithme, respectivement, l'enregistrement optimisé taux de réussite de reconstruction OMP et de l'algorithme OMP, et les résultats représentés graphiquement, comme représenté sur la Fig.
Travailler au même processeur, des expériences d'optimisation signal d'image bidimensionnelle efficacité algorithme de OMP. Experimental sélectionné échelle est de 256 pixels de 256 pixels images expérimentales classiques Lena, la matrice de mesure aléatoire gaussien en tant que matrice. algorithme d'optimisation OMP OMP reconstruction de l'algorithme de comparaison expérimentale ici, le résultat de reconstruction représenté sur la figure.
Lorsque le taux d'échantillonnage de M / N = 50%, en utilisant l'image de test Lena, l'algorithme d'optimisation de OMP, l'algorithme OMP SNR est 34,53 dB, 33,72 dB. Par conséquent, l'algorithme optimisé OMP algorithmes de reconstruction est supérieure à la précision des OMP.
algorithme d'optimisation OMP est effectuée par un logiciel de simulation de circuit matériel FPGA simulation Modelsim, comme le montre la figure.
5. Conclusion
En optimisant les critères de sélection d'atomes, tel algorithme de reconstruction d'OMP peut sélectionner les atomes optimum dans une période de temps très courte, ce qui raccourcit le temps de reconstruction du signal, l'algorithme de reconstruction pour améliorer le taux. En même temps, nous optimisons la conception de la structure matérielle FPGA, un meilleur équilibre gourmand en ressources et le temps de calcul. Cette conception utilise une description du matériel langage Verilog algorithme de reconstruction OMP HDL d'optimisation, en utilisant l'algorithme logiciel intégré Quartus, la description du niveau de RTL, co-simulation par Matlab et Modelsim, obtenir un meilleur effet de la reconstruction. Les résultats ont montré que, OMP algorithme optimisé peut récupérer le signal original avec moins de temps.
références
plus les États-Unis, Zhang Yanning, LI Ying compression perception progrès et les applications de traitement d'image et perspectives Automatica Sinica, 2014,40 (8): 1563-1575.
Donoho D.Compressed détection .IEEE Trans.Info.Theory, 2006,52 (4): 1289-1306.
Mo Yu-jun, Baizheng Yao, Huang et al., Optimized Conception et mise en uvre de FPGA Orthogonal Matching Pursuit Technologie électronique, 2014,50 (10): 79-82.
WANG J, S Kwon, SHIM B.Generalized matching pursuit orthogonal .IEEE Trans.on Signal Processing, 2012,60 (12): 6202-6216.
WU R, W HUANG, CHEN D R.Procédé support exact recoveryof signaux de bruit rares par matching pursuit orthogonal les lettres de traitement de signaux .IEEE Trans.on, 2013,20 (4): 403-406.
Lishao Dong, Pei Wenjiong, Jun Yang, et. OMP dans l'algorithme bayésien de reconstruction du modèle et son application Ingénierie des systèmes et de l'électronique, 2015,37 (2): 246-252.
SEPTINUS A, la reconstruction matérielle STEINBERG R.Compressive .Circuits et systèmes (ISCAS), de Proc.of2010 IEEE Internatioal on.IEEE 2010: 316-3319.
P BLACHE, RABAH H, AMIRA prototypage niveau a.High et FPGA mise en oeuvre du pursuitalgorithm correspondant orthogonal .Information Scien, Traitement du signal et leurs applications (ISSPA), 2012: 1336-1340.
WU G, DOU Y, PETERSON G D.Blocking LU décomposi-tion pour FPGA .IEEE.Proceeding de FCCM'10.ChArlotte: IEEE 2010: 109-112.
STANISLAUS J.L.V.M, la performance Mohsenin T.High matériel de reconstruction de détection avec compression processus QRD .Circuits et systèmes (ISCAS), 2012, IEEE.International Symposium on.IEEE, 2012: 29-32.
Wei Chan, Zhang Juan, l'eau MRS. Procédé de conception inverse décomposition rapide Cholesky de la matrice Ingénierie, électronique, 2014,22 (1): 159-164.
