Johnny Gasperi
email: gasperi@u-pec.fr

Bastien Laborie
email: bastien.laborie@siaap.fr

Vincent Rocher
email: vincent.rocher@siaap.fr

Mots Cles

Traitement des rejets urbains de temps de pluie par clarifloculation : quelle efficacité vis-à-vis des micropolluants ? Treatment of combined sewer overflows by ballasted clarification: which pollutants are removed?

Keywords:

Cette étude a pour but d'évaluer l'efficacité des unités de clarifloculation pour le traitement des rejets urbains de temps de pluie (RUTP), vis-à-vis des nutriments et des micropolluants. Dans ce but, des campagnes de prélèvements ont été menées sur l'unité de clarifloculation de la station d'épuration Seine Aval (Ile-de-France, SIAAP, 1 700 000 m 3 /j) lors de trois événements pluvieux. Outre les paramètres physico-chimiques classiques, un panel de 97 molécules a été recherché. Cinquante-sept substances dont 18 substances prioritaires ont été détectées dans l'influent. En opérant à des doses optimales de réactifs et de micro-sable, l'unité de clarifloculation est capable d'éliminer efficacement les particules, les pollutions carbonées et phosphorées, certains métaux particulaires et les polluants organiques hydrophobes (log Kow > 4). A contrario, elle ne permet qu'une élimination faible à modérée (de < 20% à 50%) de la pollution azotée et des polluants organiques hydrophiles (log Kow < 4). L'efficacité de l'unité de clarifloculation ne semble que très peu impactée par les variations de nature des effluents ou de charge des effluents, mais semble directement dépendre des bons ajustements de réactifs et de sable.

CONTEXTE ENVIROMENTAL

En Europe, la politique de lutte contre la pollution de l'eau fut établie par la Directive Cadre sur l'Eau (DCE 2000/60/EU). Cette Directive modifiée par la Directive 2008/105/CE combine une approche générale de lutte contre le déversement de substances dangereuses ou polluantes dans l'environnement aquatique, et une approche plus spécifique définissant des normes de qualité environnementale pour les polluants prioritaires et certains autres polluants (Annexe I). Pour ces substances, elle exige une réduction progressive des émissions, pertes et rejets ou la cessation de leurs émissions d'ici à 2015. Une des pistes d'action évoquées par la réglementation est de limiter les rejets urbains de temps de pluie, dont l'impact des déversements sur les milieux récepteurs a été largement démontré dans les milieux [START_REF] Krejci | Contribution of different sources to pollutant loads in combined sewers. 4th international conference on Urban Storm Drainage[END_REF].

Au cours des dernières années, différentes stratégies de gestion ont été élaborées pour atténuer l'impact des RUTP, soit en réduisant les volumes ruisselés soit en améliorant leur qualité. Dans le cas d'un réseau unitaire, l'approche la plus couramment adoptée consiste à développer des bassins de stockage ou de rétention pour réduire et/ou différer le pic hydraulique. Suite à la forte affinité de certains polluants historiques (métaux, hydrocarbures aromatiques polycycliques -HAP, etc.) pour les matières en suspension (MES), et afin d'obtenir une meilleure élimination des polluants dans ces bassins, des ouvrages de décantation physico-chimique lamellaire sont parfois associés à ces bassins. Néanmoins, dans les villes où les systèmes de drainage existants ne peuvent pas être facilement adaptés ou repensés, le contrôle et la gestion des RUTP ne peuvent être complétement assurés par ce type de dispositifs.

De ce fait, des technologies permettant un traitement physico-chimique rapide des eaux excédentaires de temps de pluie ont été déployées sur les bassins versants urbanisés, et en particulier en région parisienne. La décantation physico-chimique lestée (Actiflo ® , Véolia) au cours de laquelle la sédimentation des flocs, formés grâce à l'ajout de réactifs coagulant-floculant, est accélérée par l'apport de micro-sable a ainsi été intégrée dans les grandes usines d'épuration parisienne (Seine Aval [Achères, 1 700 000 m 3 /j] et Seine Amont [Valenton, 600 000 m 3 /j]) A ce jour, quelques d'études ont étudié les performances de cette technologie pour traiter les RUTP. Elles reportent des efficacités d'élimination de l'ordre de 70% à 90% pour les MES, et de 40% à 60% pour la demande chimique en oxygène (DCO) [START_REF] Plum | The Actiflo method[END_REF][START_REF] Jacobsen | Microsand ballasted flocculation and clarification for the high rate treatment of stormwaters and sewer overflows[END_REF][START_REF] Delporte | Optimized lamellar settling for urban stormwater waste[END_REF][START_REF] Jolis | Evaluation of high-rate clarification for wet-weather-only treatment facilities[END_REF][START_REF] Zhu | Evaluation of a micro carrier weighted coagulation flocculation process for the treatment of combined sewer overflow[END_REF]. Malgré la contribution significative de ces travaux, ces études délivrent des informations limitées puisque la plupart d'entre elles ont été menées à l'échelle de pilotes de laboratoire ou se sont attachées à étudier les MES et la pollution carbonée. Etant donné qu'un nombre important de polluants dont les polluants prioritaires de la DCE sont véhiculés par les RUTP [START_REF] Gasperi | Priority pollutants in urban stormwater: Part 2 -Case of combined sewers[END_REF], l'efficacité de cette technologie vis à vis de ces polluants doit être évaluée. Ces informations sont primordiales pour évaluer les différentes stratégies de gestion des RUTP qui seront mises en place afin de répondre aux objectifs de la DCE.

Cette étude, menée dans le cadre du programme OPUR (Observatoire des Polluants Urbains), a donc été initiée pour évaluer l'efficacité d'élimination vis à vis d'un large panel de micropolluants d'une unité de clarifloculation pour traiter les RUTP. Dans ce but, l'unité de clarifloculation de la station d'épuration Seine Aval a été étudiée au cours de trois événements pluvieux, pour lesquels 97 substances ont été recherchées. L'objectif de cette étude est plus spécifiquement de relier l'efficacité de la clarifloculation aux conditions opérationnelles d'exploitation. Les résultats sont décrits plus en détails dans une publication récemment acceptée [START_REF] Gasperi | Treatment of combined sewer overflows by ballasted flocculation: removal study of a large broad of pollutants[END_REF].

MATERIEL ET METHODES

Ouvrage industriel étudié : Actiflo® (Seine Aval)

