The 19th Intelligent System Symposium (FAN2009), Aizu-Wakamatsu, Sep.17-18, 2009 Embedded MCSoC Architecture and Period-Peak Detection (PPD) Algorithm for ECG/EKG Processing Let’s start. Good after noon everyone. My presentation title is Embedded MCSoC Architecture and Period-Peak Detection Algorithm for ECG/EKG Processing. ----- My name is Yasuyoshi Haga. I belong to the University of Aizu. Yasuyoshi Haga, Abderazek Ben Abdallah, Kenichi Kuroda School of Computer Science and Engineering, The University of Aizu, Japan Sep. 17, 2009 FAN2009
Outline Background Our proposal Preliminary Evaluation Conclusion Period-Peak Detection Algorithm System architecture Preliminary Evaluation Conclusion The Outline is Background, Our proposal, Period-Peak Detection Algorithm, System architecture, Preliminary Evaluation and Conclusion Sep. 17, 2009 FAN2009
Background (1/4) Heart period is important in medical care. Heart period is calculated from electrocardiogram (ECG/EKG) signal. Heart period is important in medical care. Heart period is calculated from electrocardiogram signal. This figure shows a typical ECG/EKG signal. This waveform is obtained from sensors on body. ---------------- 心臓周期は医療にとても重要です。 心臓周期は心電図から計算します。 図は心電図を表しています。 この波形は、体に取り付けたセンサから得た信号で構成されています。 voltage mV R Period R’ T T’ P U P’ U’ Q Q’ time s S S’ Sep. 17, 2009 FAN2009
Background (2/4) Heart period detection Heart period R R R mV s This figure shows heart period detection from the ECG/EKG waveform. For heart period detection, this algorithm detects R-peaks from the ECG/EKG waveform, and calculating interval between these peaks. But this algorithm has some problems. ---------------- 図は、現存のアルゴリズムでの心臓周期の計測を表しています。 心臓周期を計測するとき、現存のアルゴリズムでは波形中からRピークを探し出し、その間の時間を計算し、計測しています。 しかし、それでは問題があります。 Heart period R R R mV s Sep. 17, 2009 FAN2009
Background (3/4) Problems of period detection Faulty analysis R-R’ Interval False Interval This figure shows two main problems in the period detection. First is R-R’ interval. This problem is misdetection of R and R’ peaks, leading to a wrong period between these peaks. Second is R-T interval. This problem is wrong period detection of R and T peaks. ------------------------- この図は従来のアルゴリズムの問題を表しています。 2つの主な問題があります。 1つはR-Rインターバルです。 この問題は、2つに分かれたRピークを別々に検出し、Rピークともう一つの間を計算してしまうことです。 もう一つの問題はR-Tインターバルです。 この問題は、T波をピークと誤って検出し、RピークとTピークの間を計算してしまうことです。 このプレゼンテーションではこれらの問題のソリューションを提供します。 R-T Interval R’ R False Interval R mV T True Interval True Interval t Sep. 17, 2009 FAN2009
Background (4/4) ECG/EKG is an essential tool in heart medicine. Problems Long time for analysis Analyze huge amount of data Insufficient accuracy Noisy and complicate waveform Large and heavy systems Targets Real time analysis High accuracy Portability ECG/EKG is an essential tool in heart medicine. Especially, analysis of 12-lead signals is very important in ECG/EKG. For example, the Pan-tompkins Algorithm and so on, have been used for long time. But existing systems still have many problems. The three main problems are: Long time for analysis, Insufficient accuracy and Large and heavy systems. So, we focus on three targets for there problems solutions. Those targets are: Real time analysis, High accuracy and Portability. -------------------- ECG/EKGは心臓治療において必要な課題です。 特に、12leadの分析はECG/EKGにおいてとても重要です。 そのため今までに様々な研究がされてきました。 例えば、QRSコンプレックスや、パン-トンプキンス アルゴリズムなど。 しかし、既存のシステムはまだ多くの問題を持っています。 主な3つの問題は、 ・分析が長い ・不十分な精度 ・大きく重いシステム なので、これらの問題を解決するため、3つの点に着目した。 それらの点は、 ・リアルタイム分析 ・高い精度 ・携帯性 Sep. 17, 2009 FAN2009
Our proposal (1/2) Hardware Implementation Real time analysis High accuracy Portability To solve these problems, the hardware implementation is one of appropriate approaches. Our proposal is implementation in MultiCore System-on-a-Chip architecture for there solutions. ---------------------------------- 私たちの提案は、これらの解決方法をMultiCore System-on-a-chipで実現することです。 Hardware Implementation MultiCore System-on-a-Chip architecture (MCSoC) Sep. 17, 2009 FAN2009
Our proposal (2/2) MCSoC part Signal reading Filtering Display ADC 1 ADC 12 FIR 1 FIR 12 SDRAM MCSoC ECG Analysis Signal reading Filtering Display A typical 12 leads Heart period Peaks Waveforms This figure shows our system. This part is MCSoC part. Next, I explain about analysis algorithm and hardware architecture for our system in my presentation. -------- 図は、私たちのシステムです。 この部分がMCSoC部分です。 このシステムによって、複数のECG/EKG信号データを、リアルタイムに分析することができます。 以降のプレゼンテーションでは、このシステムの分析アルゴリズムとハードウェア構成について説明します。 Sep. 17, 2009 FAN2009
Contents Background Our proposal Preliminary Evaluation Conclusion Period-Peak Detection Algorithm System architecture Preliminary Evaluation Conclusion Next, I explain about period-peak detection algorithm. ---------- 次に、period-peak algorithmについて説明します。 Sep. 17, 2009 FAN2009
Filter (1/2) Signal reading Filtering Display Heart period Peaks ADC 1 ADC 12 FIR 1 FIR 12 SDRAM MCSoC ECG Analysis Signal reading Filtering Display A typical 12 leads Heart period Peaks Waveforms I explain about filter. ------------------------------------------- フィルタについて説明します。 Sep. 17, 2009 FAN2009
Filter (2/2) Filter is used for noise reduction. Muscle noise T-wave interference The filter module is Bandpass filter Based on digital FIR filter Filter is used for noise reduction. For example, muscle noise and T-wave interference. The filter module is Bandpass filter. This filter is based on digital FIR filter. This mathematical formula is difference equation of digital filter. --------------------------------------------------------------------- フィルタはノイズ除去に使用されます。 例えば、筋音障害やT波干渉。 フィルタモジュールはバンドパスフィルタです。 このフィルタはデジタルFIRフィルタを基準にしています。 この数式はデジタルフィルタの差分方程式です。 Sep. 17, 2009 FAN2009
Analysis algorithm Signal reading Filtering Display Heart period Peaks ADC 1 ADC 12 FIR 1 FIR 12 SDRAM MCSoC ECG Analysis Signal reading Filtering Display A typical 12 leads Heart period Peaks Waveforms Next, I explain about analysis algorithm. ---------------------------------- 次に、分析アルゴリズムについて説明します。 Sep. 17, 2009 FAN2009
Period-Peak Detection Algorithm (1/4) This algorithm is based on autocorrelation function (ACF). Peak detection Reading data This figure shows Period-Peak Detection Algorithm processing flow. The left part shows the “period detection” stage. This part consists of 4 phases. Reading data, Derivation, Autocorrelation and Find interval Reading data is read filtered the ECG/EKG signal data from memory. Derivation is emphasis of the ECG/EKG signal. Autocorrelation is calculating periodic of the ECG/EKG signal. Find interval is calculating interval of the ECG/EKG signal from calculated periodic. The right part shows the “peak detection” stage. This part consists of 3 phases. Calculate threshold, Find peaks and Store results Calculate threshold is calculating thresholds of peaks from the ECG/EKG signal. Find peaks are calculating peaks from threshold. Store results are to store result of this algorithm to memory. ----------------------------------------------- At first, I explain Reading data phase and Derivation phase. Next I explain about Autocorrelation as main part in my presentation. ---------------------------------------------- まずはじめに、Reading dataフェーズとDerivationフェーズについて説明します。 次に、プレゼンテーションのメインパートであるAutocorrelation について説明します。 Derivation Calculate threshold Autocorrelation Find peaks Find interval Store results Period detection Sep. 17, 2009 FAN2009
Period-Peak Detection Algorithm (2/4) -Derivation- Emphasis of the signal peaks Implementation with simple operations (-) This slide shows derivation phase. There are two purposes in derivation. One is emphasis of the signal peaks. Another one is implementation with simple operations. This mathematical formula is formula of derivation. ------ このスライドは微分フェーズを表しています。 微分は2つの目的があります。 ひとつは信号の最大を増幅することです。 もうひとつは、簡単な演算を実装することです。 この数式は微分の数式です。 Sep. 17, 2009 FAN2009
Period-Peak Detection Algorithm (3/4) –ACF– Periodicity analysis of signals This slide shows about autocorrelation. The purpose of autocorrelation is periodicity analysis of the ECG/EKG signals. This mathematical formula is original formula of autocorrelation function. ---------------------------- このスライドは自己相関について表しています。 自己相関の目的はECG/EKG信号の周期性を分析することです。 この数式は基本の自己相関関数の数式です。 Sep. 17, 2009 FAN2009
Period-Peak Detection Algorithm (4/4) –ACF– Modification for MCSoC implementation But the ECG/EKG filtered signal start from zero. So actually, range used for analysis is from zero to necessary number. Therefore, original formula is modifies this formula. Accuracy increases by the more the number of N, but also the number of operation increase. -------------------------------- しかし、フィルタ処理されたECG/EKGシグナルは0から始まるので、実際に分析に使用する範囲は0から分析に必要な数までです。 したがって、このような数式になります。 Nの数が多いほど正確性が増しますが、その分消費電力も増します。 Sep. 17, 2009 FAN2009
Calculation process of ACF (1/6) Assumption The ECG/EKG signals are 9 samples. 1 2 3 4 5 6 7 8 Next, I explain the calculation process of the ACF. This slide shows assumption of sample data. In this case, I calculate 9 samples. This table shows the data of signals. The range of N is from 0 to 8. Therefore, the mathematical formula is this. However, when n – L less than 0, then value of y is 0. -------------------------------------------------- 次に、ACFの計算過程を説明します。 ここでは、9サンプルのECGシグナルを評価することにします。 シグナルのデータは表の通りです。 Nの範囲は0から8までです。 そのため式は以下のようになります。 ただし、n-Lがマイナスの時yの値はゼロとします。 Sep. 17, 2009 FAN2009
Calculation process of ACF (2/6) When L is 0, that calculation part is this. enclosed in red line. Each number of upper parts are multiplied by lower parts after all addition. So, result of Ry[0] is fifteen. ----------------------------------- Lが0の時、赤線で囲まれた部分を計算します。 上と下のそれぞれの部分を掛けてその後全てを足します なので、Ry[0]の結果は15です 1 2 × 1 2 Calculation Sep. 17, 2009 FAN2009
Calculation process of ACF (3/6) When L is 1, result of Ry[1] is six. ----------------------- 1 2 × 1 2 Zero (n-L < 0) Calculation No calculation (n > 8) Sep. 17, 2009 FAN2009
Calculation process of ACF (4/6) When L is 2, result of Ry[2] is four. ----------------------------------------------------------------- 1 2 × 1 2 Zero (n-L < 0) Calculation No calculation (n > 8) Sep. 17, 2009 FAN2009
Calculation process of ACF (5/6) When L is 3, result of Ry[3] is ten. ------------------------------------------------------------------ 1 2 × 1 2 Zero (n-L < 0) Calculation No calculation (n > 8) Sep. 17, 2009 FAN2009
Calculation process of ACF (6/6) Results 1 2 1 2 3 4 5 6 7 8 15 10 This table and graph show result of calculation. ------------------------ Sep. 17, 2009 FAN2009
Calculation process of ACF (6/6) Results 1 2 1 2 3 4 5 6 7 8 15 10 From this graph, there is periodicities from 0 to 3 and from 3 to 6. ------------- このグラフより、0から3と3から6に周期性がある Period Period Sep. 17, 2009 FAN2009
Calculation process of ACF (6/6) Results 1 2 1 2 3 4 5 6 7 8 15 10 Therefore, this example has periodic every 3 data. ---------------------------- 従って、この例では3つのデータ毎に周期性がある Period Period Every 3 samples are periodic Sep. 17, 2009 FAN2009
Calculation process of peaks (1/3) Period detection Calculate threshold I explain the calculation process of peaks. This figure shows “peak detection” stage. This stage consists of three phases. Calculate threshold, Find peaks and Store results. Moreover “calculate threshold” step consists of two phases Find max peak and Configure threshold. After this, I explain calculation process of peaks. --------------------------- Find max peak Find peaks Configure threshold Store results Sep. 17, 2009 FAN2009
Calculation process of peaks (2/3) Step 1 Calculate threshold Period Step1 Calculate threshold. This figure shows result of “period detection” stage. First, max peak is found from the ECG/EKG signal. So, max peak is two. ------------------------- 1 2 Max peak = 2 Threshold = 1 Sep. 17, 2009 FAN2009
Calculation process of peaks (2/3) Step 1 Calculate threshold Period After then, threshold is set from max peak. In ECG/EKG waves with a normal, R wave is the biggest and T wave is second biggest. T wave peak is about half of R wave peak. So, in this case, I assume the threshold is 50% (fifty) of max peak. Therefore, threshold is one. ---------------------- その後、最大ピークからしきい値を設定します。 正常なECG/EKG波形において、R波が一番大きく、次に大きいのがT波です。 T波の最大はR波の約半分です。 従って、ここでは、最大値の50%を、しきい値と仮定します。 この仮定より、しきい値は1です。 1 2 Max peak = 2 Threshold = 1 50% Sep. 17, 2009 FAN2009
Calculation process of peaks (3/3) Step 2 Find the time slots and values of peaks Period Step2 Find the time slots and values of peaks Peaks are over the threshold from peaks in period. ------ 1 2 Over the threshold Max peak = 2 Threshold = 1 Sep. 17, 2009 FAN2009
Calculation process of peaks (3/3) Step 2 Find the time slots and values of peaks Period Therefore, these are peaks. -------------------- 1 2 Peaks Max peak = 2 Threshold = 1 Sep. 17, 2009 FAN2009
Contents Background Our proposal Preliminary Evaluation Conclusion Period-Peak Detection Algorithm System architecture Preliminary Evaluation Conclusion Next, I explain about system architecture. ---------------- Sep. 17, 2009 FAN2009
Processing phase Phase 1 Phase 2 Phase 3 Phase 4 Signal reading ADC 1 ADC 12 FIR 1 FIR 12 SDRAM MCSoC ECG Analysis Signal reading Filtering Display A typical 12 leads Heart period Peaks Waveforms This figure shows our system architecture. This part is multicore-system-on-a-chip based. This system consists of four phases. Phase 1 is signal reading. Phase 2 is filtering. Phase 3 is analysis. and Phase 4 is display. ------------------------------ Sep. 17, 2009 FAN2009
System block diagram (1/4) Shared Bus VGA Controller SDRAM FIR Filter ADC On-chip Memory CPU This figure shows system block diagram of our system. Cpu, on-chip memory, FIR filter and analog digital converter are consist of multiple core. The number of these cores are decided by the number of leads. -------------------- この図は私たちのシステムのブロックダイアグラムを表しています。 Cpu, on-chip memory, FIR filter, ADCは複数のコアで構成されています。 これらのコアの数はリードの数によってきまります。 Sep. 17, 2009 FAN2009
System block diagram (2/4) Shared Bus VGA Controller SDRAM FIR Filter ADC On-chip Memory CPU Phase 1 Reading data This part is Phase 1 of our system. This part is used for Reading data. This part consists of multiple CPU, multiple on-chip memory and multiple analog digital converter. ------------------------ Sep. 17, 2009 FAN2009
System block diagram (3/4) Phase 2, 3 Filtering and Analysis Shared Bus VGA Controller SDRAM FIR Filter ADC On-chip Memory CPU This part is Phase 2 and 3 of our system. This part is used for Filtering and Analysis. This part consists of multiple CPU, multiple on-chip memory, multiple filter, SDRAM controller and SDRAM. --------------- Sep. 17, 2009 FAN2009
System block diagram (4/4) Shared Bus VGA Controller SDRAM FIR Filter ADC On-chip Memory CPU This part is Phase 4 of our system. This part is used for Display the result. This part consists of multiple CPU, multiple on-chip memory, SDRAM controller, SDRAM, VGA controller and small VGA monitor. ------------------- Phase 4 Display Sep. 17, 2009 FAN2009
Contents Background Our proposal Preliminary Evaluation Conclusion Period-Peak Detection Algorithm System architecture Preliminary Evaluation Conclusion Next I talk about preliminary evaluation. ------------------------ Sep. 17, 2009 FAN2009
Dedicated logic registers Prototype Result Module Combinational ALUTs Memory ALUTs Dedicated logic registers Processor + on-chip memory 1,680 (1%) 0 (0%) 1,654 (1%) FIR filter 450 (<1%) 52 (<1%) 612 (<1%) Others 1,918 (2%) 96 (<1%) 1,937 (2%) Entire system 4,048 (4%) 148 (<1%) 4,203 (4%) This table shows prototype design result. Only one signal analysis is implemented in this design We used Altera Quartus II and SOCP builder to design. The target device is Altera Stratix III DSP board. For this table, prototype implemented small size. So, analysis module will implement in prototype. ------------------- このテーブルはプロトタイプの結果を表しています。 このデザインは一つのシグナルを処理するシステムです。 私たちはデザインに、Altera Quartus IIとSOCP builderを使用しました。 対象デバイスはAltera Stratix III DSP boardです。 テーブルより、プロトタイプは小さく実装できました。 なので、分析モジュールが実装できるでしょう。 ロジックエレメントにまだ十分余裕があることがわかります。 なので、この部分を利用して、分析アルゴリズム用のコアを実装することが可能です。 Prototyping board (Stratix III DSP board EP3SL150F1152C2) Sep. 17, 2009 FAN2009
System Block Diagram with Analysis Module Shared Bus VGA Controller SDRAM FIR Filter ADC Master Module Slave Module On-chip Memory CPU Hardware Accelerator (PPDA Module) This figure shows our system block diagram including the analysis module. When this analysis module is implemented, our system is able to process at high speed. ------------------ 図は、アルゴリズム用コアを実装した時のブロックダイアグラムです。 このコアを実装することで、処理を速くすることができるでしょう。 Sep. 17, 2009 FAN2009
Conclusion We proposed Embedded MCSoC Architecture for ECG/EKG processing. We implemented small Master Module. Conclusion We proposed Embedded MCSoC Architecture for ECG/EKG processing. And, we implemented a small prototype of the master module. Our future works are: Implementation of slave module in MCSoC. And complete all systems design and evaluation. ---------------------- 私たちはECG/EKG処理のための組み込みMCSoC構成を提案した。 そして、私たちは小さい主モジュールを実装した。 私たちの今後の仕事は、 私たちは副モジュールをMCSoCに実装できるでしょう。 そして、すべてのシステムデザインと評価を完成させます。 私たちのシステムのプロトタイプを制作してみたところ、空いているロジックエレメントが十分にあることがわかった。 ハードウェアリソースが十分あるのでアルゴリズム部分をハードウェア実装が可能であることがわかった。 今後は、アルゴリズム部分を含めたすべてのシステムを完成させ、検証していきたい。 Sep. 17, 2009 FAN2009
Thank you for listening That’s all. Thank you for listening. ---------------------- Sep. 17, 2009 FAN2009