Piecewise-affine maps:structural characteristics and nonlinear circuit applications

Abstract

ÖZET PARÇA PARÇA DO?RUSAL DÖNÜŞÜMLER: YAPISAL ÖZELLİKLERİ VE DO?RUSAL OLMAYAN DEVRE ANALİZİNE UYGULAMALARI Geçen otuz yıl boyunca, parça parça doğrusal (PPD) yaklaşım tekniği doğrusal olmayan devrelerin analiz ve sentezinde geniş bir kullanım alanı buldu. PPD bir dev re, doğrusal olmayan davranışlar gösteren fiziksel bir devreyi temsil etmede kullanılabilecek yaklaşık modeller den yalnızca biridir. Doğrusal analiz yöntemlerine olanak tanıması ve doğrusal olmayan devrelerde karşılaşılan problemlerin anlaşılmasında ve çözümünde iyi bir yol gösterici olması, PPD analizin geniş kullanım olanağı bulma sının iki ana nedenidir. PPD analize olan ilgi/ yakın geçmişte, büyük çapta devrelerin analizindeki gelişmelere bağlı olarak arttı. Yapılan çalışmalarda, PPD modellerin, yapılan hatayı kabul edilebilir sınırlar içerisinde tutarak gerekli bilgi sayar zamanını azaltabilmeyi sağladıklarından, büyük çap ta sistemler için özellikle elverişli olduğu gösterildi. 1950'lerin sonlarından beri, PPD devreler çeşitli yönleri ile araştırıldı ve elde edilen sonuçlara bağlı olarak bir dizi yöntem geliştirildi. Varolan bütün yön temler kısmen veya tamamen devrelerin PPD yapısının incelenmesi ve gözlenen özelliklerin yöntemde kullanılması yolu ile elde edilmişlerdir. Devre için PPD bir model seçildikten sonra, analizde karşılaşılacak problemleri çözmede kullanılacak en iyi yöntem modelin PPD yapısından en iyi şekilde yararlanan yöntemdir. Bu yüzden, yetkin yön temlere ulaşmak için, PPD devrelerin özelliklerinin derinlemesine ve doğru bir şekilde anlaşılması büyük önem kazanmaktadır. PPD devrelerin nitel ve nicel özellikleri PPD dönüşümlerin matematiksel yapısına çok sıkı bağlı olduğundan PPD dönüşümlerin yapısal özelliklerinin ayrıntılı bir şekilde incelenmesi gerekli olmaktadır. PPD devre analizinde yoğun olarak ilgilenilen üç temel problem cebrik ve dinamik devrelerin çözümlerinin bulunması, giriş ve geçiş bağıntılarının elde edilmesi ve büyük çapta devrelerin modellenmesi ve simülasyonu olarak verilebilir, Belirtilen problemlerin çözümü için birçok yöntem geliştirilmiş olmasına rağmen, özellikle büyük çapta devreler için, zaman ve bellek gereksinimlerini azaltacak yetkin yöntemlerin geliştirilmesi sürekli büyü yen bir ilgi alanı oluşturmaktadır. Herhangi bir yöntem de çözüm süresince harcanan zamanı azaltmak, yakınsama vııhızı yüksek ve iterasyon adımlarında gerekli olan işlem zamanı az olan algoritmalar geliştirmekle mümkündür. Diğer bir yandan, PPD bir devreyi en az bellek kullanımı ile tanımlayabilmek için PPD devre denklemlerinin, tüm tanım bölgesinde geçerli, analitik gösterilimlerinin elde edilmesi gerekmektedir. Bu tezde, PPD devrelerin yapısal bir analizi, tüm çözümlerinin bulunması için yeni bir yöntem ve oldukça geniş bir sınıfı için kanonik gösterilimler geliştirilmiştir. Devrelerin yapısal analizi PPD dönüşümlerin matematiksel yapısının araştırılması temelinde yürütülmüş tür. Bu araştırma ile, PPD devrelerin yapısına ilişkin özelliklerin derinlemesine anlaşılmasına ve böylece yet kin yöntemler elde edilmesine yönelik matematiksel bir taban oluşturulmuştur. Elde edilen sonuçlardan, bütün çözümlerin bulunması için önerilen yöntemin ve yeni kanonik gösterilimin geliştirilmesinde yararlanılmıştır. Önerilen çözüm yöntemi, PPD dönüşümlerin bölgeler içinde doğrusal ve her bir bölgenin de içbükey olma özelliklerinin kullanılması ile geliştirilmiştir. Verilen kanonik gösterilimin elde edilmesinde ise PPD bir bölmeleme üze rinde tanımlı sürekli dönüşümlere ilişkin Jacobian mat risler arasındaki sıkı ilişki kullanılmıştır. PPD dönüşümlerin incelenmesine bir giriş olarak, Bölüm 2' de doğrusal bölmelenmiş bir tanım bölgesinin üç önemli büyüklüğü; bölgeler, köşe-noktaları ve temel-ışınlar araştırılmış ve bölmelemelerde karşılaşılan uyumsuz durumlar incelenmiştir. Doğrusal bir bölmelemeye ilişkin bölgelerin belirlenmesi ve bu bölgelerin sayısını veren bir formül geliştirilmesi cebrik bir yaklaşımla ele alınmıştır. Geliştirilen cebrik yöntem yalnızca PPD devre kuramında değil aynı zamanda hesapsal-geometri ve kombi- natoryal-geometri dallarında da kullanılabilir. îçbükey- küme kur anandaki ayıran-düzlem teoreminin bir uygulaması olarak, bölgeleri tanımlayan doğrusal eşitsizliklerin uyumlu olup olmadığı ve böylece boş olmayan bölgelerin belirlenmesi problemi açı şartını sağlayan en az bir te mel çözüm içeren çeyreklerin bulunması problemine dönüştürüldü {Teorem 2.1-3), Bunun bir sonucu olarak, yukarı da belirtilen özelliklere sahip çeyrekleri belirten tam sayı kümelerinin sayılması yolu ile doğrusal bir bölmelemedeki bölge sayısını veren bir bağıntı elde edilmiştir (Teorem 2.4), Verilen bağıntı uyumsuz durumları da içeren herhangi bir doğrusal bölmeleme için geçerli olduğun dan PPD analize olduğu kadar kombinatoryal-geometri'ye de bir katkı oluşturur. Matematiksel programlama dalında, bir çok-yüzlünün tüm köşe-noktaları ve temel-ışınlarının bulunmasında kullanılagelen yöntemlerin dayandığı temel fikirler, burada çok-yüzlülerin özel bir topluluğu olan doğrusal bölmelemeye genelleştirilmiştir (Teorem 2.5-6). Elde edilen sonuçlar, bütün çözümleri bulmak için geliştirilen yöntemde, bölmelemeye ilişkin büyüklüklerin bulunmasına ilk adım olarak gerekli olduğundan, kullanılmaktadır. En genel bölmelemeye ilişkin bölge, köşe-noktası ve temel-ışınları belirlemek için verilen genel viiialgoritmalar yerine, özel bölmelemeler ele alınarak daha hızlı algoritmalar türetilebilir. Kafes bölmeleme için verilen sonuçlar böyle uygulamalara bir örnek oluşturmaktadır (özellik 3.10-11). Doğrusal bölmeleme üzerine yapılan bu tartışma doğrusal olmayan daha genel bölmeleme durumlarına da genişletilebilir. Fakat, PPD bölmeleme durumunda bile bölgeleri tanımlayan eşitsizlik sistemleri bölgeden bölgeye önemli bir değişime uğradıklarından doğrusal bölmeleme için verilen yöntemde birçok değişiklik yapılması gerekmektedir. Ayrıca, öngörülebilir ki rastgele PPD bölmelemelerde bir bölge için gerekli işlem sayısı doğrusal bir bölmelemenin tamamı için gerekli işlem sayısı kadar olur. Bölüm 3'te, PPD dönüşümlerin matematiksel yapısının araştırılmasına, gösterilim, tanım-değer bölgesi iliş kileri ve işlemsel özellikleri açılarından incelenmesi ile devam edildi. PPD dönüşümlerin bilinen dört gösterilimi zaman ve bellek gereksinimleri açısından karşılaştırıldı. Bu inceleme, farklı gösterilimlere dayalı olarak geliştirilmiş yöntemlerin etkinliklerinin karşılaştırılması olanağını verir. Bu bölümde, ayrıca, PPD dönüşümlerin, bugüne kadar yapılan araştırmalarda tam olarak yararlanılmayan, bölgeler ve onların görüntülerinin içbükey olması özelliği kullanılarak yeni bir gösterilim geliştirilmiştir (Teorem 3.1). îçbükey-küme kuramına dayalı bu gösterilim simpleks gösterilimin en genel bölmeleme durumuna bir genellemesi olarak düşünülebilir. Geliştirilen gösterilim, PPD dönüşümleri belirli bir bölgede tanımlamada kullanılan doğrusal bir dönüşüm ve eşitsizlik siste mini negatif-olmayan değişkenlerin doğrusal bir dönüşümü ne çevirme olanağını verir. Böylece, Bölüm 5'te verilen yöntemde olduğu gibi, geliştirilecek yeni yöntemlere el verişli bir matematiksel taban sağlar. Diğer yandan, PPD dönüşümlerin sürekli olmayanlarını da içeren çok geniş bir kümesi bu gösterilim ile verilebilir. Bu ise diğer gösterilimlere dayanan bir analizde karşılaşılan bir problemi çözüme daha uygun olabilecek eşdeğer bir probleme dönüştürme olanağını verir. PPD dönüşümlerin matematik sel yapısının araştırılması, PPD dönüşümler altında görüntü bölgelerinin özellikleri, PPD dönüşümlerin ters ve bireşimlerinin yapısı incelenerek tamamlanmıştır. Elde edilen sonuçlar kuramsal incelemeler için olduğu kadar uygu lamaya yönelik çalışmalar için de yararlı bir matematik sel taban oluşturur. Bu inceleme PPD direnç devrelerinin yapısını anlamaya yeterli olmasına rağmen, dinamik devreler için daha fazla araştırma yapılması gerekmektedir. Bölüm 4'te, Chua ve Kang tarafından önerilen kanonik gösterilim incelenmiş ve PPD devre kuramında karşılaşılan PPD dönüşümlerin oldukça geniş bir sınıfı için yeterli olan daha genel yeni bir kanonik gösterilim geliştirilmiştir, Kanonik gösterilimlerin varlık koşulları ıxüzerine [1893 fal>da elde edilen sonuçlar düzeltilmiştir {Teorem 4.1-4F, Varlık koşullarının incelenmesine ek olarak, kanonik gösterilimlerin katsayılarının elde edilmesi (özellik 4,1), doğrusal veya PPD dönüşümler altında kapalı kalıp kalmadıkları (özellik 4,2-3) araştırılmış ve PPD bağıntıların kanonik bir gösterilimi elde edilmiştir. Geliştirilen gösterilimler Bölüm 6'da; PPD devrelerin devre denklemleri, giriş ve geçiş bağıntıları ve durum denklemlerinin en az bellek gereksinimi ile tanımlanmasını sağlayan analitik gösterilimlerin elde edilmesinde kullanılmıştır. Bölüm 5'te, PPD devrelerin bütün çözümlerini bulan bir yöntem geliştirilmiştir, Bölüm 3'te elde edilen iç- bükey-küme kuramsal gösterilim kullanılarak, PPD bir denklemin herhangi bir bölgede çözümünün bulunması problemi doğrusal homojen bir denklemin negatif olmayan çözümlerinin aranması problemine dönüştürülmüştür (Teorem 5,1). Böylece, çözüm bulunduran bölgelerin büyük bir çoğunluğunu, herbir bölge için doğrusal bir denklem çözmek yerine, sadece işaret testleri ile belirleme olanağı doğmaktadır, îşaret testi denklem çözmek için gerekli olana göre oldukça az bir çaba gerektirdiğinden, Önerilen yöntem, uygulamada birçok üstünlüğü ile birlikte bu alandaki en etkin yöntemlerden biri olarak gözükmektedir. Kafes bölmeleme gibi, uygulamada karşılaşılabilecek özel bölmeleme biçimleri için geliştirilen yönteme bağlı olarak daha hızlı algoritmalar türetilebilir. PPD dönüşümler üzerine tersi alınabilir, kesin artan gibi kısıtlamalar konulması hızlı bir bölge eleme yolu sağlar, Böylece, verilen yöntem tek çözümü olan devrelere uygulanırsa hızlı algoritmalar elde edilebilir. Yöntem, herhangi sayıda denklem ve değişken içeren PPD denklemlere uygulanabildiğinden, giriş ve geçiş bağıntılarını belirlemede de kullanılabilir. Bölüm 6'da, PPD devre denklemlerinin matematiksel yapısı araştırılmış ve devre denklemleri, giriş ve geçiş bağıntıları ve durum denklemlerinin kanonik biçimdeki analitik gösterilimleri elde edilmiştir. PPD dönüşümler için Bölüm 3'te elde edilen sonuçlar kullanılarak, PPD ve sürekli elemanlardan oluşmuş herhangi bir devrenin dev re denklemlerinin (Teorem 6.1), giriş ve geçiş bağıntılarının (Teorem 6.3) ve durum denklemlerinin (Teorem 6.5) herzaman PPD ve sürekli olacağı gösterilmiştir. PPD dev reler için burada verilen analitik gösterilimler Bölüm 4' te geliştirilen yeni kanonik gösterilime dayanmaktadır. (^f) Bu tez yazım aşamasında iken yayınlanan bir çalışmada [190], burada ve [189] 'da verilenlere benzer bir gerek ve/veya yeter koşul takımı verilmiştir. Ancak, bu tezde verilen yeter koşul [190] `da verilenden daha zayıf bir koşuldur.Chua ve Kang tarafxndan önerilen kanonik gösterilim PPD devrelerin oldukça geniş bir sınıfının devre denklemlerini temsil etmek için yeterli olmasına rağmen, daha genel olan bu yeni gösterilime özellikle giriş ve geçiş bağıntıları (Teorem 6.4) ve durum denklemleri için kuvvetli bir gereksinim vardır. Önerilen kanonik göster ilimler, elemanlara ilişkin kanonik gösterilimlerin katsayıları üzerine doğrusal cebrik işlemler uygulanarak elde edile bilir. Bu yüzden, sadece PPD devreler üzerine kuramsal incelemelere değil aynı zamanda uygulamaya yönelik çalışmalara da yararlı olacaktır.

ABSTRACT A structural and in depth analysis of piecewise- affine (PWA) circuits has been carried-out; a new method for finding multiple solutions of PWA resistive circuits and a new canonical representation for a rather general class of PWA circuits have been developed. The structural analysis relies heavily on the in vestigation of the mathematical structure of PWA map. The emphasis in the investigation has been on the charac teristics such as non-empty regions, vertices, extreme- rays of domain and range spaces, kinds of characteriza tions and functional properties of PWA mappings. The method capable of finding all solutions uses the newly developed representation which is based on convex- set theory. The main idea in the determination of the regions having a solution is to use the sign- tests rather than solving an affine equation in each region. The proposed canonical representation of PWA mapps extends the one on linear partition given by Chua-Kang to maps defined on PWA partitions. Therefore, compact glo bal analytic forms of circuit equations, driving-point, transfer characteristics and state equations of a rather general class of PWA circuits have been developed. vi