La station de Seine Aval traite quotidiennement 1 700 000 m 3 d'eaux usées (20 m 3 /s), soit environ 80% des eaux résiduaires urbaines parisiennes. La configuration de la station est précisée figure 1. Par temps sec, le traitement des eaux brutes comprend quatre étapes : (1) un prétraitement et un traitement primaire par décantation simple, (2) un traitement biologique par boues activées et (3) un traitement tertiaire (clarifloculation Actiflo®, Figure 2) pour affiner le traitement des MES et de la pollution phosphorée et (4) un traitement par biofiltration permettant la nitrification et la dénitrification des effluents. Après traitement, les effluents sont rejetés en Seine. Par temps de pluie, les RUTP peuvent directement alimenter l'unité de clarifloculation. Selon l'événement, l'unité peut être alimentée exclusivement par des RUTP ou par un mélange plus ou moins important de RUTP et d'eaux usées traitées en sortie de traitement biologique. Le débit maximal d'alimentation de la clarifloculation peut atteindre 35 m 3 /s. Similairement au temps sec, les effluents sont ensuite nitrifiés et dénitrifiés. Quelle que soit la configuration, les doses de réactifs (coagulant -chlorure ferrique (FeCl 3 ) et flocculantpolymère anionique) et de sable sont ajustées grâce à la mesure en ligne de la turbidité en entrée d'ouvrage. Par temps de pluie, les doses optimales préconisées par le constructeur sont comprises entre 40 et 90 g/m 3 de FeCl 3 , 0,5 et 1 g/m 3 de polymère et 3,5 kg/m 3 de sable (granulométrie proche de 100-150 µm). Les micropolluants ont été analysés par un laboratoire extérieur accrédité COFRAC (laboratoire IPL, Bretagne) et par le laboratoire Eau Environnement et Systèmes Urbains (LEESU, tableau 1). Plus précisément, 8 métaux et 72 polluants organiques dont les organoétains, les chlorobenzènes, les chlorophénols, les composés organiques volatils (COV comprenant les BTEX et les COHV), les HAP, les pesticides, les chloroalcanes, les polychlorobiphényles (PCB) et le DEHP (diéthylhexylphthalate) ont été mesurés par le laboratoire IPL Bretagne. Les alkylphénols éthoxylés (7 congénères), le bisphénol A (BPA) et les polybromodiphenylethers (PBDE, 9 congénères) ont été analysés par le laboratoire du LEESU, selon des protocoles analytiques décrits par [START_REF] Gilbert | Devenir des polybromodiphényléthers et des alkylphénols dans les filières de traitement des eaux usées[END_REF]. A l'exception des métaux et des COV analysés sur la fraction totale, les fractions dissoutes et particulaires ont été étudiées (seuil de coupure à 0,45 µm).

RESULTATS ET DISCUSSION

Efficacité vis-à-vis des pollutions carbonées, azotées et phosphorées

Les résultats mettent en évidence une bonne efficacité de l'unité de clarifloculation pour l'élimination des particules et des polluants particulaires, mais des différences significatives apparaissent entre les campagnes (tableau 2). (5,1 kg/m 3 ) comparativement à la campagne 1 (3,2 kg/m 3 ) ne permet pas une meilleure élimination. Cette observation corrobore les résultats de Zhu et al. (2007), démontrant que l'injection de sable jusqu'à 3 kg/m 3 permet l'amélioration de la sédimentation des flocs mais que des doses plus importantes n'y parviennent pas. Comparativement aux premières campagnes, la campagne 3 se démarque par des abattements nettement plus faibles (35% contre > 80% pour les MES, 40% contre > 70% pour la DCO). Ces différences ne sont pas imputables aux doses de polymères appliquées, relativement constantes pour les 3 campagnes (0,80 -1,08 g/m 3 ), mais plutôt à la faiblesse des taux de coagulant (25 -45 g/m 3 contre 70 -80 g/m 3 ) ou de sable (0,7 kg/m 3 contre 3,5 kg/m 3 ).

Pour la pollution carbonée, la DBO 5 est bien éliminée (39% -69%) suite à l'élimination des particules mais aussi de la fraction colloïdale. Cette dernière est confirmée par un abattement du carbone organique dissous (5% -35%) quelle que soit la campagne. L'abattement de la DBO 5 au cours de la campagne 2 apparaît nettement supérieur à ceux des campagnes 1 et 2. Ceci est à relier à la fraction particulaire de DBO 5 plus importante dans les effluents de la campagne 2 comparativement aux autres campagnes. Une élimination de la pollution carbonée dissoute est aussi observée. Alors que des doses de coagulant inférieures aux doses optimales ont été appliquées pour la campagne 3 (25 -45 g/m 3 vs. 70 -80 g/m 3 ), des abattements similaires de la fraction dissoute sont observés pour les trois campagnes. Cette observation suggère que les colloïdes sont éliminés à des doses plus faibles de coagulants que les doses préconisées.

Pour la pollution azotée, seule une partie mineure du NK est éliminée (9% -35%) suite à l'élimination de l'azote organique associé aux particules, tandis que l''ammonium, majoritairement dissous et représentant de l'ordre de 80% de l'azote total, n'est pas éliminé (Boari et al. 1997) Afin de mieux visualiser l'élimination de la fraction particulaire, les abattements des polluants particulaires ont été normalisés à ceux des MES (Figure 4). Cette normalisation met clairement en évidence que pour la plupart des polluants, leur élimination est corrélée à l'élimination des MES puisque les abattements normalisés fluctuent typiquement entre 0,75 et 1,25. De manière surprenante, les abattements normalisés pour la campagne 3 sont clairement supérieurs à 1,25. Ceci suggère que la fraction de MES éliminées pendant la campagne 3 (de l'ordre de 30%) contient une fraction plus importante de polluants que les MES qui n'ont pas sédimenté. Ce résultat corrobore les observations qui ont démontré que la répartition des HAP particulaires par classe de vitesse chute différait de celle des MES [START_REF] Gasperi | Settling Velocity Grading of Particle Bound PAHs: Case of Wet Weather Flows within Combined Sewer Systems[END_REF]. Ces observations ne peuvent pas être mises en exergue pour les campagnes 1-2, pour lesquelles toutes les particules sédimentables ont été piégées.

CONCLUSIONS

En lien avec les exigences de la DCE, cette étude confirme le besoin de traiter les RUTP, pour limiter leurs impacts sur les milieux récepteurs. Les RUTP véhiculent en effet un large panel de composés ; sur les 97 molécules recherchées, 57 (dont 18 de la DCE) ont été détectées. Alors que les concentrations en métaux varient entre 20 et 500 µg/L, les composés organiques présentent des concentrations entre 0,5 et 2 µg/L, à l'exception de quelques substances individuelles telles que le DEHP (4,3 -9,7 µg/L), les COV (1 -8 µg/L) et l'AMPA (3,3 -11,5 µg/L).

La clarifloculation apparaît une technologie prometteuse pour traiter les RUTP, mais pas totalement adaptée pour limiter durablement l'impact des RUTP sur les milieux récepteurs. En opérant à des doses optimales de réactifs et de sable, cette technologie apparaît en effet capable d'éliminer efficacement les particules, les pollutions carbonées et phosphorées. Alors que les métaux (Cu, Pb et Zn) sont efficacement retenus par clarifloculation en raison de leur affinité avec les particules, l'abattement des polluants organiques dépend de leur hydrophobicité (Log Kow). Les composés très hydrophobes (log Kow > 5,5) sont bien éliminés (> 80%), tandis que les polluants organiques hydrophiles (log Kow < 4) ne sont que faiblement éliminés (<20 -50%). Pour les composés intermédiaires (4 < Log Kow < 5,5), les abattements varient entre 50% et 80%. Cette étude souligne également que l'efficacité de l'unité de clarifloculation ne semble que très peu impactée par les variations de nature des effluents ou de charge des effluents, mais semble directement dépendre des bons ajustements de réactifs et de sable.

Une perspective de ce travail pourrait consister à suivre la période de montée en charge de ce type d'unité, non considérée dans cette étude. Certains auteurs soulignent en effet que la montée en charge, dont la durée est comprise entre 10 et 30 minutes, peut constituer un des désavantages de cette technologie, les performances n'étant pas optimales au cours de cette période transitoire [START_REF] Plum | The Actiflo method[END_REF], David et Matos 2005). Par ailleurs, si la clarifloculation semble particulièrement adaptée à l'élimination des particules et de la plupart des polluants hydrophobes, il doit être également mentionné que les RUTP véhiculent de nombreuses autres substances telles que les pesticides, les résidus pharmaceutiques ou les produits de soins corporels [START_REF] Reemtsma | Polar pollutants entry into the water cycle by municipal wastewater: A European perspective[END_REF]. Selon leurs propriétés physico-chimiques, certaines de ces substances ne seront pas ou peu éliminées par clarifloculation. Il serait donc pertinent de voir dans quelle mesure les technologies nouvelles, actuellement développées par les constructeurs français (Actiflo TM Carb [Véolia], CarboPlus ® [Stéreau], etc.), sont adaptées au traitement de ces molécules.

