In this dissertation, we studied coded multicasting and coded computing for wireless edge processing systems. Coded multicasting (or Index coding) is a method, which serves users’ requests simultaneously via exclusive-or (XOR) operation leveraging the stored information at users. Since index coding can be interpreted as a kind of source coding, we reveal that the optimal index code should be dependent on the channel conditions, not simply on the number of transmissions. Then, we find the optimal index code and the optimal time allocation that minimizes the overall outage probability of the users. We found the optimal index code based on majorization theory and the Hasse diagram. On the other hand, coded computing is a method to allocate redundant computed tasks, to combat the bottleneck of distributed computing. First, from the structural insight of the Strassen algorithm and the aid of frame quantization theory, we propose a novel straggler mitigation scheme, which guarantees moderate performance even for the limited number of nodes. Second, we elaborate on how to distribute and reconstruct the matrix multiplication using the group theory and representation theory. Moreover, we derive the condition for perfectly reconstructing the original solution from the local computation results of the worker nodes.
본 논문에서는 무선 엣지 프로세싱 시스템의 통신 및 컴퓨팅 성능을 개선할 수 있는 유망한 기술들로써, 부호화 멀티캐스팅 및 부호화 컴퓨팅 기법을 연구한다. 부호화 멀티캐스팅(또는 인덱스 부호화) 기법은 사용자들에게 저장된 정보를 활용하는 배타적 논리합을 통해 동시에 사용자의 요청을 처리하는 방법이다. 본 논문에서는 소스 코딩의 한가지 방식으로 여겨지는 인덱스 부호화 기법이 무선 환경이 고려될 경우, 최적의 인덱스 부호화 기법은 무선 채널 조건에 따라 달라져야함을 보였다. 그 후 인덱스 부호화와 시간 할당량 간에 동시 최적화 방법을 제안하였다. 또한 메이저리제이션 이론 및 하세 다이어그램을 이용하여 저복잡도로 최적의 인덱스 부호를 찾는 방법을 제시하였다. 한편, 부호화 컴퓨팅은 분산 컴퓨팅에서 각 노드에게 분산 연산을 할당하고 받을 때, 연산 노드들의 정체 현상을 해결하기 위해, 추가적인 연산을 할당하는 방법이다. 기존 부호화 컴퓨팅은 대부분 부호이론 기반으로 연구가 진행되었는데, 본 논문에서는 원래 단일 연산 장치에서 행렬 곱의 연산 복잡도를 낮추기 위해 개발되었던 알고리즘들의 원리를 변형하여, 기존 부호화 컴퓨팅의 한계를 해결할 수 있는 새로운 알고리즘들을 제시하였다. 이러한 관점에서 첫번째로, 본 논문에서는 프레임 양자화 이론을 기반으로 하는 부호화 컴퓨팅 방식을 제안하였다. 제안 기법을 통해 노드 수가 매우 적은 환경에서도 어느정도의 에러율을 보장하는 분산 행렬 곱 방식을 제안하였다. 또 다른 방법으로, 기존 행렬 곱셈의 계산 복잡성을 줄이는 연구들로 영감을 받아, 군환 기반의 분산 행렬 곱셈 방법을 개발하였다. 군론과 표현론을 사용하여 행렬 곱을 분산하고 재구성하는 부호화 방법을 제안하였다. 또한 분산 노드들로부터 받은 결과로 원 결과를 완벽하게 재구성하기 위한 조건을 도출하였다.
