[發明專利]版圖二劃分方法

有效

• 申請號: 201110328029.9
• 申請日: 2011-10-25
• 公開（公告）號: CN102521425A
• 公開（公告）日: 2012-06-27
• 發明（設計）人: 蔡懿慈;姚海龍;鄧超
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 北京中偉智信專利商標代理事務所 11325
• 代理人: 張岱

1.一種版圖二劃分方法，其特征在于：將版圖中圖形間距小于最小光刻距離的圖形劃分成為兩個子版圖，通過兩次光刻刻蝕得到版圖圖形；當分成為兩個子版圖后所述子版圖中圖形間距仍小于最小光刻距離時，將版圖中圖形分割成至少兩個子圖形，以所述子圖形為單位將間距小于最小光刻距離的子圖形劃分為兩個子版圖，通過兩次光刻刻蝕在基片上得到版圖圖形；將無法用分割的方法得到子版圖的版圖區域進行標注。

2.根據權利要求1所述的版圖二劃分方法，其特征在于，所述方法包括下述步驟：

將版圖中的多邊形和矩形信息存入OpenAccess平臺的數據結構中；

將存貯的多邊形按序劃分得到至少一個矩形；

計算兩矩形間的間距值，當所述間距值小于最小光刻距離時判定所述兩矩形所在多邊形存在沖突關系，形成沖突圖；

在存在沖突關系的多邊形上通過幾何計算得到切割保護層信息，所述切割保護層是所述多邊形邊緣上所有與其它多邊形間距離小于最小光刻距離的點的集合；

將所述沖突圖劃分成為多個沖突子圖；

在多邊形上確定切割位置；

沿所述切割位置形成分割邊；

在所述沖突圖中確定無法分割的區域，并標注；

生成翻轉圖；

通過對所述翻轉圖的計算得到劃分結果。

3.根據權利要求2所述的版圖二劃分方法，其特征在于：所述多邊形劃分得到至少一個矩形所按的順序為逆時針順序或順時針順序。

4.根據權利要求2所述的版圖二劃分方法，其特征在于：沖突圖通過廣度優先搜索算法劃分成為多個沖突子圖。

5.根據權利要求4所述的版圖二劃分方法，其特征在于，沖突子圖的劃分步驟包括：任選沖突圖中一個圖形形成沖突子圖，通過廣度優先搜索算法將由沖突邊連接起來的圖形加入到所述沖突子圖中，當所述沖突子圖中的所有圖形與所述沖突子圖外的圖形之間沒有沖突關系時沖突子圖形成完畢。

6.根據權利要求2所述的版圖二劃分方法，其特征在于，在多邊形上確定切割位置的條件包括：所述切割位置不能穿過所述切割保護層；以及所述切割位置處的重疊長度不小于最小光刻距離，所述重疊長度是指被切割生成的新矩形在不引入新的沖突邊的情況下可向外延伸的最大長度。

7.根據權利要求2所述的版圖二劃分方法，其特征在于：生成翻轉圖的依據是翻轉增益，所述翻轉增益為節點集合內部圖形顏色翻轉后與翻轉前的實際切割點數目的差值。

8.根據權利要求2所述的版圖二劃分方法，其特征在于：由所述翻轉圖得到劃分結果的計算方法是整數線性規劃方法，

目標函數(最大化)：max∑a_i，j

其中，約束條件為：

如果fg_i，j≥0，約束條件為

a_i，j≤fg_i，j(2-x_i-x_j)

a_i，j≤fg_i，j(x_i+x_j)

a_i，j∈{0，1}

如果fg_i，j＜0，約束條件為

a_i，j≤fg_i，j(x_i-x_j)

a_i，j≤fg_i，j(x_j-x_i)

a_i，j∈{0，1}

其中，x_i為節點簇c_i的頭節點所屬于的顏色，fg_i，j為節點簇c_i和節點簇c_j之間的翻轉增益，a_i，j是最終實現的翻轉增益。