BIBLIOGRAPHIE

Figure 1 :

 1 Figure 1 : Configuration de la station Seine Aval par temps sec et par temps de pluie Les effluents en entrée et en sortie de clarifloculation ont été échantillonnés au moyen de préleveurs automatiques asservis au débit et équipés d'un mono flacon en verre de 20 l et de tuyaux en téflon ® . Le prélèvement a été déclenché dès dépassement d'une valeur seuil fixée à 12 m 3 /s et la durée de la collecte a été fixée à 3h. Trois campagnes ont été réalisées les 7 juin (campagne 1), 20 juin (campagne 2) et 19 juillet 2011 (campagne 3), campagnes au cours desquelles les précipitations journalières étaient respectivement de 8,6, 13,4 et 24,7 mm. Les campagnes 2 et 3 correspondent à des orages d'été importants, et les eaux alimentant la clarifloculation étaient exclusivement composées de RUTP. La campagne 1 correspond à un événement pluvieux plus modéré, et un mélange entre RUTP (60%) et eaux usées traitées (40%) a alimentée l'unité. Les vitesses ascensionnelles ont été respectivement estimées à 52, 66 et 67 m/h. Selon le nombre d'Actiflo® en service, le temps de séjour hydraulique varie entre 19 et 28 minutes. Les doses de réactifs et de sable appliquées lors de ces campagnes sont présentées par la Figure 2.

Figure 2 :

 2 Figure 2 : Actiflow® technologie et dose de réactifs appliquées pendant les 3 campagnes 2.2 Paramètres classiques et micropolluants Les paramètres classiques tels que les MES, les demandes chimiques et biochimiques en oxygène (DCO et DBO 5 ), le carbone organique total, dissous et particulaire (COT, COD et COP), l'ammonium (NH 4 + ), l'azote Kjeldahl (NK), le phosphore total et dissous (Ptot et Pdiss) et les orthophosphates (PO 4 3-) ont été analysés selon les normes françaises de qualité AFNOR par le laboratoire interne du SIAAP (accrédité COFRAC).

  (1) Famille : BTEX = benzène, toluène, éthylbenzène et xylènes, COHV = Composés Organiques Halogénés Volatils, HAP = Hydrocarbures Aromatiques Polycycliques, PBDE = polybromodiphényléthers, PCB = Polychlorobiphényles, (2) Le nombre de substances de la Directive Cadre sur l'Eau est indiqué entre parenthèses, (3) Méthodes analytiques utilisées, ICP = spectromètre d'émission atomique, SAA = spectrométrie d'absorption atomique, GC = chromatographie gazeuse, GC-ECD = GC avec détection en capture d'électrons, GC-MS = GC avec spectrométrie de masse, GC-MSMS = GC avec spectrométrie de masse en tandem, HPLC-fluo = chromatographie liquide couplée avec un détecteur à fluorescence, UPLC-MSMS = chromatographie liquide haute performance avec spectrométrie de masse en tandem, (4) Phases considérées, D = dissous, P = particulaire, T = Total.

  Kow = -0,82 et 0,12 respectivement). Ces différences pourraient découler de la présence de groupements polaires et anioniques pour ces molécules, conduisant à une répartition dissousparticulaire sensiblement différente de la répartition théorique. Les abattements plus importants observés pour les premières campagnes comparativement à la campagne 3 confirment que ces composés ne sont pas exclusivement sous forme dissoute et qu'une fraction est associée aux particules. Pour les composés hydrophiles, les concentrations en sortie d'ouvrage varient entre 0,5 et 1 µg/L, à l'exception des COV avec des concentrations supérieures à 7 µg/L.

Figure 3 :

 3 Figure 3 : Abattements des polluants organiques selon leur log Kow Les abattements pour les composés hydrophobes (log Kow > 4) sont significativement corrélés à ceux des MES, et par conséquent varient sensiblement entre les campagnes 1-2 (doses optimales de réactifs et de sable) et 3. Sous conditions opérationnelles optimales, les composés très hydrophobes (log Kow > 5,5) sont abattus à plus de 80% sur les ouvrages de clarifloculation. Parmi ces composés, les HAP de haut poids moléculaires (chrysène, benzo(a)anthracène, benzo(a)pyrène, benzo(b et k)fluoranthène benzo(ghi)pérylène, indéno(cd)pyrène et dibenzo(ah)anthracène), les PCB (PCB 138, PCB 153 et PCB 180) et les PBDE (BDE-47, BDE-99, BDE-100 et BDE-209) sont très efficacement éliminés et les concentrations en sortie d'ouvrage n'excèdent pas 0,1 µg/L. Pour les composés moyennement hydrophobes (4 < Log Kow < 5,5), les abattements varient entre 50% et 80%.

Figure 4 :

 4 Figure 4 : Abattements normalisés des polluants organiques particulaires par rapport aux MES Parallèlement à l'élimination de la fraction particulaire, l'unité de clarifloculation semble également permettre une élimination plus ou moins importante de la fraction dissoute (Figure 5).

