隨著生理感測器與晶片的微型化，愈來愈多可攜式或穿戴式即時疾病與健康監測裝置系統及產品因而誕生。由於戴在使用者身上的裝置未必可以隨時聯絡到網路，因此當今之趨勢為邊緣運算，系統中的微處理器 (MCU、micro-controller)透過演算法計算後做當下診斷或監測。樣本熵(Sample entropy、SpEn)是一種量度時間序列的規則度或複雜度的一個方法。它自發展以來越來越受到關注而且已經成功應用到生物醫學與其它許多領域的即時監測。但是其(標準算法)計算複雜度(computational complexity)是O(n^2)，其中n是資料長度。因此計算是非常耗時的，無法在嵌入式系統(embedded system)上作即時計算(real-time 或online computation) ，因而妨礙它的許多應用。樣本熵的計算事實上為資訊科學中之計算幾何(computational geometry)中的正交範圍搜尋(orthogonal range search)問題。更精確地說它是在計算m維(與m-1維)嵌入式相空間(embedded phase space)中計算互為鄰居點之總數目。基於生物訊號大部分都是以有限解析度(R)之數位儲存的前提。本計畫在沒有其它假設下提出快速演算法，目標有二： 提出一個自適性 2^m元樹的線性快速演算法：此方法將改寫文獻上對此問題之最佳計算複雜度。令解析度為R，我們將證明其計算複雜度為線性O(kn)， k是log_2R與維度m的函數；且記憶體複雜度為也是線性。且此方法經稍微修正後也可適用無限解析度(實數)訊號。 樣本熵在MCU(micro controller)上作即時計算：加速運算達100倍(的數量級)，減少99%功耗。為了驗證所開發技術的實用性，本計畫將該演算法實現於MCU進行各種生理訊號之SpEn運算，包含中樞神經系統的整夜睡眠腦波，以及自主神經系統的心律變異分析。達到以樣本熵為作為特徵擷取之即時診斷疾病與監測健康狀態的邊緣計算能力。隨著智慧醫療研究與產品的發展需求，本計畫成果將兼具數值分析理論探討、智慧演算開發與嵌入式生理訊號邊緣計算應用等學術與實務目標。未來將可實際應用於多重訊號的狀態變化分析與相關產品的加值。 ;Sample entropy (SpEn) is a measure of underlying regularity or complexity of a system, which has received increasing attention in recent years and has been successfully applied in biomedical applications and others. However the standard implementation of SpEn requires computational complexity of O(n^2) (n is the data length), and is rather time consuming when applying to a long data set and imposes difficulties in real-time applications in embedded system. The computation of sample entropy is, in fact, is an orthogonal range search problem in the field of computational geometry in computer science. To be more specific, it is equivalent to count the total neighbors in m- (and m—1) dimensional embedded phase space. Because most of the biological signal is stored in finite resolution (R) format, it allows us to develop fast algorithm. In addition, the method can be applied to real signal after slightly modification. The goals of this proposal are: We will propose an adaptive 2^m-tree algorithm (AM-tree). The computational complexity of this algorithm is faster than any of algorithms in the literature. Let R being the resolution of the signal. We will prove that the method is with O(kn) linear computational complexity and linear memory. The parameter k is function of log_2Rand m. We will execute the developed algorithms in a micro-controller (MCU) for real-time illness detection and health monitoring. The algorithm will speed up the execution time by a factor of 100 and save 99% power consumption. We will use a whole night brain wave and HRV signals as examples to demonstrate the efficacy of the proposed algorithm
