[發明專利]分類電路和方法

無效

• 申請號: 201110346147.2
• 申請日: 2011-11-04
• 公開（公告）號: CN103092812A
• 公開（公告）日: 2013-05-08
• 發明（設計）人: 胡伯特斯·杰拉德斯·亨德里克斯·維梅倫;簡·斯特庫拉特;安德烈·克林·尼由蘭德;伊麗莎白·弗蘭西卡·瑪麗亞·斯特芬斯
• 申請（專利權）人: NXP股份有限公司
• 主分類號: G06F17/00
• 分類號: G06F17/00
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 王波波

技術領域

本發明涉及用于對數據值集合進行分類(sort)的電路。

本發明還涉及使用這種電路對數據值集合進行分類的方法。

背景技術

當前，許多電子系統必須能夠以魯棒和容錯的方式處理同時傳輸的大量數據。這些需求例如在應用領域中非常重要，在這些應用領域中，復雜系統的糾錯功能取決于該復雜系統中包含的電子系統的無故障操作。這種復雜系統的示例包括在錯誤操作時可能會危害操作該系統的人的安全的那些系統，例如車輛。由于這個原因，使得電子系統花費很長時間才能夠管理這種復雜系統的關鍵功能，例如，這種關鍵功能的非限制性示例是線控飛行(fly-by-wire)和線控駕駛(drive-by-wire)。

但是，不斷增加的實現復雜功能的電路能力近來呈現出對在復雜系統中賦予多種或多或少的關鍵功能操作的電子設備正趨于更易被接受的態度。例如，在汽車工業中，正在持續努力為車輛提供標準化電子控制網絡，由于網絡多個組件之間的通信協議可以是標準中定義的，所以可以更容易的為這種標準化網絡設計附加功能。這種車載網絡通信協議的示例是FlexRay^TM協議，可以在www.flexray.com找到該協議的描述。

提供魯棒和容錯的車載網絡的一個主要挑戰是，網絡可能包括大量離散和獨立的組件，這些組件可能需要以同步的方式彼此通信。為此目的，可能需要定義通信周期，但是，對每個這些獨立的組件同時初始化其通信周期是具有挑戰性的任務。

在FlexRay^TM中采用了多主控(multi-master)分布式時鐘同步機構，其中多達15個主控組件發送同步消息，每個節點基于接收這些同步消息來調整他們對全局時間的局部視圖。但是，由于這些消息的某一些可能遭受某些形式的訛誤，例如不期望的延遲，每個節點基于容錯中點算法(FTMA)實施投票機制。在FTMA中，丟棄p個最高值和p個最低值，之后根據q個最高的剩余值和q個最低的剩余值，針對剩余值的集合，計算平均值，這里p是非負整數，q是正整數。FTMA也可以在FlexRay^TM內或外的其他應用中，在這些應用中有必要通過例如多數投票的方式實現容錯。

與實現FTMA相關的實際問題是在硬件需求方面很昂貴。由于FTMA依賴于分類(sorting)算法識別p+q個最高值和p+q個最低值，當前FTMA的實施可能依賴于提供可以存儲所有接收的要被分類的值的存儲器，以及操作存儲器中存儲的數據集合以識別最高值和最低值的集合、根據FTMA計算該集合的平均值的微控制器。對于大的數據集合，這可能需要非常大的存儲器，其可能由于成本和/或可用硅面積等因素而不可行。此外，分類必須在后處理步驟中進行，例如在已經接收到所有數據值之后進行，這可能導致大數據集合的處理時間長得不可接受，特別是在必須對大量數據求平均，和/或數據具有較大的值，例如由大量比特表示的情況下。

發明內容

本發明提供一種用于對數據集合進行分類的電路，該電路在面積和吞吐時間方面更高效。

本發明還提供使用這種改進電路對數據值進行分類的方法。

根據本發明第一方面，提供了一種對數據值集合進行分類的電路，該電路包括：具有p+q個寄存器的第一集合，用于對包含p個統計野值的數據值集合的p+q個最大數據值進行存儲；具有p+q個寄存器的第二集合，用于對p+q個最小數據值進行存儲，其中p是非負整數，q是正整數；控制器，耦合到第一和第二集合中的每個寄存器，所述控制器布置為接收數據值集合，以及針對每個數據值獲取該數據值與每個寄存器中相應數據值進行比較的結果；以及根據比較結果更新寄存器；該電路進一步包括數據處理電路，其耦合到第一和第二集合中的至少q個寄存器，用于響應于所述控制器，處理每個寄存器中存儲的數據值中的至少一個。

本發明基于容錯分類算法(例如FTMA)的實施，而不需要像通常那樣存儲所有數據值，而是只有少量數據值用于產生處理的數據值，例如平均值、和值、差值等等。因此，通過提供組合大小典型地實質上小于要平均的數據值集合中的數據值總數的兩個寄存器集合，可以在接收的數據值和已經存儲在寄存器中的數據值之間進行運行中(on-the-fly)比較，從而使得一旦接收到最后的數據值，則幾乎可以立即獲得分類結果。因此，由于實際上僅存儲輸入數據值總數量的一部分，本發明的電路提供了這種分類算法的更緊湊的實施，同時，由于是在數據值接收過程中而不是在接收之后進行數據值分類，因而大大改善了吞吐時間。相比于這種分類算法已知的實施方案，本發明進一步具有明顯的功率節省的效果。