Figure 5 :

 5 Figure 5 : Abattements des polluants organiques dissous par clarifloculation Selon la substance considérée, l'abattement peut fluctuer entre 0% et 60%. Pour quelques polluants comme les nonylphénols (NP, 18% -45%), le bisphénol A (BPA, 10% -31%), le BDE-209 (9% -24%),

  Boari, G.,Mancini, I.M. et Trulli, E. (1997) Technologies for water and wastewater treatment. CIHEAM -Options Mediterraneennes 31, 262-287. Crittenden, J.C., Trussell, R.R., Hand, D.W., Howe, K.J. et Tchobanoglous, G. (2005) Water Treatment -Principles and Design (2nd Edition), John Wiley & Sons. David, L.M. et Matos, J.S. (2005) Combined sewer overflow emissions to bathing waters in Portugal. How to

  . Au contraire, des éliminations significatives sont observées pour les orthophosphates (90% -95%) et le phosphore dissous (83% -89%). Leur élimination est essentiellement liée à la précipitation des orthophosphates et du phosphore dissous avec les ions métalliques (FePO 4 )(Crittenden et al. 2005). Comme précédemment observé, une élimination équivalente de la pollution phosphorée est observée pour la campagne 3, en dépit de la dose plus faible de chlorure ferrique. Quelle que soit la campagne, les concentrations en sortie de clarifloculation sont < 0,3 mg/L pour le phosphore dissous et < 0,1 mg/L pour les orthophosphates. Alors que le MBT et TBT sont préférentiellement associés aux MES, aucune tendance ne peut être donnée pour le TBT qui n'a pas été détecté dans la phase particulaire probablement dû à des limites de quantification plus élevées. Pour les campagnes 1 et 2, entre 66% et 69% du DBT et entre 63% et 80% du MBT particulaires sont éliminés par clarifloculation.

	Tableau 2 : Abattements (%) en paramètres globaux et concentrations en sortie de clarifloculation
			Campagne 1		Campagne 2		Campagne 3
			Abat (%)	Conc 1	Abat (%)	Conc 1	Abat (%)t	Conc 1
	MES	mg/L	86,7	27,0	80,2	78,0	34,1	193,1
	COT	mg C/L	34,1	16,2	39,2	19,6	20,5	28,5
	COP	mg C/L	84,8	1,1	77,5	3,1	42,2	7,1
	COD	mg C/L	12,0	15,1	11,2	16,6	9,2	21,4
	DCO	mg O2/L	75,2	67,0	76,8	130,0	40,0	270,0
	DBO 5	mg O2/L	42,0	29,0	69,2	20,0	38,5	80,0
	NTK	mg N/L	13,3	39,0	34,5	19,0	8,7	42,0
	NH 4 +	mg N/L	1,3	36,8	-6,6	17,7	-3,3	31,4
	Ptot	mg P/L	86,4	0,6	88,4	0,5	43,1	3,7
	Pdiss	mg P/L	87,0	< 0,3	83,3	< 0,3	89,6	< 0,3
	PO 4 3-	mg P/L	90,0	< 0,1	93,0	< 0,1	95,0	< 0,1
	Les abattements observés pour les composés organiques diffèrent d'une molécule à l'autre. Ces
	différences de comportement peuvent être expliquées en considérant les propriétés physico-
	chimiques des molécules et, en particulier, leur hydrophobicité ; le caractère hydrophile ou
	hydrophobe d'une molécule étant généralement apprécié en s'appuyant sur le coefficient de partage
	octanol -eau (log Kow). La figure 3 illustre l'abattement des différents composés organiques en
	fonction de leur log Kow. Quelle que soit la campagne, les composés hydrophiles (log Kow < 4) sont
	de très faiblement (< 20%) à faiblement (< 50%) éliminés. Au total, 13 substances sont concernées
	dont 5 pesticides (glyphosate, métaldéhyde, diuron, aminotriazole et acide amino
	méthylphosphonique -AMPA), 6 COV (isopropylbenzène, tri-et tétra-chloroéthylènes, toluène,

1 = concentrations en sortie de clarifloculation

3.2 Efficacité vis-à-vis des micropolluants

Selon la campagne, de 47 à 52 substances ont été détectées dans les effluents en entrée de l'unité de clarifloculation. Sur les 97 molécules recherchées, 57 (dont 18 de la DCE) ont été détectées au moins une fois. Parmi ces molécules, on retrouve classiquement 3 métaux, 8 COV, 3 organoétains, 10 pesticides, 16 HAP, 3 PCB, 7 alkylphénols, 4 PBDE et d'autres substances individuelles telles que les chloroalcanes, le bisphénol A et le DEHP. Le profil des molécules des eaux alimentant l'unité de clarifloculation est tout à fait comparable à ceux mentionnés par

[START_REF] Gasperi | Priority pollutants in urban stormwater: Part 2 -Case of combined sewers[END_REF]

pour les surverses unitaires de temps de pluie sur le déversoir d'orage de Clichy en région parisienne.

Les métaux sont globalement bien retenus par clarifloculation, confirmant l'intérêt de cette technologie pour ces éléments. Les abattements fluctuent entre 70% -80% pour le Pb et le Cu et entre 85% -90% pour le Zn, conduisant à des concentrations respectivement inférieures à 10 µg/L et à 70 µg/L. Ce piégeage important de la pollution métallique est lié à la forte affinité de ces métaux pour la phase particulaire dans les RUTP.

Les organoétains (mono-, di-et tri-butyl étains, MBT, DBT, TBT) sont modérément abattus (50% -80%) dans les conditions optimales. éthylbenzène et xylènes), le bisphénol et le butylphénol. Pour ces composés, aucune différence n'est observée entre les campagnes, suggérant que leur élimination n'est pas reliée à l'abattement des MES mais plutôt à l'élimination de la fraction colloïdale. Un comportement particulier est observé pour le glyphosate (34% -58%) et l'AMPA (26% -42%), pour lesquels les résultats mettent en évidence des abattements plus élevés que ceux attendus théoriquement à partir de leur hydrophobicité (log

  le fluoranthène (9% -27%), l'aminotriazole (12% -25%) et le glyphosate(38% et 44%, n=2), un abattement relativement constant de l'ordre de 10% à 40% est observé. Pour ces polluants, les abattements de la fraction dissoute semblent légèrement supérieurs aux abattements du COD (9% -12%), mais comparables à ceux obtenus pour la DBO 5 (5% -35%). Les abattements pour les autres composés tels que le pyrène (29% -67%), le nonylphénol monoéthoxylé (NP1EO, 23% -59%), le butylphénol (50% -55%), l'AMPA (25% -73%) et les n=1) varient fortement d'une campagne à une autre, mais s'avèrent très supérieurs à l'élimination de la pollution carbonée dissoute. Etant donné le nombre limité de campagnes, aucune relation claire ne peut être établie entre l'abattement de la fraction dissoute et les propriétés physico-chimiques des polluants. Il est probable que l'élimination de cette fraction dissoute est liée soit à l'élimination de la fraction colloïdale (et donc en partie aux interactions entre ces contaminants et les colloïdes), soit à d'autres processus qui ont lieu lors des phases de coagulation-floculation. Par l'intermédiaire du chlorure ferrique qui s'hydrolyse et forme des hydroxydes de fer (FeOH 3 pour sa forme la plus simple), les colloïdes se retrouvent déstabilisés suite à la neutralisation de leurs charges superficielles. Une fois déstabilisés par l'étape de coagulation les colloïdes s'agrègent ensuite sous forme de micro-flocs. Comme le suggèrent[START_REF] Martinez | Solubility of Cd 2+ , Cu 2+ , Pb 2+ , and Zn 2+ in aged coprecipitates with amorphous iron hydroxides[END_REF][START_REF] El Samrani | Chemical coagulation of combined sewer overflow: Heavy metal removal and treatment optimization[END_REF] pour la pollution métallique dissoute, il se pourrait qu'une certaine fraction de pollution dissoute s'adsorbe sur les formes plus ou moins complexes d'hydroxydes de fer.


Sheng Wu

Dalal Fadil

Shuang Liu

Ammar Aryan

B Renault

Jean-Marc Routoure

Bruno Guillet

Stéphane Flament

Pierre Langlois

Laurence Méchin

La0.7Sr0.3MnO3 Thin Films for Magnetic and Temperature Sensors at Room Temperature

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.


Ammar Aryan

Jean-Marc Routoure

Bruno Guillet

Pierre Langlois

Cédric Fur

Julien Gasnier

Carolina Adamo

Darrell G Schlom

Laurence Méchin

Optical Characterisation of La0.7Sr0.3MnO3 Thin Film Based Uncooled Bolometers

come


Alexander Zeh

San Ling
email: lingsan@ntu.edu.sg

Decoding of Quasi-Cyclic Codes up to A New Lower Bound on the Minimum Distance

Keywords: minimum distance, efficient decoding, quasi-cyclic code, spectral analysis

A new lower bound on the minimum Hamming distance of linear quasi-cyclic codes over finite fields is proposed. It is based on spectral analysis and generalizes the Semenov-Trifonov bound in a similar way as the Hartmann-Tzeng bound extends the BCH approach for cyclic codes. Furthermore, a syndrome-based algebraic decoding algorithm is given.

I. INTRODUCTION

