Abstract FR:

Les masques a decalage de phase (mdp) dits alternes introduits par marc levenson au debut des annees 80 ont rapidement montre des performances lithographiques spectaculaires. Aujourd'hui, quinze ans apres, cette technique n'est toujours pas utilisee pour la production de masse des circuits integres car son industrialisation comporte plusieurs difficultes. La fabrication des mdp alternes est couteuse et complexe. La generation des motifs alternes doit aussi etre automatisee. Il s'agit d'un probleme informatique complexe encore mal connu pour lequel cette these propose une nouvelle approche geometrique. Dans un premier temps, on construit un cadre theorique pour la generation des motifs alternes autour de la theorie des graphes et de la geometrie algorithmique. Quatre formulations sont donnees en fonction du contexte de la generation des motifs. La formulation 1 qui est la plus simple peut etre solutionnee en temps quasi-lineaire. Les formulaires 2, 3 et 4 sont plus complexes. Cette these propose pour la premiere fois des algorithmes en temps sub-quadratiques pour ces formulations. La formulation 2 est ainsi solutionnee en temps quasi-lineaire. Les formulations 3 et 4 quant a elles sont unifiees par le meme modele : le probleme du postier chinois planaire. En utilisant l'algorithme de barahona, on obtient alors une solution en temps en o (n 3 / 2 log n). Une telle complexite permet des applications aux circuits integres. Afin de valider notre approche theorique, nous avons construit un logiciel de generation des motifs alternes appele psmgen. Autour de ce programme informatique, nous avons developpe une methodologie d'application qui a ete utilisee avec succes sur plusieurs dizaines de circuits integres. Cette methodologie tire partie de la hierarchie des circuits afin de gerer leur complexite. Elle s'applique aux circuits apres leur conception. La situation actuelle d'introduction de la technique ne permet pas de prendre en compte les mdp alternes des la conception. Dans l'avenir, la situation ideal consiste a integrer la generation des motifs alternes au processus de conception des circuits integres. Au total, cette these propose a la fois une comprehension theorique et des outils industriels pour la generation des motifs alternes. Elle montre finalement que la generation des motifs ne doit pas etre un obstacle a l'industrialisation de la technique alternee.