디지털 통신 시스템의 Error-correcting code는 다음과 같다. $RSyndrome checkingCyclic Redundancy Check (CRC)Applications: Automatic Repeat reQuest (ARQ) 가장 나이브한 방법은 Message size를 알고 그에 따른 codeword를 알고 있을 때, received된 codeword와 table에 있는 codeword의 유사도를 비교하는 방법이다.위 방법은 $2^3$개의 table row를 요구하기 때문에, k이 작은 경우에만 사용할 수 있다. 유사도는 어떻게 비교할까?Hamming distance : 다른 bit의 수를 세기Hamming weight : nonzero bit의 수를 세기Binary case : $d..

통신 시스템에서 중요한 개념 중 하나는 "Channel capacity"이다. Channel capacity란 통신 채널을 통해서 안전하게 전달될 수 있는 데이터의 최대 비율을 의미한다. 통신이란 A가 B에게 message를 전달하는 행위를 말하며, B가 A가 보낸 message를 정확하게 복원할 수 있으면 통신이 성공했다고 말할 수 있다. 이때 간섭이나 공격에 의해 message는 변조가 될 수 있어, B에서 복원할 수 있음이 중요한 요소로 작용한다. Channel capacity는 이런 에러가 작은 통신에서 최대로 전송할 수 있는 데이터 양이라고 생각하면 된다. Channel codes는 channel capacity만큼의 통신을 가능하게 해주는 code라고 보면 된다. 1. Discrete Memo..

Coding은 데이터 압축, 암호화, 오류감지 및 수정, 데이터 전송 및 저장에 사용되는 이론이다. 주된 목적은 데이터의 패턴을 분석해서 압축하여 통신을 가능하게 하는 것이다. 1. Source coding: Data compression데이터 압축의 목적으로 사용되는 coding의 경우, 가장 빈번하게 나오는 결과에는 짧은 표현을, 가장 덜 발생하는 결과에는 상대적으로 긴 표현을 주어 압축한다.(ex. 모스 부호가 한국인에게는 가장 유명하다) DefinitionsSource code란 부호화된 데이터라고 보면된다.$c(x)$ : codeword of x$l(x)$ : $c(x)$의 길이$D*$ : D-ary alphabet으로 만들 수 있는 source code의 집합 (유한한 길이) Code를 평가하..

Real-time OS에 대한 소개와 Static RTOS, UNIX-like RTOS에 대해 다룬다. 1. RTOS?Predictable + well structured real-time application의 구현을 간단하게 해주는 resource management + abstraction을 RTOS라고 한다.Predictable : worst-case delay를 statically determine할 수 있음Resource management & abstraction : 제한적인 HW 자원을 multiplexing + 일관된 interface General purpose PC와 다른 점은 크게Full control (no kernel-level)Compile time에 시스템 config. 결정..

Uniprocessor(가정)에서 하나의 system 내에 서로 다른 중요도를 가진 system이 있을 때, 스케쥴링하는 방법에 대한 설명이다. 가령 자율주행 차량의 ABS와 스테레오 음향 시스템을 생각해 보면, ABS가 훨씬 중요함을 알 수 있다. WCET에 대한 정의도 다를 수 있다. Certification requirements가 다를 경우, 동시에 진행되는 task임에도 다른 WCET 측정 방법이 진행된다. 현재 주로 사용 중인 방법은 space-time partitioning으로 각 서브시스템 마다 time slot을 할당해 관리하고 있다. (Isolation을 통한 분석이 진행되었다.) 다만, High criticality system의 경우, 너무 보수적으로 WCET를 측정하다 보니, WC..

앞에서는 uniprocessor 환경이었고 이제는 multiprocessor 환경이다. Multiprocessor에는 칩 성능에 따라 크게 3가지 종류가 있다.identicaluniform heterogeneousunrelated heterogeneousSpeed : 동일Capability : 동일Speed : 다름Capability : 동일Speed : 다름Capability : 다름 Multiprocessor 환경에서 스케쥴링이 어려운 이유는 task마다 한개의 processor를 사용하기 때문이다. 대표적으로 두 가지 스케쥴링 방식이 있다.Partitioned schedulingTask가 statically 코어에 할당됨코어 당 하나의 ready queue가 있음Uniprocessor schedul..

Priority inversion 문제와 이를 해결하기 위한 동기화 프로토콜에 대한 설명이다. 1. Priority InversionPriority-based preemptive scheduling에서 priority는 task의 중요도나 긴급하게 실행해야 함을 의미한다. Priority inversion은 high priority task가 low priority task에 의해 실행이 되지 못하는 경우를 말한다. 대부분의 경우 해로운 것은 아니나, 특정 상황에서 심각한 지연이 발생할 수 있다. Shared resource에 대한 mutex나 non-preemptive sub-system access와 같은 이유로 발생할 수 있다. 가령 화성의 패쓰파인더는 이 문제로 제어 불능 상태에 바졌던 적이 있다..

스케쥴링 가능성을 분석하는 방법에 대해 배운다. 또한, 이론적으로 가능하더라도 현실적으로 불가능할 수 있다는 사실을 알아야 한다. 우선, 스케쥴링 분석 여부에 따라 Exact와 Only sufficient로 나뉘게 된다.Exact : 모든 Task가 스케쥴링 가능하며, analysis 가능함Only Sufficient : 일부 Task가 스케쥴링 가능하며, analysis 가능함 보다 쉬운 이해를 위해 지금부터는 다음의 가정을 사용한다. 반대로 말하면, 다음의 내용이 실제 구현에 있어 고려할 내용임을 의미한다.Single processorHard deadlineIndependent periodic tasks$d_i = p_i$PreemptableNo overhead for context switch 1...

Set of tasks가 deadline과 함께 주어지면, real-time scheduling을 통해 policy에 따라 computing 자원에 task를 할당하게 된다. 목표는 deadline을 최대한 충족하는 것이다. 스케쥴링 알고리즘을 제안할 수도, 스케쥴 가능성(schedulability)을 분석할 수도 있다. Schedulability란 real-time 시스템이 모든 task의 deadline을 충족시킬 수 있는 지를 의미한다. 이를 만족하기 위해 스케쥴링을 통해 task의 실행 순서를 결정한다. 1. Priority-based 스케쥴링Task-level fixed-priority (TFP) 스케쥴링 : 각 task에 고정된 priority 부여Job-level fixed-priority ..