The class of linear quasi-cyclic codes over finite fields is a generalization of cyclic codes and is known to be asymptotically good (see, e.g., Chen-Peterson-Weldon [START_REF] Chen | Some Results on Quasi-Cyclic Codes[END_REF]). Many of the best known linear codes belong to this class (see, e.g., Gulliver-Bhargava [START_REF] Gulliver | Some Best Rate 1/p and Rate (p-1)/p Systematic Quasi-Cyclic Codes[END_REF] and Chen's database [START_REF] Chen | A Database on Binary Quasi-Cyclic Codes[END_REF]). Several good LDPC codes are quasi-cyclic and the connection to convolutional codes was investigated among others in [START_REF] Solomon | A Connection Between Block and Convolutional Codes[END_REF]- [START_REF] Lally | Algebraic Lower Bounds on the Free Distance of Convolutional Codes[END_REF].

The algebraic structure of quasi-cyclic codes was exploited in various ways (see, e.g., Lally-Fitzpatrick [START_REF] Lally | Algebraic Structure of Quasicyclic Codes[END_REF], Ling-Solé [START_REF] Ling | On the Algebraic Structure of Quasi-Cyclic Codes I: Finite fields[END_REF]- [START_REF] Ling | On the Algebraic Structure of Quasi-Cyclic Codes III: Generator Theory[END_REF], Barbier et al. [START_REF] Barbier | On Quasi-Cyclic Codes as a Generalization of Cyclic Codes[END_REF], [START_REF] Barbier | On the Decoding of Quasi-BCH Codes[END_REF]), but the estimates on the minimum distance are far away from the real minimum distance and thus the guaranteed decoding radius. Recently, Semenov and Trifonov [START_REF] Semenov | Spectral Method for Quasi-Cyclic Code Analysis[END_REF] developed a spectral analysis of quasi-cyclic codes based on the work of Lally and Fitzpatrick [START_REF] Lally | Algebraic Structure of Quasicyclic Codes[END_REF], [START_REF] Lally | Construction and Classification of Quasicyclic Codes[END_REF] and formulated a BCH-like lower bound on the minimum distance of quasi-cyclic codes.

We generalize the Semenov-Trifonov [START_REF] Semenov | Spectral Method for Quasi-Cyclic Code Analysis[END_REF] bound on the minimum distance of quasi-cyclic codes. Our new approach is similar to the Hartmann-Tzeng (HT, [START_REF] Hartmann | Decoding Beyond the BCH Bound[END_REF], [START_REF] Hartmann | Generalizations of the BCH Bound[END_REF]) bound, which generalizes the BCH [START_REF] Bose | On A Class of Error Correcting Binary Group Codes[END_REF], [START_REF] Hocquenghem | Codes Correcteurs d'Erreurs[END_REF] bound for cyclic codes. Moreover, we prove a quadratic-time syndrome-based algebraic decoding algorithm up to the new bound and show that it is advantageous in the case of burst errors.

This paper is organized as follows. In Section II, we recall the Gröbner basis representation of quasi-cyclic codes of Lally-Fitzpatrick [START_REF] Lally | Algebraic Structure of Quasicyclic Codes[END_REF], [START_REF] Lally | Construction and Classification of Quasicyclic Codes[END_REF] and the definitions of the spectral method of Semenov-Trifonov [START_REF] Semenov | Spectral Method for Quasi-Cyclic Code Analysis[END_REF]. The new HT-like bound on the minimum distance is formulated and proven in Section III. Section IV describes a syndrome-based decoding algorithm up to our bound and shows that in the case of burst errors more A. Zeh has been supported by the German research council (Deutsche Forschungsgemeinschaft, DFG) under grant Ze1016/1-1. S. Ling has been supported by NTU Research Grant M4080456. symbol errors can be corrected. We draw some conclusions in Section V.

II. PRELIMINARIES

A. Reduced Gröbner Basis

Let F q denote the finite field of order q and F q [X] the polynomial ring over F q with indeterminate X. Let z be a positive integer and denote by [z] the set of integers {0, 1, . . . , z -1}. A vector of length n is denoted by a lowercase bold letter as

v = (v 0 v 1 . . . v n-1 ) and v • w denotes the scalar product n-1 i=0 v i w i of two vectors v, w of length n. An m × n matrix is denoted by a capital bold letter as M = (m i,j ) j∈[n] i∈[m] . A linear [m • ℓ, k, d] q code C
of length mℓ, dimension k and minimum Hamming distance d over F q is ℓ-quasi-cyclic if every cyclic shift by ℓ of a codeword is again a codeword of C, more explicitly if:

(c 0,0 . . . c ℓ-1,0 c 0,1 . . . c ℓ-1,1 . . . c ℓ-1,m-1 ) ∈ C ⇒ (c 0,m-1 . . . c ℓ-1,m-1 c 0,0 . . . c ℓ-1,0 . . . c ℓ-1,m-2 ) ∈ C. We can represent a codeword of an [m • ℓ, k, d] q ℓ-quasi-cyclic code as c(X) = (c 0 (X) c 1 (X) . . . c ℓ-1 (X)) ∈ F q [X] ℓ , where c i (X) def = m-1 j=0 c i,j X j , ∀i ∈ [ℓ].
Then, the defining property of C is that each component c i (X) of c(X) is closed under multiplication by X and reduction modulo X m -1. Lally and Fitzpatrick [START_REF] Lally | Algebraic Structure of Quasicyclic Codes[END_REF], [START_REF] Lally | Construction and Classification of Quasicyclic Codes[END_REF] showed that this enables us to see a quasi-cyclic code as an F q [X]/ X m -1 -submodule of the algebra (F q [X]/ X m -1 ) ℓ and they proved that every quasi-cyclic code has a generating set in the form of a reduced Gröbner basis with respect to the positionover-term order in F q [X] ℓ . This basis can be represented in the form of an upper-triangular ℓ × ℓ matrix with entries in F q [X] as follows:

G(X) =      g 0,0 (X) g 0,1 (X) • • • g 0,ℓ-1 (X) g 1,1 (X) • • • g 1,ℓ-1 (X) 0 . . . . . . g ℓ-1,ℓ-1 (X)      , (1)
where the following conditions must be fulfilled:

1) g i,j (X) = 0, ∀0 ≤ j < i < ℓ, 2) deg g j,i (X) < deg g i,i (X), ∀j < i, i ∈ [ℓ], 3) g i,i (X)|(X m -1), ∀i ∈ [ℓ], 4) if g i,i (X) = X m -1 then g i,j (X) = 0, ∀j = i + 1, . . . , ℓ -1. A codeword of C can be represented as c(X) = a(X) G(X) and it follows that k = mℓ - ℓ-1 i=0 deg g i,i (X).
For ℓ = 1, the generator matrix G(X) becomes the wellknown generator polynomial of a cyclic code of degree m-k. We restrict ourselves throughout this paper to the single-root case, i.e., gcd(m, char(F q )) = 1.

B. Spectral Analysis of Quasi-Cyclic Codes

Let G(X) be the upper-triangular generator matrix of a given [m • ℓ, k, d] q ℓ-quasi-cyclic code C in reduced Gröbner basis form as in [START_REF] Chen | Some Results on Quasi-Cyclic Codes[END_REF]. Let α ∈ F q r be an m-th root of unity. An eigenvalue λ i = α ji of C is defined to be a root of det( G(X)), i.e., a root of ℓ-1 i=0 g i,i (X). The algebraic multiplicity of λ i is the largest integer u i such that (X -λ i ) ui | det( G(X)). Semenov and Trifonov [START_REF] Semenov | Spectral Method for Quasi-Cyclic Code Analysis[END_REF] defined the geometric multiplicity of an eigenvalue λ i as the dimension of the right kernel of the matrix G(λ i ), i.e., the dimension of the solution space of the homogeneous linear system of equations:

G(λ i )v = 0. (2)
The solution space of ( 2) is called the right kernel eigenspace and it is denoted by V i . Furthermore, it was shown that, for a matrix G(X) ∈ F q [X] ℓ×ℓ in the reduced Gröbner basis representation, the algebraic multiplicity u i of an eigenvalue λ i equals the geometric multiplicity (see [START_REF] Semenov | Spectral Method for Quasi-Cyclic Code Analysis[END_REF]Lemma 1]). Moreover, they gave in [START_REF] Semenov | Spectral Method for Quasi-Cyclic Code Analysis[END_REF] an explicit construction of the parity-check matrix of an [m • ℓ, k, d] q ℓ-quasi-cyclic code C and proved a BCH-like [START_REF] Bose | On A Class of Error Correcting Binary Group Codes[END_REF], [START_REF] Hocquenghem | Codes Correcteurs d'Erreurs[END_REF] lower bound on d using the parity-check matrix and the so-called eigencode. We generalize their approach, but do not explicitly need the paritycheck matrix for the proof though the eigencode is still needed.

