FR 2184106 A1 19731221 FR 7317167 A 19730511 Cette invention concerne la production d'informations pour l'étude de circuits électriques et électroniques dans laquelle l'information relative au tra cé du circuit est effectuée automatiquement. Elle vise à surmonter quelques uns des inconvénients des systèmes antérieurs et comprend de nouveaux algorithmes pour la position des composants et le passage des connexions. Une solution classique au problème du tracé automatique a été de considérer l'étude de l'emplacement et celle des connexions comme deux fonctions séparées. Cette méthode peut être bonne lorsqu'elle est appliquée à une carte à circuit imprimé à deux faces, comprenant un réseau régulier de composants. Cependant, les tentatives d'application de cette solution aux circuits imprimés à une seule face et à des composants de forme et de taille quelconques n'ont pas été heureuses. Le type de circuit auquel cette invention se rapporte sont les circuits imprimés à une seule face et les circuits intégrés. Une raison à ce manque de succès réside dans l'absence de relation entre la position des composants et le passage des connexions. Une fois que la position a été déterminée,à partir de quelques considérations telles que la longueur des fils, l'entrée du programme de trace est déterminéeet la position ne peut être facilement modifiée pour tenir compte des exigences réelles imposées aux connexions. Cette invention cherche à obtenir un système dans lequel il peut exister une relation entre la position des composants et les passages des connexions. Selon l'invention, il est prévu un procédé de commande d'un calaulateur pour qu'il fournisse les informations nécessaires au montage d'éléments de circuits électriques et à leur interconnexion dans lequel a) les éléments de circuits sont traités les uns à la suite des autres,l'emplacement de chaque élément de circuit est déterminé, les connexions aux bornes de cet élément sont ensuite déterminées, b) après que chaque élément de circuit a été placé et une ou plusieurs connexions entre bornes définies, le calculateur programmé détermine les zones restées libres et disponibles pour l'emplacement des éléments de circuit et le passage des connexions, c) les zones libres sont déterminées d'après des critères choisis à l'avance parmi lesquels se trouve celui de la distance minimum permise entre deux connexions adjacentes, d) les données stockées dans la mémoire du calculateur comprennent - la taille et la forme de l'élément de montage et la position et les carac téristiques des connecteurs et autres moyens d'accès à l'élément de montage, - l'emplacement et la taille de chaque élément de circuit dont la position a été déterminée, - l'emplacement et le passage de quelques unes des connexions qui y sont associées, laquelle information est complétée au fur et à mesure que le programme se déroule, e) pour chaque élément de circuit, le calculateur programmé détermine à partir des informations dans sa mémoire relatives aux zones restées libres et à partir des caractéristiques de cet élément de circuitX un emplacement convenable, en se basant sur les critères choisis, f) chaque passage entre éléments à adopter pour une connexion est déterminé par une opération effectuée par le calculateur dans laquelle une simulation est faite de la propagation d'un front d'onde débutant à une extrémité d'une connexion et parcourant les zones restées libres, en direction de l'autre extrémitéjet g) les informations ainsi obtenues qui représentent les données de montage pour les éléments sont envoyées à un dispositif de sortie. Les objets et caractéristiques de la présente invention apparaîtront plus clairement à la lecture de la description suivante d'exemples de réalisation, ladite description étant faite en relation avec les dessins ci-annexés dans lesquels La figure 1 est un organigramme relatif à l'emplacement des composants. La figure 2 concerne la définition des limites. La figure 3 concerne l'emplacement des composants La figure 4 concerne le tracé des connexion. La figure 5 est un schéma de circuit auquel l'invention a été appliquée La figure 6 montre le tracé termine. La position de chaque composant est tracé en premier, puis le passage des connexions entre bornes. A cela correspond l'organigramme de la figure 1 qui montre que la position d'un composant donné peut tenir compte des passage trouvés antérieurement auxquels ce composant doit être connecté, ainsi que de sa position parmi les autres composants déjà placés. Un aspect très important des programmes de tracé réside dans la forme que les données de tracé prennent au sein du programme. Une forme de structure de données inadéquate affecte à la fois la vitesse du programme et la taille. L'objectif ici a été de rendre la représentation du tracé aussi compacte que possible, tout en conservant les relations essentielles. La représentation adoptée repose sur la définition des zones libres et le passage des connexions. Ceci sera décrit ultérieurement en se rapportant en particulier à la représentation de la configuration des connexions. La figure 2 montre une telle configuration de limites et de lignes en pointillé entourant les zones qui sont encore disponibles pour d'autres passages de fils. Elle montre des connexions telles que 1,2,3 chacune bordée par deux lignes en pointillé, les zones qui restent entre les lignes en pointillé et ne contiennent oas de lignes représentent des connexions restant utilisables. Sont aussi représentés des îlots tels que 4 et 5 dus aux connexions ou bornes qui sont suffisament éloignées des autres connexions pour permettre m tracé les contournant. les limites définissant ces zones sont placées à une faible distance de cloaque côté des lignes centrales. Celle-ci représente la moitié de la distance entre les lignes centrales de deur connexions adjacentes. lorsque des connexions supplémentaires sont tracées elles doivent se trouver à une distance similaire à l'intérieur de cette limite. La structure des données représentant ces limites de calage est idéalisée sous forme d'un anneau reliant les points de référence figurés sur les limites. Chaque poirt est stocké dans une mémoirede calculateur au moyen de ses coordonnés, et chaque segment de limite est référencé par le nor bre de connexions à partir desquelles il est obtenu. La structure en anneau est utilisée pour associer les diverses nones formées et aussi pour associer des îlots aux limites extérieures des zones à l'intérieur desquelles ces îlots se trouvent. Une stru c ture tres proche est utilisée pour la description des zones disponibles pour le placentt. L'entrée dans le- programa décrivant l'élément à caler est définie en utilisant ces limites. Les zones pour tracer les connexions et la position des composants sont définies séparément et peuvent avoir une forme quelconque. Ayant choisi cette représentation des données,les algorithmes pour le tracé des connexions et l'etplacesent des composants doivent être définis. L'ordre dans lequel les composants sont choisis pour l'emplacement sur le support est déterminé de manière à garder une longueur de connexion aussi faible que possible. Un poids est obtenu pour chaque connexion, égal au nombre de bornes des composants non placés lui appartenant. Ainsi, pour chaque composant, les valeurs n1, égales au poids total de connexions à ses bornes, et n2, égales au nombre de ses bornes pour lesquelles des connexions existent déjà,sont trouvées. lie composant placé à la suite est celui qui présente la valeur la plus faible de n1/n2. Ceci signifie que les composants à connecter à des connexions existantes qui sont presque réalisées doivent être choisis ensuite. La première partie de l'algorithme qui est utilisé conduit à une position et à une orientation idéalisées pour le composant déterminé. Uneposition idéalisée est obtenue en représentant la connexion à laquelle chacune de ses bornes appartient par un seul point. Le point de connexion est le centre de gravité de toutes les parties des limites du calage appartenant à cette connexion. La position idéalisée est à son tour le centre de gravité des points de connexion pour chacune de ses bornes. Le composant est essayé dans les quatre orientations possibles avec son centre dans la position idéalisée. L'orientation donnant la distance totale la plus faible entre chaque borne et son point de connexion correspondant est choisie. L'algorithme suivant trouve l'emplacement le plus proche de la position idéalisée pour laquelle la forme du composant s'adaptera au tracé dans l'orien- tation trouvée et de manière que des passages puissent etre trouvés vers ses bornes. Ceci impose d'établir des limites pour la définit-ion de ces critères. Les limites qui définissent l'emplacement d'un composant sont obtenues en traçant sur celui-ci un point de référence lorsqu'il est déplacé à l'intérieur des limites de déplacement. Les limites de câblage, qui sont référencées au moyen du numéro de fil d'une bor e, définissent la zone à l'intérieur de laquelle il doit se trouver pour qu'un passage puisse l'atteindre. Les limites tracées par le point de référence sont trouvées de façon que chaque borne se trouve à l'intérieur d'une limite o ù un passage peut etre trouve. Une position est trouvée pour le point de référence qui se trouve à l'intérieur de toutes ces limites et pour lequel le centre du composant est situé le plus près de la position idéalisée. Si aucune position semblable ne peut être trouvée une autre orientation peut être essayée. L'algorithme décrit ci-dessus est illustré à la figure 3A, dans laquelle il existe deux limites de câblage 6 et 7 ; chacune d'elle définit une zone à l'intérieur de laquelle une connexion vers un composant doit se trouver. Le rectangle 8 est la frontière de la zone à l'intérieur de laquelle ce composant peut etre placé. Ce composant, tel qu'il est figuré séparémént en 9,possède des bornesà cha son que extrémité indiques par des croix et/coin gauche inférieur 10 constitue son point de référence. Comme il est indiqué en lignes brisées en 11, le composant est mis à une place convenable à l'intérieur du rectangle 8, pour laquelle les connexions à A et B sont les plus courtes. La figure 3B représente un diagramme dans lequel les limites constituées par les rectangles 12, 13, 14 définissent les critèes de-position et de passage par rapport au point 15, qui représente un point de référence de composant. Une fois que la position réelle du composant a été trouvée,les les bornes sont fixées en position de manière que des passages vers elles puissent être trouvés. La recherche de passages est effectuée par simulation d'un front d'onde en propagation (figure 4). Tous les points du front d'onde sont équidistant du point de départ. Lorsque les passages sont seulement parallèles aux axes x et y, cela donne naissance à des coupures du front d'onde suivant un angle de 45 par rapport aux axes. Chaque nouvel essai de recherche déplace le front d'onde en entier de façon à rencontrer l'obstacle suivant. Sur la figure 4, le front d'onde est diffracté, divisé ou éliminé dans les coins lorsqu'il continue à se propager. La recherche s'arrête lorsqu'une partie quelconque du front d'onde atteint une sec tion de la limite référencée au moyen du numéro de connexion du passage trouvé. Les extrémités des fronts d'ondes sont à une faible distance à l'intérieur de la limite qui représente la distance de la ligne centrale du passage trouvé vers le milieu de la zone libre entre deux passages adjacents ; le fait de changer cette distance permet le passage à des connexions de différentes largeurs. La route réelle est trouvée en traçant en retour à travers les centres de front d'ondes les coordonnées lesquelles sont stockées dans la mémoire du calculateur lorsque le front d'onde se propage. Ces centres apparaissent lorsque le front d'onde atteint les coins, et sont mis en position pour chaque section du front d'onde de façon qutil semble se propager directement à partir d'eux. Les centres définis par les fronts d'onde à la figure 4 (a) sont représentés à la figure 4 (b). Ceci montre aussi que le passage qui est trouvé résulte du tracé des centres en retour. Une fois que les passages ont été trouvés, les coordonnées qui définissent les limites du câblage et de l'emplacement dans la mémoire sont modifiées de façon à être pretes à l'apport d'un nouveau composant. La sortie du programme suivant lequel ceci se passe est produite sur l'imprimante, en indiquant l'ordre dans lequel les composants sont placés, leurs positions et leurs orientations ainsi que les coordonnées des passages trouvés. Un dessin du tracé est aussi effectuéJlorsque le programme se déroule, sur un écran de visualisation à mémoire. Celui-ci montre les contours et les bornes des composants et les passages trouvés. Les informations pour reproduire ce dessin sont aussi fournies en données numériques. Si le programme ne trouve pas une position pour un composant qui satisfera les différentes critères, un message est établit par4calculateur-pour indiquer oW le problème slest posé et le programme s'arrête. Des modifications peuvent être apportées par un opérateur de façon que le programme continue. Les changements peuvent être faits de deux manières. D'une part, les positions et les orientations des composants peuvent être déterminées manuellement. D'autre part, des fils de liaison peuvent être ajoutés à n'importe quelle connexion du tracé demandé. Le programme continue ensuite à partir de ces changements manuels. La figure 5 montre un schéma de circuit, dont tous les noeuds et les composants ont été numéroté5 Une liste des types de composants est faite donnant la taille du composant et la position des bornes. Une liste des composants dans le circuit est ensuite formée, donnant pour chaque composant son numéro et son type et le nombre de connexions à chaque bornes. Puis l'opération algorithme ci-dessus produit un tracé final représenté à la figure 5, dans lequel chacun des composants est numéroté comme indiqué sur le sché ma du circuit. Leurs formes rectangulaires sont placées les unes à côté des autres, les croix représentant les positions des bornes à l'intérieur des composants. Les lignes reliant les croix et la partie inférieuredu tracé représentent les passages trouvés. Ce tracé a demandé une intervention manuelle à deux moments. La première fois après que 16 des 26 composants aient été placés. Les positions de quatre composants restant ont été modifiées. La seconde fois au vingt et unième composant, lorsque le fil de jonction (marqué J) a été ajouté. Le programme continue alors jusqu'a son achèvement. Le temps total pris pour le tracé a été de quinze minutes. Une autre application de ces techniques peut être faite aux supports pour circuits imprimés à double face sur lesquels sont montés des composants classiques. Ceci apporte plus de place pour le calage par rapport à la place occupée par les composants qui sont groupés sur le tracé représenté. Dans cet exemple, les problèmes ont été posés en partie par le manque de place du câblage. L'application proposée pour les tracés à deux couches est de considérer les deux couches comme étant entièrement séparées. Initialementa les connexions sont toutes placées sur une couche jusqu a ce qu'une connexion ne puisse pas être ajoutée. Cette connexion est alors placée sur la deuxième couche. Il serait avantageux probablement d'essayer des connexions sur la seconde couche qui deviennent plus longues sur la première couche que deux fois la distance entre les points à réunir, pour éviter le plus tât possible l'encombrement de la première couche. Le peu d'interventions manuelles pour le circuit représenté suggère que le tracé peut probablement être effectué de ma nière complètement automatique sur les deux couches.Pour des circuits plus importants d'autres dispositions seraient probablement nécessaires pour que les connexions qui ne peuvent être placées sur une couche seulement utilisent les deux couches Les méthodes décrites pour les circuits imprimés à deux faces apportent une solution raisonnable en ce qui concerne la construction des supports. La plupart des connexions se trouvent du côté opposé à celui sur lequel les composants sont montés, pour une soudure directe des composants. Un nombre plus restreint de connexions retrouvent sur le deuxième côté avec des connexions vers le premier côté étant seulement aux bornes des composants (quelques trous de montage peuvent être métallisés). montrent Les techniques décrites ici / qu'une simple étude au tracé automatique peut conduire à des résultats acceptables. L'invention apportent solution du point de vue du prix et de la qualité. Les algorithmes utilisés apportent une souplesse à l'étude des circuits de forme et taille quelconques, de composants divers et dont les connexions présentent des largeurs et des espacements variables. L'invention a aussi été appliquée avec succès à l'étude du tracé des cir cuits intégrés bipolaires, dans lequel les problèmes de tracé sont similaires à ceux des circuits à une seule face. Il est clair que la description précédente d'exemples particuliers de l'invention est faite à titre d'exemple seulement et ne pas être considérée comme une limitation de sa portée. REYENDICATIONS 1. Procédé de commande d'un calculateur pour que ce dernier fournisse les informations nécesssires au montage d'éléments pour circuits électriques sur un support et aux interconnexions de tels éléments, caractérisé en co que - les éléments de circuits sont traités les uns après les autres et l'emplacement de chaque élément de circuit est détermine, les connexions aux bornes de cet élément sont ensuite déterminées - après que chaque élément de circuit a été placé et une ou plusieurs connexions à ses bornes ont été définies, le calculateur programmé détermine les zones restées libres et disponibles pour ltemplacement d'éléments de circuit et le passage des connexions;; - les zones libres sont déterminées d'après des critères fixés å l'avance parmi lesquels se trouve celui de la distance minimum permise entre deux connections adjacentes ; - les données stockées dans la mémoire du calculateur comprennent - la taille et la forme du support ; - l'emplacement et les caractéristiques des connecteurs et-les autres moyens d'accès au support ; - l'emplacement et la taille de chaque élément de circuit dont l'emplacement a été déterminé - l'emplacement et le passage de quelques unes des connexions qui y sont associées, laquelle information est complétée au fur et à mesure que le programme se déroule. - pour chaque élément de circuit le calculateur programmé détermine à à partir des informations relatives aux zones libres, stockées dans sa mémoirejet 9 partir des caractéristiques de cet élément et en prenant en considération des critères choisis à l'avance) la distance minimum permise entre deux connexions adjacentes et entre éléments de circuit - chaque passage à adopter entre éléments pour une connexion est déterminé par une opération pour laquelle une simulation est faite d'un front d'onde débutant à une extrémité d'une connexion et parcourant les zones restées libres en direction de l'autre extrémité de cette connexion ; - et en ce que, l'information ainsi obtenue, qui représente les données de montage pour l'élément de circuit est délivrée à un dispositif de sortie. 2. Procédé selon la revendication 1, caractérisé en ce que lorsque la suite d'opérations programmées ne peut trouver un passage pour une connexion ou un emplacement possible pour l'élément de circuits, le programme s'arrête ét le calculateur émet un signal de manière qu'une intervention manuelle puisse être effectuée. 3. Procédé selon la revendication 1, caractérisé en ce que le support est une carte à circuits imprimés. 4. Procédé selon la revendication 1, caractérisé en ce que le support est un substrat sur lequel un semi-conducteur intégré doit etre fabriqué 5. Circuit imprimé, caractérisé en ce qu'il est obtenu par la mise en oeuvre du procédé selon la revendication 3. 6. Circuit imprimé, caractérisé en ce qu'il est obtenu par la mise en oeuvre du procédé selon la revendication 4.