ON THE COMPLEXITY OF GENERATING FORNEY’S CODES

Abstract

Concatenated codes are code constructions made of two codes called the inner code and the outer code [1]. The outer code is usually asymptotically good code over a large alphabet m q F , like the Reed-Solomon code. If a greedy code is used as an inner code, then, following the terminology from [2], we call these coНОs FornОв’s МoНОs. In [2], it is suggested that the best МoНО Тn АoгОnМrКПt’s ОnsОmЛlО should be used as an inner code; thus lowering the complexity on finding a good inner code. In this paper we present four greedy algorithms that can be used to produce the inner code. Some of these algorithms have lower time complexity than finding the best code in the АoгОnМrКПt’s ensemble.