Definition 1 (Eigencode). Let V ⊆ F ℓ q r be an eigenspace. Define the [n ec = ℓ, k ec , d ec ] q eigencode corresponding to V by C(V) def = (c 0 . . . c ℓ-1 ) ∈ F ℓ q | ∀v ∈ V : ℓ-1 i=0 v i c i = 0 . (3) If there exists v = (v 0 v 1 . . . v ℓ-1
) ∈ V such that the elements v 0 , v 1 , . . . , v ℓ-1 are linearly independent over F q , then C(V) = {(0 0 . . . 0)} and d ec is infinity. To describe quasi-cyclic codes explicitly, we need to recall the following facts about cyclic codes. A q-cyclotomic coset M i is defined as:

M i def = iq j mod m | j ∈ [a] , (4)
where a is the smallest positive integer such that iq a ≡ i mod m. The minimal polynomial in F q [X] of the element α i ∈ F q r is given by m i (X) = j∈Mi (X -α j ).

III. IMPROVED LOWER BOUND

In this section, we generalize the lower bound on the minimum distance of quasi-cyclic codes given in [START_REF] Semenov | Spectral Method for Quasi-Cyclic Code Analysis[END_REF]Thm. 2] in a similar way as the Hartmann-Tzeng bound [START_REF] Hartmann | Decoding Beyond the BCH Bound[END_REF], [START_REF] Hartmann | Generalizations of the BCH Bound[END_REF] generalizes the BCH bound [START_REF] Bose | On A Class of Error Correcting Binary Group Codes[END_REF], [START_REF] Hocquenghem | Codes Correcteurs d'Erreurs[END_REF] for cyclic codes.

Theorem 1 (New Lower Bound). Let C be an [m • ℓ, k, d] q ℓquasi-cyclic code and let α ∈ F q r denote an element of order m. Define the set

D def = f, f + z, . . . ,f + (δ -2)z, f + 1, f +1 + z, . . . , f + 1 + (δ -2)z, . . . . . . • • • . . . f + ν, f + ν + z, . . . , f + ν + (δ -2)z ,
for some integers f , δ > 2 and z > 0 with gcd(m, z) = 1.

Let the eigenvalues λ i = α i , ∀i ∈ D, their corresponding eigenspaces V i , ∀i ∈ D, be given, and let their intersection be

V def = i∈D V i . Let d ec denote the distance of the eigencode C(V) and let v = (v 0 v 1 . . . v ℓ-1 ) ∈ V be an eigenvector where v 0 , v 1 , . . . , v ℓ-1 are linearly independent over F q . If ∞ i=0 c(α f +zi+j ) • vX i ≡ 0 mod X δ-1 , ∀j ∈ [ν + 1], (5) holds for all c(X) = c 0 (X) c 1 (X) . . . c ℓ-1 (X) ∈ C, then, d ≥ d * def = min(δ + ν, d ec ). Proof: Let c i (X) = j∈Yi c i,j X j , ∀i ∈ [ℓ]
, where c i,j ∈ F q . We can write the LHS of (5) more explicitly:

∞ i=0 ℓ-1 t=0 c t (α f +zi+j )v t X i ≡ 0 mod X δ-1 , ∀j ∈ [ν + 1]. (6)
Now, define:

Y = {i 0 , i 1 , . . . , i y-1 } def = ℓ-1 i=0 Y i ⊆ [m]. (7)
We obtain from ( 6) with ( 7) :

∞ i=0 s∈Y ℓ-1 t=0 c t,s v t α (f +zi+j)s X i ≡ 0 mod X δ-1 , ∀j ∈ [ν + 1]. ( 8
)
We define m elements in F q r as follows:

C s def = ℓ-1 t=0 c t,s v t , ∀s ∈ [m]. (9)
With ( 9), we can simplify [START_REF] Ling | On the Algebraic Structure of Quasi-Cyclic Codes I: Finite fields[END_REF] to

∞ i=0 s∈Y C s α (f +zi+j)s X i ≡ 0 mod X δ-1 , ∀j ∈ [ν + 1]. (10)
We linearly combine the ν + 1 sequences of [START_REF] Ling | On the Algebraic Structure of Quasi-Cyclic Codes III: Generator Theory[END_REF], multiply each of them by an element ω j ∈ F q r \{0} and obtain:

ν j=0 ω j ∞ i=0 s∈Y C s α (f +zi+j)s X i ≡ 0 mod X δ-1 . ( 11
)
Interchanging the sums in [START_REF] Barbier | On Quasi-Cyclic Codes as a Generalization of Cyclic Codes[END_REF] leads to:

∞ i=0 s∈Y C s α (f +zi)s ν j=0 ω j α js X i ≡ 0 mod X δ-1 . ( 12
)
We choose ω 0 , ω 1 , . . . , ω ν such that the first ν terms with coefficients C i0 , C i1 , . . . , C iν-1 are annihilated. We obtain the following linear (ν + 1) × (ν + 1) system of equations:

     1 α i0 α i02 • • • α i0ν 1 α i1 α i12 • • • α i1ν . . . . . . . . . . . . . . . 1 α iν α iν 2 • • • α iν ν           ω 0 ω 1 . . . ω ν      =      0 . . . 0 1      , (13)
with Vandermonde structure and therefore the non-zero solution is unique. Let Y def = Y \ {i 0 , i 1 , . . . , i ν-1 }. Then we can rewrite [START_REF] Barbier | On the Decoding of Quasi-BCH Codes[END_REF]:

∞ i=0 s∈ Y C s α (f +zi)s ν j=0 ω j α js X i ≡ 0 mod X δ-1 . (14)
With the geometric series we get from [START_REF] Lally | Construction and Classification of Quasicyclic Codes[END_REF]:

s∈ Y C s α sf ν j=0 ω j α js 1 -α zs X ≡ 0 mod X δ-1 ,
and writing each fraction as an equivalent fraction with the least common denominator leads to:

s∈ Y C s α sf ν j=0 ω j α js h∈ Y h =s (1 -α zh X) s∈ Y (1 -α zs X) ≡ 0 mod X δ-1 , (15)
where the degree of the numerator is at most | Y|-1 = y-ν-1 and has to be at least δ -1.

To bound the distance d we distinguish two cases. For the first case where d ec > δ + ν, at least y -ν elements C i ∈ F q r have to be non-zero such that (15) holds, i.e., at least y -ν elements c t0,i0 , c t1,i1 , . . . , c ty-1-ν ,iy-1-ν ∈ F q for t 0 , . . . , t y-1-ν distinct, have to be non-zero and therefore

d -ν -1 ≥ δ -1 ⇐⇒ d ≥ δ + ν.
For the second case where d ec < δ +ν, at least d ec elements c j,i0 , c j,i1 , . . . , c j,i d ec -1 have to be non-zero (see [START_REF] Ling | On the Algebraic Structure of Quasi-Cyclic Codes II: Chain Rings[END_REF]) such that C j = 0 and if all the other C s , s ∈ Y\{j}, are zero, then the LHS of (15) becomes zero. In this case d ≥ d ec .

