-
Wireless Digital Communication 1
서론 무선 통신 시스템은 현대 사회에서 없어서는 안될 시스템입니다. 음성 통신을 위한 휴대전화부터 인터넷을 사용하는 것까지 저희가 실생활에서 겪는 수많은 일에 무선 통신이 반드시 필요합니다. 그렇다면 어떻게 A라는 사람이 전송한 데이터가 수백 km 떨어져있는 B라는 사람에게 정확하게 도착할 수 있을까요? 앞으로 오랜 시간에 걸쳐서 이 질문에 대한 대답을 해보려고 합니다. 이 시리즈가 총 몇 개의 글로 이루어질지는 정확히 예측이 안되지만, 최종적으로는 현재 LTE, 5G 시스템에서 사용되는 OFDM 방식을 설명하는 것을 목표로 하고자합니다. 우선 첫 글에서는...
-
Incremental Topological Ordering and Strong Component Maintenance
Incremental Topological Ordering and Strong Component Maintenance 방향 그래프 $G$ 에 대해서, $G$ 의 위상 정렬 $O: V \rightarrow [n]$ 은 모든 간선 $u \rightarrow v$ 에 대해서 $O(u) < O(v)$ 가 성립하는 순열로 정의된다. $G$ 의 위상 정렬이 존재하기 위해서는 $G$ 가 사이클이 없어야 한다는 사실이 잘 알려져 있다 (Directed Acyclic Graph, DAG). 위상 정렬은 방향 그래프에서 사용하는 가장 기초적인 알고리즘 중 하나이다. 그래프는 일반적으로 순서가 없이 표현되는데, 문제를 풀거나 처리를 하는 데 있어서...
-
Breaking Python random module
서론 PlaidCTF 2021에서 Fake Medallion 이라는 문제가 나왔습니다. 문제를 푸는 과정은 다음과 같았습니다. Qubit 30개가 |0>, |1>, |+>, |-> 4개 중 하나의 state로 존재합니다. 각 qubit마다 여분의 빈 2개의 qubit이 주어지는데, quantum teleportation과 probabilistic quantum cloning을 통해서 이 stage를 통과할 수 있었습니다. (자세한 설명은 이 글의 주제가 아니라서 생략하겠습니다.) Qubit 30개를 초기화할 때 Python random 모듈의 random.getrandbits(30)을 사용합니다. 한 번 1번 stage를 성공하면 이 값들을 수많이 받아올 수 있습니다. 이 값들을 모은 뒤 다음 random.getrandbits(30)을...
-
Small To Large Merging
Small To Large Merging “작은거를 큰거에 합친다”, 이름만 들으면 무엇인지 유추가 잘 되지 않습니다. 하지만 알고리즘을 공부하는 사람이라면 한 번쯤은 간접적으로라도 접한적이 있을 것입니다. 바로 Union Find의 Union by size에서 시간복잡도를 보장하기 위해 쓰이기 때문입니다. 알고리즘에서 소개한대로 작은 집합을 큰 집합에 합친다면 한번의 Find 연산이 $O(\log N)$만큼 걸린다는 것이 증명되어 있습니다. 이 글에서는 Small to Large Merging을 소개하면서 왜 이런 시간복잡도가 보장되는지 알아보고, 응용되는 문제의 풀이를 설명하겠습니다. 간단한 문제를 하나 풀면서 시작하겠습니다. 무작위의 수가 1개씩...
-
CORDIC(Volder's Algorithm)
자주 있는 일은 아니지만, 살면서 적어도 한 번쯤은 삼각함수를 사용하는 코드를 작성해야 할 일이 있을 것입니다. C++의 math.h 헤더나 Python의 math 모듈같이, 대부분의 언어에서 삼각함수를 비롯한 여러 기능을 지원하는 수학 라이브러리가 기본으로 제공됩니다. >>> from math import * >>> sin(1) # usage of sin function in Python 0.8414709848078965 그런데, 주어진 각도가 $ \pi/6 $, $\pi/4$, $\pi/3$과 같이 딱 떨어지는 특수각이 아닐 때에도 컴퓨터는 어떻게 삼각함수의 값을 구할 수 있는 걸까요? 위 예시에서 $\sin 1$의 값은...