For ν = 0, the bound of Theorem 1 becomes the bound of Semenov-Trifonov (see [START_REF] Semenov | Spectral Method for Quasi-Cyclic Code Analysis[END_REF]Thm. 2]). We chose to state Thm. 1 in terms of all c(X) ∈ C (see [START_REF] Esmaeili | A Link Between Quasi-Cyclic Codes and Convolutional Codes[END_REF]) to easily obtain a syndrome expression (see Section IV). In practice, from the spectral analysis of G(X), one can search for eigenvalues of the form α i , for i in some D of the form in Thm. 1, and determine the corresponding eigencode with its minimum distance. The condition ( 5) is then automatically satisfied for all codewords c(X) ∈ C, with the corresponding f , z and δ.

Example 1 (HT-like Bound for Quasi-Cyclic Code). Let C be the binary [63 • 2, 100, 6] 2 2-quasi-cyclic code with 2 × 2 generator matrix in reduced Gröbner form as defined in (1):

G(X) = g 0,0 (X) g 0,1 (X) 0 g 1,1 (X) ,
where:

g 0,0 (X) = m 0 (X)m 1 (X)m 9 (X), g 0,1 (X) = g 0,0 (X)a 0,1 (X), g 1,1 (X) = g 0,0 (X)m 5 (X)
,

and a 0,1 (X) = X 4 + X 3 + X 2 + X + 1 with deg a 0,1 (X) < deg m 5 (X) and a 0,1 (X) ∤ (X 63 -1). Let α ∈ F 2 6 ∼ = F 2 [X]/(X 6 + X 4 + X 3 + X + 1
) be an element of order 63. The eigenvalues λ i = α i , i ∈ {0, 1, 2, 4, 8, 9, 16, 18, 32, 36} = M 0 ∪ M 1 ∪ M 9 are the roots of g 0,0 (X), g 0,1 (X), g 1,1 (X) and have (algebraic and geometric) multiplicity two. Therefore, the corresponding eigenvectors span the full space F 2 2 6 . The distinct eigenvectors v (i) , ∀i ∈ M 5 , are in F 2 2 6 and v

(i) 0 , v (i) 1 ∈ F 2 6 , are linearly independent over F 2 for each i ∈ M 5 .
With f = 0, z = 4, δ = 4, ν = 1, we obtain two consecutive sequences of eigenvalues α 0 , α 4 , α 8 and α 1 , α 5 , α 9 of length three, where v

(5) 0 = 1, v (5)
1 = α 4 + 1, are linearly independent over F 2 and v (5) is contained in the intersection of the eigenspaces V i , i ∈ D def = {0, 4, 8, 1, 5, 9}, and therefore

d ec = ∞ of C(∩ i∈D V i ). With

IV. SYNDROME-BASED DECODING OF QUASI-CYCLIC CODES

In this section, we develop a syndrome-based decoding algorithm, which guarantees to correct up to ⌊(d * -1)/2⌋ symbol errors in F q . Let the received word of a given [m • ℓ, k, d] q ℓquasi-cyclic code be:

r(X) = r 0 (X) . . . r ℓ-1 (X) = c 0 (X) + e 0 (X) . . . c ℓ-1 (X) + e ℓ-1 (X)
,

where e i (X) = j∈Ei e i,j X j , i ∈ [ℓ], (16)
are ℓ error polynomials in F q [X] with ε i def = |E i | and degree less than m. The number of errors in F q is ε def = ℓ-1 i=0 ε i . Define the following set of burst errors:

E def = ℓ-1 i=0 E i ⊆ [m]. ( 17
)
with cardinality

ε def = |E| ≤ ε.
In the following, we describe a decoding procedure that is able to decode up to ε ≤ τ errors, where:

τ ≤ d * -1 2 . ( 18
)
Let α ∈ F q r denote an m-th root of unity and let the

(ν + 1)(δ -1) eigenvalues λ i = α f +iz+j , ∀i ∈ [δ - 1], j ∈ [ν + 1]
, the integer f and the integer z > 0 with gcd(z, m) = 1 be given as stated in Thm. 1. Furthermore, let V = i∈[δ-1],j∈[ν+1] V f +iz+j and let one eigenvector v = (v 0 v 1 . . . v ℓ-1 ) ∈ V, where v 0 , v 1 , . . . , v ℓ-1 are linearly independent over F q , be given. We assume that the minimum distance of the corresponding eigencode C(V) is greater than δ + ν. Then, we define the following ν + 1 syndrome polynomials in F q r [X]:

S t (X) def ≡ ∞ i=0 ℓ-1 j=0 r j (α f +iz+t )v j X i mod X δ-1 = δ-2 i=0 ℓ-1 j=0 r j (α f +iz+t )v j X i , ∀t ∈ [ν + 1]. ( 19
)
From Thm. 1 it follows that the syndrome polynomials as defined in [START_REF] Feng | A Generalized Euclidean Algorithm for Multisequence Shift-Register Synthesis[END_REF] depend only on the error and therefore:

S t (X) = δ-2 i=0 ℓ-1 j=0 e j (α f +iz+t )v j X i , ∀t ∈ [ν + 1].
Define an error-locator polynomial in F q r [X]:

Λ(X) = ε i=0 Λ i X i def = i∈E (1 -Xα iz ). (20)
Like in the classical case of cyclic codes, we get ν + 1 Key Equations with a common error-locator polynomial Λ(X) as defined in [START_REF] Feng | A Generalization of the Berlekamp-Massey Algorithm for Multisequence Shift-Register Synthesis with Applications to Decoding Cyclic Codes[END_REF]:

Λ(X) • S t (X) ≡ Ω t (X) mod X δ-1 , ∀t ∈ [ν + 1], (21)
where the degree of each of Ω 0 (X), Ω 1 (X), . . . , Ω ν (X) is smaller than ε. Solving these ν + 1 Key Equations ( 21) jointly can be realized by multi-sequence shift-register synthesis and several efficient realizations exist [START_REF] Feng | A Generalized Euclidean Algorithm for Multisequence Shift-Register Synthesis[END_REF]- [START_REF] Zeh | Fast Multi-Sequence Shift-Register Synthesis with the Euclidean Algorithm[END_REF]. Solving [START_REF] Zeh | Fast Multi-Sequence Shift-Register Synthesis with the Euclidean Algorithm[END_REF] jointly is equivalent to solving the following heterogeneous system of equations:

     S 0 S 1 . . . S ν           Λ ε Λ ε-1 . . . Λ 1      =      T 0 T 1 . . . T ν      , (22)
where each (δ -1 -ε) × ε submatrix is a Hankel matrix:

S t = S t i+j j∈[ε] i∈[δ-1-ε] , ∀t ∈ [ν + 1], (23)
and each T t = (S t ε S t ε+1 . . . S t δ-2 ) T with:

S t i = ℓ-1 j=0 r j (α f +iz+t )v j , ∀i ∈ [δ -1], t ∈ [ν + 1].
Theorem 2 (Decoding up to New Bound). Let C be an ℓ-quasi-cyclic code and let the conditions of Thm. 1 hold. Let [START_REF] Hocquenghem | Codes Correcteurs d'Erreurs[END_REF] be fulfilled, let the ν + 1 syndrome polynomials S 0 (X), S 1 (X), . . . , S ν (X) be defined as in [START_REF] Feng | A Generalized Euclidean Algorithm for Multisequence Shift-Register Synthesis[END_REF], and let the set of burst errorsE = {j 0 , j 1 , . . . , j ε-1 } be as defined in [START_REF] Bose | On A Class of Error Correcting Binary Group Codes[END_REF]. Then, the syndrome matrix S = (S 0 S 1 . . . S ν ) T with the submatrices from (23) has rank(S) = ε.

Proof: Assume w.l.o.g. that f = 0. Similar to [20, Section VI], we can decompose the syndrome matrix into three matrices as follows:

S = (S 0 S 1 • • • S ν ) T = X • Y • X = (X 0 X 1 • • • X ν ) T • Y • X,
where X is a (ν + 1)(δ -1 -ε) × ε matrix over F q r and Y and X are ε × ε matrices over F q r . Explicitly the decomposition provides the following matrices:

X t = α (t+zi)j j∈E i∈[δ-2-ε] , t ∈ [ν + 1], X = α izj j∈[ε] i∈E , Y = diag(E i0 , E i1 , . . . , E iε-1 )
,

where E i def = ℓ-1 t=0 e i,t v t for all i ∈ E. Since Y is a diagonal matrix, it is non-singular. From gcd(m, z) = 1, we know that X is a Vandermonde matrix and has full rank. Hence, Y • X is a non-singular ε × ε matrix and therefore rank(S) = rank(X). In order to analyze the rank of X, we proceed similarly as in [START_REF] Feng | A Generalization of the Berlekamp-Massey Algorithm for Multisequence Shift-Register Synthesis with Applications to Decoding Cyclic Codes[END_REF]Sec. VI]. We use the matrix operation from [START_REF] Van Lint | On The Minimum Distance of Cyclic Codes[END_REF] to rewrite X = A * B, where

A = α ij j∈E i∈[ν+1]
and B = X 0 . We know from [START_REF] Van Lint | On The Minimum Distance of Cyclic Codes[END_REF] that, if rank(A) + rank(B) > ε, then rank(A * B) = ε. Since gcd(m, z) = 1, both matrices A and B are Vandermonde matrices with rank(A) = min{ν + 1, ε} and rank(B) = min{δ -1 -ε, ε}. Assume w.l.o.g. that (δ -1) > ν (else we can interchange the roles δ and ν in Thm. 1). Therefore, from [START_REF] Hocquenghem | Codes Correcteurs d'Erreurs[END_REF] we obtain ε ≤ (d * -1)/2 = (δ + ν -1)/2 < δ -1. Hence, investigating all four possible cases of rank(A) + rank(B) gives:

ν + 1 + δ -1 -ε ≥ 2ε -ε + 1 = ε + 1 > ε, ν + 1 + ε > ε, ε + δ -1 -ε = δ -1 > ε, ε + ε = 2ε > ε, Thus, rank(A) + rank(B) > ε.
Algorithm 1 summarizes the whole decoding procedure, where the complexity is dominated by the operation in Line 2. After the syndrome calculation (in Line 1 of Algorithm 1), the ν+1 Key Equations ( 21) are solved jointly (here in Line 2 with a Generalized Extended Euclidean Algorithm, GEEA [START_REF] Feng | A Generalized Euclidean Algorithm for Multisequence Shift-Register Synthesis[END_REF]). Various other algorithms for solving the Key Equations jointly as in Line 2 with sub-quadratic time complexity exist. Afterwards, the roots of Λ(X) as defined in [START_REF] Feng | A Generalization of the Berlekamp-Massey Algorithm for Multisequence Shift-Register Synthesis with Applications to Decoding Cyclic Codes[END_REF] correspond to the positions of the burst errors as defined in [START_REF] Bose | On A Class of Error Correcting Binary Group Codes[END_REF] (see Line 3).

The error values E i0 , E i0 , . . . E iε-1 can be obtained from one of the ν + 1 polynomials Ω j (X) as given from the Key Equations ( 21) (see Line 7 in Algorithm 1). In Line 8, each error value E ij ∈ F q r is mapped back to the ℓ error symbols e ij ,0 , e ij ,1 , . . . , e ij ,ℓ-1 ∈ F q and the codeword c(X) = (c 0 (X) c 1 (X) . . . c ℓ-1 (X)) can be reconstructed.

Algo 1: DECODING AN [m•ℓ, k, d] q QUASI-CYCLIC CODE Input: Parameters m, ℓ, k, q, r of the quasi-cyclic code Received word r(X) = (r 0 (X) . . . r ℓ-1 (X)) ∈ F q [X] ℓ Integers f, δ > 2, ν ≥ 0 and z > 0 with gcd(z, m) = 1 Eigenvalues λ i = α f +iz+j , ∀i ∈ [δ -1], j ∈ [ν + 1] Eigenvector (v 0 v 1 . . . v ℓ-1 ) ∈ F ℓ q r Output: Estimated codeword c(X) = (c 0 (X) c 1 (X) . . . c ℓ-1 (X))
or DECODING FAILURE 1 Calculate S 0 (X), S 1 (X), . . . , S ν (X) as in [START_REF] Feng | A Generalized Euclidean Algorithm for Multisequence Shift-Register Synthesis[END_REF] 2 Solving Key Equations jointly (Λ(X), Ω 0 (X), Ω 1 (X), . . . , Ω ν (X)) = GEEA X δ-1 , S 0 (X), S 1 (X), . . . , S ν (X)

3 Find all i: Λ(α -iz ) = 0 ⇒ E = {i 0 , i 8 Determine e ij ,0 , e ij ,1 , . . . , e ij ,ℓ-1 ∈ F q , s.t. r 0 (X) = e 0 (X) = 1 + X 32 , r 1 (X) = e 1 (X) = X 32 .

We have ε = 3, but ε = 2 (see [START_REF] Bose | On A Class of Error Correcting Binary Group Codes[END_REF]). The eigenvector v (5) = (1 α 4 + 1) ∈ F 2 2 6 is contained in the intersection of the eigenspaces ∩ i∈D V i , where D def = {0, 4, 8, 1, 5, 9}, and is used for decoding. The system of two equations as in [START_REF] Van Lint | On The Minimum Distance of Cyclic Codes[END_REF] becomes here:

α 35 α 26 α 45 α 33 Λ 2 Λ 1 = α 7 α 51 ,
and the corresponding error-locator polynomial is 2 i=0 Λ i X i = 1 + α 49 X + α 2 X 2 = (1 -X)(1 -Xα 128 ). The error-evaluation gives the two error values in F 2 6 : E 0 = 1 and E 32 = α 4 . Therefore we can reconstruct the ε = 3 error values e 0,0 = 1, e 32,0 = 1 and e 32,1 = 1 in F 2 .

V. CONCLUSION AND OUTLOOK

We proved a new lower bound on the minimum distance of quasi-cyclic codes based on the spectral analysis introduced by Semenov and Trifonov. Moreover, a syndrome-based decoding algorithm was developed and its correctness proven.

  Theorem 1, we can bound d to be at least δ + ν = 5, which is one less than the actual minimum distance for the [63 • 2, 100, 6] 2 2-quasi-cyclic code. The bound of Semenov-Trifonov gives d ≥ 4.

ℓ- 1 t=0 9 eExample 2 (

 192 e ij ,t v t = E ij , ∀i j ∈ E i (X) ← j∈Ei e j,i X j , ∀i ∈ [ℓ] 10 c i (X) ← r i (X) -e i (X), ∀i ∈ [ℓ]Decoding up to HT-like New Bound). Suppose the all-zero codeword of the [63 • 2, 100, 6] 2 2-quasi-cyclic code from Example 1 was transmitted. Let the two received polynomials in F 2 [X] be:

  1 , . . . , i ε-1 }

4 if ε < deg Λ(X) then 5 Declare DECODING FAILURE 6 else 7 Determine error values E i0 , E i1 , . . . , E iε-1 ∈ F q r

ACKNOWLEDGMENTS

This work was initiated when S. Ling was visiting the CS Department of the Technion. He thanks this institution for its hospitality.