Bài giảng Xử lý ảnh - Chương 9: Lý thuyết hệ thống tuyến tính

113 PHẦN HAI Ch­¬ng 9 LÝ THUYẾT HỆ THỐNG TUYẾN TÍNH 9.1.GIỚI THIỆU Trong các chương trước, chúng ta đã nghiên cứu một vài tác dụng của các phép toán xử lý ảnh nào đó trên các ảnh. Những kết quả này có thể được giải thích bằng các phép toán đơn giản. Vì thế, chúng ta không đề cập đến các kết quả lấy mẫu, độ phân giải không gian hay các phép toán phổ biến được nói đến như tăng cường ảnh (image enhancement). Trong phần 2, chúng ta sẽ đưa ra những câu hỏi về vấn đề lấy mẫu, độ phân giải và lọc tuyến tính, một phương pháp tiếp cận phổ biến sử dụng cho việc tăng cường ảnh. Trong chương này và chương tiếp theo, chúng ta sẽ trình bày những công cụ phân tích yêu cầu cho công tác tiếp cận các vấn đề. Lý thuyết hệ thống tuyến tính là một lĩnh vực được phát triển toàn diện thường được sử dụng để mô tả hoạt động của mạch điện và các hệ thống quang học. Nó cung cấp một cơ sở toán học vững chắc để nghiên cứu các kết quả lấy mẫu, lọc và độ phân giải không gian. Lý thuyết hệ thống lấy mẫu cũng hữu dụng trong nhiều ứng dụng khác. 9.1.1.Định nghĩa Trong nội dung của cuốn sách này, chúng ta coi một hệ thống là một cái gì đó đảm nhận một đầu vào và tạo ra một đầu ra tương ứng. Bởi vì chúng ta chỉ quan tâm tới mối quan hệ giữa đầu vào và đầu ra, nên chúng ta phải để ý chút ít đến những gì nằm bên trong hệ thống. Đầu vào và đầu ra có thể là một chiều, hai chiều hay nhiều chiều hơn. Tuy nhiên, trong việc phát triển ban đầu, chúng ta hạn chế các ví dụ ở hai trường hợp: các hàm một chiều về thời gian và các hàm hai chiều của các biến không gian. Điều này giữ cho ký hiệu đơn giản hơn và làm cho các phép phân tích có phần dễ hiểu hơn, vì sự phát triển bị các quá trình vật lý thực sự ràng buộc. Phép phân tích có thể được tổng quát hoá một cách dễ dàng với số chiều cao hơn khi cần thiết. Trong phần đầu của chương này, sự trình bày được thực hiện cho các hàm một chiều theo thời gian và tổng quát hóa đối với các ảnh hai chiều. Hình 9-1 và 9-2 cho thấy ký hiệu quy ước cho các hệ thống tuyến tính một hoặc hai chiều. Trong mỗi trường hợp, đầu vào hệ thống là một hàm một hoặc hai biến và nó tạo ra một hàm đáp ứng một hoặc hai biến tương tự từ hệ thống. 114 HÌNH 9-1 Hình 9-1 Ký hiệu hệ thống tuyến tính HÌNH 9-2 Hình 9-2 Hệ thống tuyến tính hai chiều Tính tuyến tính. Các hệ thống tuyến tính có một đặc điểm mà đặc điểm này tạo ra tên gọi của chúng. Giả sử rằng, đối với một hệ thống riêng lẻ, một đầu vào x1(t) tạo ra một đầu ra y1(t): )()( 11 tytx  (1) (Mũi tên đọc là “gây ra”) Cũng giả thiết rằng đầu vào thứ hai x2(t) tạo ra đầu ra y2(t): )()( 22 tytx  (2) Hệ thống là tuyến tính nếu và chỉ nếu nó có đặc tính )()()()( 2121 tytytxtx  (3) Tức là, tín hiệu đầu vào thứ ba là tổng của hai tín hiệu đầu tạo ra một tín hiệu đầu ra là tổng của hai tín hiệu ra ban đầu. Bất kỳ một hệ thống nào mà không tuân theo quy tắc này đều là phi tuyến. Phân tích hệ thống phi tuyến tạo ra nhiều kết quả trong các lĩnh vực khác nhau. Tuy nhiên, sự phân tích hệ thống phi tuyến phức tạp hơn nhiều so với sự phân tích các hệ thống tuyến tính và mục đích của chúng ta không đòi hỏi phức tạp thêm. tuy nhiên, chúng ta sẽ giới hạn vấn đề phân tích hệ thống tuyến tính của chúng ta. Định nghĩa hệ thống tuyến tính chỉ rõ rằng một đầu vào là tổng của hai tín hiệu tạo ra một đầu ra tổng của hai đầu ra, mà hai đầu ra này được tạo ra bởi mỗi một tín hiệu đầu vào hoạt động riêng lẻ. Từ đó, nếu một tín hiệu đầu vào được nhân với một số hữu tỷ (rational) thì đầu ra sẽ tăng hay giảm cùng một hệ số, tức là, )()( 11 taytax  (4) Ta coi nó như một tiên đề mà biểu thức (4) cũng đúng cho các số vô tỷ (irrational). 115 Tính chất được định nghĩa trong các biểu thức (1), (2), (3) và kết quả suy ra của nó trong biểu thức (4), phục vụ cho việc định nghĩa hệ thống tuyến tính. Khi sử dụng lý thuyết hệ thống tuyến tính để phân tích một quá trình, điều cần thiết để quá trình sẽ được mô hình hoá, ít nhất cũng phải xấp xỉ, là tuyến tính. Nếu hệ thống đang được nghiên cứu không đáp ứng tiêu chẩn tuyến tính, thì nó là phi tuyến và lý thuyết hệ thống tuyến tính sẽ tạo ra các kết quả sai và có thể làm cho sai lệch. Nếu hệ thống chỉ phi tuyến một chút thì nó có thể được giả thiết là tuyến tính để phục vụ cho mục đích phân tích, nhưng các kết quả phân tích sẽ chỉ gần đúng với giả thiết. Thường thường, các hệ thống gần phi tuyến được nghiên cứu bằng lý thuyết hệ thống tuyến tính bởi vì cách tiếp cận này dễ điều khiển một cách chính xác. Tuy nhiên, người ta thường phải cẩn thận khi giải quyết các hệ thống phi tuyến bởi vì lớp bảo vệ của lý thuyết hệ thống tuyến tính tan rã như giả thiết về tính tuyến tính. Nhà phân tích có trách nhiệm không những chỉ về toán học mà còn về giá trị của những giả thiết bên dưới. Bất biến dịch. Một đặc điểm quan trọng mà một hệ thống nào đó đưa ra gọi là bất biến dịch (shift invariance). Nó được minh hoạ dưới đây. Giả sử, đối với một hệ thống tuyến tính đặc biệt mà )()( tytx  (5) Giả sử bây giờ chúng ta dịch chuyển tín hiệu đầu vào theo thời gian đi một lượng T. Hệ thống là bất biến dịch nếu )()( TtyTtx  (6) Tức là, đầu ra được dịch chuyển một lượng giống như đầu vào, nhưng mặt khác không bị thay đổi. Vì thế, đối với một hệ thống bất biến dịch, việc dịch chuuển đầu vào đơn thuần là dịch chuyển cùng một lượng đối với đầu ra. Điểm quan trọng là bản chất của đầu ra không bị thay đổi do bước dịch chuyển tín hiệu đầu vào. Bất biến dịch không gian là bất biến dịch thời gian tương tự hai chiều (two dimensional analog): nếu ảnh đầu vào được dịch chuyển liên quan đến ảnh gốc thì ảnh đầu ra cũng tương tự như ảnh trước. Hầu hết sự phân tích trong vài chương tiếp theo hướng về các hệ thống tuyến tính bất biến dịch. Các giả thiết về tính tuyến tính và bất biến dịch có giá trị gần đúng nhất đối với các mạng điện (electrical networks), các mạng điện tử tuyến tính được thiết kế hoàn hảo và các hệ thống quang học-các thành phần cơ bản của hệ thống xử lý ảnh. 9.2.TÍN HIỆU ĐIỀU HOÀ VÀ PHÂN TÍCH TÍN HIỆU PHỨC TẠP Theo cách sử dụng bình thường, các tín hiệu và các ảnh có thể được biểu diễn bằng các hàm thực của một và hai biến tương ứng. Giá trị hàm biểu diễn độ lớn của tham số vật lý nào đó, chẳng hạn như điện áp bằng hàm thời gian hay cường độ ánh sáng bằng một hàm hai toạ độ không gian. Tuy nhiên, sự phát triển các đặc điểm hệ thống tuyến tính tiến hành một cách trôi chảy hơn nhiều, nếu chúng ta cho phép đầu vào và đầu ra là các hàm phức. Bởi vì các hàm thực có thể xem là trường hợp đặc biệt của các hàm phức, mà không mất tính tỏng quát. sự thuận lợi trở nên rõ ràng trong suốt quá trình phát triển. 9.2.1.Tín hiệu điều hoà Xem xét một tín hiệu điều hoà có dạng )sin()cos()( tjtetx tj   (7) Trong đó f2 = -1. Gọi là tín hiệu điều hoà. Nó là hàm phức theo thời gian mà có thể xem xét như vec tơ đơn vị quay trong mặt phẳng phức với vận tốc góc  (Hình 9-3). Tần 116 số góc , đơn vị radian/giây, quan hệ với f, tần suất số vòng quay hay số chu kỳ trên giây (Herzt) bởi  = 2f. HÌNH 9-3 Hình 9-3 Vec tơ tạo ra tín hiệu điều hoà 9.2.2.Đáp ứng đầu vào điều hoà Giả sử một hệ thống tuyến tính bất biến dịch được cho với đầu vào điều hoà tjetx )(1 (8) Chúng ta có thể biểu diễn đáp ứng của hệ thống như sau tjetKty  ),()(1  (9) Trong đó tje tytK   )( ),( 1 (10) Là hàm phức của  và t được chọn sao cho khi nhân với ejt, sẽ được y1(t). Vì vậy, luôn có K(,t). Bây giờ giả sử chúng ta tạo ra tín hiệu đầu vào thứ hai bằng cách dịch x1(t). Sau đó, chúng ta có )()( 1 )( 2 txeeeetx TjtjTjTtj    (11) Lưu ý rằng x2(t) đơn thuần là x1(t) nhân với một hằng số phức. Điều này có được là do x1(t) là tín hiệu điều hoà. Đáp ứng của hệ thống tuyến tính với x2(t) bây giờ là )(2 ),()( TtjeTtKty   (12) biến đổi tjTj eeTtKty   ),()(2 (13) hay )(),()( 12 txeTtKty Tj  (14) Theo biểu thức (4), ta có thể viết 117 tjTjTj etKetyetxetx Tj   ),()()()( 112    (15) Từ biểu thức (8), chúng ta xem hệ số mũ bên phải như x1(t). Ngoài ra, chúng ta biết rằng đáp ứng của biểu thức (15) phải là y2(t), bởi vì nó là đáp ứng của hệ thống với x2(t). Vì vậy chúng ta có thể viết )(),()( 12 txtKety tTj  (16) Là biểu thức thứ hai đối với đáp ứng của hệ thống với đầu vào điều hoà được dịch chuyển. Biểu thức (14) thu được bằng cách chèn một độ dịch chuyển thời gian vào biểu thức (9). Biểu thức (16) có được từ đặc điểm tuyến tính của biểu thức (4). Tuy nhiên, cả hai biểu thức trên đều là đáp ứng của hệ thống đối với đầu vào điều hoà chuyển dịch theo thời gian: vì thế, chúng phải bằng nhau. Kết hợp biểu thức (14) và biểu thức (16) ta được )(),()(),( 11 txetKtxeTtK tTjtTj     (17) và rõ ràng là ),(),( tKTtK   (18) Phải đúng cho bất kỳ lượng chuyển dịch T nào. Tuy nhiên, biểu thức (18) chỉ có thể đúng nếu K(,t) độc lập với t. Vì vậy, biểu thức (9) có thể được viết lại dạng tổng quát như sau )()()( txKty  (19) Hàm tổng quát có dạng như giả thiết trong biểu thức (10) thành ra hàm duy nhất một biến tần số, . Biểu thức (19) chỉ rõ đặc điểm quan trọng mà đáp ứng của hệ thống tuyến tính bất biến dịch với đầu vào điều hoà được nhân với một số phức phụ thuộc tần số. Chú ý rằng đầu vào điều hoà luôn luôn tạo ra đầu ra đơn giản tại cùng một tần số. 9.2.3.Tín hiệu điều hoà và đường sin (sinusoid) Khi chúng ta sử dụng một hệ thống tuyến tính để mô phỏng hoạt động của một hệ thống vật lý thì các đầu vào và đầu ra được biểu diễn thuận tiện bằng các hàm thực. Vì thế, chúng ta có thể thêm một hạn chế khác vào hệ thống tuyến tính bất biến dịch sao cho chúng bảo toàn tính thực tế. Theo định nghĩa, điều này có nghĩa là một đầu thực chỉ có thể tạo ra một đầu ra thực. Từ đó, nó cũng có thể được xem là một hệ thống bảo toàn tính chất ảo và điều đó loại bỏ phần ảo của một đầu vào phức đơn thuần là loại bỏ phần ảo của đầu ra ảo tương ứng; tức là, )}({)}({)()( tyetxetytx  (20) Về một ý nghĩa nào đó, phần thực và phần ảo của một đầu vào điều hoà thực hiện các phần khác hệ thống một cách độc lập. Sự giới hạn phần thực trên các hệ thống tuyến tính cho phép chúng ta định rõ phép phân tích. Ví dụ, nếu đầu vào là hàm cosin, chúng ta có thể thêm thành phần hàm sin ảo để tạo thành tín hiệu điều hoà (Xem lại biểu thức (7)), xác định đáp ứng của hệ thống với đầu vào điều hoà, sau đó loại bỏ phần ảo của đầu ra phức. Cách tiếp cận gián tiếp này được chứng minh bằng một quá trình đơn giản hoá trực tiếp phép phân tích. Một tín hiệu sin bất kỳ có thể được xem như phần thực của một tín hiệu điều hoà duy nhất. Cách tiếp cận cho phép chúng ta xuất phát từ đáp ứng của hệ thống tuyến tính với tín hiệu sin bằng cách (1) biểu diễn tín hiệu sin đầu vào bởi tín hiệu điều hoà, (2) xuất 118 phát từ đáp ứng của hệ thống tuyến tính với đầu vào điều hoà, và (3) thực hiện phần thực để mang lại đầu ra thực sự. Theo cách thực hiện như vậy, chúng ta sẽ sử dụng phương pháp biến đổi để giải quyết; đó là, chúng ta biến đổi từ tín hiệu sin sang tín hiệu điều hoà, giải bài toán dưới dạng điều hoà, và sau đó biến đổi đầu ra điều hoà trở lại dạng sin. Kỹ thuật sử dụng logarit cho phép nhân là giống nhau: người ta biến đổi số nhân và số bị nhân sang logarit, cộng chúng vào kết quả phép nhân và sau đó biến đổi kết quả từ dạng logarit thành các số thập phân để có được tích số mong muốn. Giống như phép lấy logarit, phép biến đổi sang tín hiệu điều hoà làm đơn giản hoá một cách đáng kể phép phân tích hệ thống tuyến tính. 9.2.4.Hàm truyền đạt Hàm K() gọi là hàm truyền đạt của hệ thống tuyến tính và hoàn toàn có khả năng xác định rõ hệ thống. Đối với hệ thống tuyến tính bất biến dịch, hàm truyền đạt bao gồm tất cả những thông tin về hệ thống hiện có. Chúng ta có thể chuyển đổi K() về dạng cực để được )()()(  jeAK  (21) Trong đó A() hàm giá trị thực của tần số và số mũ phức là véc tơ đơn vị trong mặt phẳng phức – tức là, số phức có độ lớn đơn vị. Kết quả của hàm truyền đạt được minh hoạ dưới đây. Giả sử đầu vào là hàm cosin, biến đổi để được phần thực của tín hiệu điều hoà: }{)cos()( ttjeettx   (22) Đáp ứng của hệ thống đối với đầu vào điều hoà là )()()()(    tjttjjttj eAeeAeK (23) Cuối cùng, tín hiệu đầu ra thực là )cos()( )]}sin())[cos(({})({)( )(       tA tjtAeeAety tj (24) A() là hệ số tăng bội và biểu diễn mức độ mà hệ thống khuếch đại hay làm suy giảm tín hiệu vào. () là góc dịch pha. Kết quả duy nhất của nó là để dịch gốc thời gian của hàm vào điều hoà. Trong phần còn lại của quyển sách này. việc phân tích sẽ được thực hiện dưới dạng các tín hiệu điều hoà, với sự chuyển đổi thành tín hiệu sin như một bước thể hiện. Theo giả thiết, chúng ta đã trình bày ba đặc điểm quan trọng của hệ thống tuyến tính bất biến dịch: (1) Một đầu vào điều hoà luôn luôn tạo ra một đầu ra điều hoà ở cùng một tần số. (2) Hệ thống là hoàn toàn xác định bởi hàm truyền đạt của nó, hàm giá trị phức của tần số đơn lẻ. (3) Hàm truyền đạt chỉ tạo ra hai kết quả trên một đầu vào điều hoà- một sự biến đổi theo biên độ và một độ dịch chuyển pha (dịch chuyển theo gốc thời gian). 9.3.PHÉP TOÁN NHÂN CHẬP (CONVOLUTION OPERATION) Xét lại hệ thống đã cho trong hình 9-1. Nó sẽ có ích tạo ra một biểu thức quan hệ tổng quát giữa tín hiệu đầu ra, y(t), với tín hiệu đầu vào x(t). Chúng ta có thể nhận được sự quan hệ giống như trong cách dưới đây. Biểu thức hàm tuyến tính (tích phân chồng) 119      dxtfty )(),()( (25) Là đủ tổng quát để biểu diễn mối quan hệ giữa x(t) và y(t) đối với hệ thống tuyến tính bất kỳ. Hàm hai biến f(t,) có thể được chọn để khiến cho biểu thức (25) có hiệu lực đối với bất kỳ hệ thống tuyến tính nào; nhưng chúng ta thích biểu thị đặc điểm một hệ thống tuyến tính với một hàm duy nhất một biến. Bây giờ chúng ta lợi dụng sự bắt buộc bất biến dịch trong kết quả cuối cùng để đơn giản hoá biểu thức (25). Thay biểu thức (6) vào biểu thức (25) ta được      dTxtfTty )(),()( (26) Đổi biến bằng cách cộng thêm T vào cả t và . Kết quả là      dxTTtfty )(),()( (27) Nếu đem biểu thức (25) so sánh với biểu thức (27), ta thấy rằng ),(),( TTtftf   (28) Phải đúng với mọi T. Nghĩa là f(t,) không thay đổi nếu ta thêm một lượng như nhau vào cả hai đối số của nó. Nói cách khác, f(t,) là hằng số miễn là hiệu số giữa t và  là hằng số. Vì thế chúng ta có thể định nghĩa một hàm mới cho hiệu số duy nhất này là ),()(  tftg  (29) Và biểu thức (25) trở thành      dxtgty )()()( (30) Biểu thức này tương tự như tích phân chập (convolution integral). Nó biểu diễn bằng ký hiệu mà đầu ra của một hệ thống tuyến tính bất biến dịch được cho bởi nhân chập tín hiệu vào với hàm g(t) đặc trưng của hệ thống đó (hình 9-4). Hàm đặc trưng này được gọi đáp ứng xung (impulse response) của hệ thống. Chú ý rằng hệ thống bảo toàn tính thực tế nếu và chỉ nếu g(t) là hàm giá trị thực. Bây giờ chúng ta có hai cách để xác định rõ mối quan hệ giữa đầu vào và đầu ra của hệ thống tuyến tính bất biến dịch: (1) Mỗi hiển thị như trên có một hàm truyền đạt phức mà khi nhân với một đầu vào điều hoà, tạo thành một đầu ra điều hoà; và (2) mỗi hệ thống như trên cóa một đáp ứng xung thực mà khi nhân chập với tín hiệu đầu vào, tạo thành tín hiệu đầu ra. HÌNH 9-4 120 Hình 9-4 Hệ thống tuyến tính Bởi vì hàm truyền đạt và đáp ứng xung của hệ thống tuyến tính bất biến dịch là duy nhất và đầy đủ để xác định hệ thống một cách hoàn toàn, chúng ta nghi ngờ rằng hai hàm này có thể có liên quan với nhau. Mối quan hệ này được trình bày ở chương tiếp theo. 9.3.1.Nhân chập một chiều Tích phân chập trong biểu thức (30) có thể rút gọn bằng ký hiệu tắt sau xgy  (31) ở đây  dùng để ký hiệu cho phép nhân chập hai hàm. Hình 9-5 đưa ra đồ thị minh hoạ phép toán nhân chập. Một điểm trên đồ thị y(t) thu được theo cách sau đây. Một hàm g được phản ánh xung quanh gốc của nó và được dịch sang phải một khoảng t. Tích số từng điểm một của x và g đã phản ánh và dịch được thực hiện, và tích số đó được lấy tích phân để tạo ra giá trị đầu ra tại t. Quá trình này được lặp lại đối với tất cả các gía trị của t để tạo ra các điểm khác trên đồ thị ra. Khi t được biến đổi, hàm phản ánh được dịch thông qua hàm ổn định và giá trị của y(t) phụ thuộc vào lượng gối lên nhau của hai hàm. Phép toán nhân chập có một vài đặc điểm quan trọng. Thứ nhất, phép nhân chập có tính giao hoán; tức là, fggf  (32) Và chúng ta có thể phản ánh hàm khác và rút ra kết quả tương tự. Có thể viết như sau      dtgfgf )()( (33) Thay đổi các biến  ddxxttx  (34) Và sắp xếp lại để tạo ra     fgdxxgxtfgf )()( (35) Trong biểu thức (35), các cận phải được đổi chỗ cho nhau và được bù đối với dấu trừ trên d. Phép toán nhân chập cũng có tính phân phối, hfgfhgf  )( (36) Có thể viết lại      dhgxtfhgf )]()()[()( (37) Sắp xếp lại để tạo thành hfgf dhtfdgtfhgf         )()()()()( (38) 121 HÌNH 9-5 Hình 9-5 Nhân chập Phép nhân chập cũng có tính kết hợp, nghĩa là hgfhgf  )()( (39) Biểu thức này dành để độc giả tự kiểm tra. Phép đạo hàm bên dưới, ''][ gfgfgf dt d  (40) 9.3.2.Phép nhân chập một chiều rời rạc Chuỗi rời rạc có thể được nhân chập theo cách tương tự phép nhân chập các hàm liên tục. Biến độc lập trở thành một chỉ số và phép tích phân được thay thế bằng phép cộng. Bởi vậy, đối với hai chuỗi f(i) và g(i) có độ dài m và n, biểu thức tương đương với biểu thức (33) là   j jigjfigifih )()()()()( (41) Tạo ra chuỗi đầu ra có độ dài N = m + n - 1. Mặc dù nhân chập rời rạc và liên tục rất khác nhau, nhưng chúng có nhiều đặc điểm chung. Thật may mắn, với phép nhân chập rời rạc, chúng ta có thể thực hiện trên các ảnh số không mấy khó khăn, song song với phép nhân chập liên tục, mà có thể mô tả nhiều sự việc xảy ra đối với ảnh trước (hoặc sau) khi chúng ở dạng số. Điều này có thể được giải thích trong việc khôi phục ảnh, công việc này nhằm để đảo ngược lại kết quả của những ảnh hưởng suy biến đã tác động lên trên ảnh. 9.3.2.1.Công thức ma trận Đây là cách tiện lợi để biểu diễn các chuỗi rời rạc bằng các véc tơ và ký hiệu súc tích và các đặc điểm phát triển được cho bởi đại số tuyến tính. Mặc dù biểu thức (4) là tổng của các kết quả, nhưng phép nhân chập hai chuỗi không thể được thực hiện bởi phép nhân véc tơ đơn giản. Tuy nhiên, nó có thể được mô tả bằng một phép nhân ma trận nếu trạng thái được thiết lập một cách hoàn chỉnh. Đầu tiên chúng ta giả sử rằng f(i) thực sự là một phần chia của chuỗi có độ dài vô hạn tuần hoàn với chu kỳ N, độ dài của chuỗi ra trong phép nhân chập ở biểu thức (4). Bởi vì f(i) nhỏ hơn N nên cần phải điền thêm các phần tử có giá trị không (zero). Từ thêm (pad) được chọn để mô tả quá trình trên bởi vì quá trình tương tự sự chắp vá thêm vào quần áo người ta khiến cho nó trông có vẻ rộng hơn. Một chu kỳ của chuỗi vô hạn được cho bởi       Nim miif if p 0 1)( )( (42) 122 Chúng ta lặp lại cấu trúc này cho g(i) cũng như h(i). Bây giờ cả ba chuỗi có độ dài như nhau. Trong khi những lợi ích của sự phức tạp này có thể chưa rõ ràng, ít nhất cũng có thể thực hiện nó mà không mất tính tổng quát. Tiếp theo chúng ta cho f là véc tơ cột N  1 mà các phần tử của nó là fp(i), một chu kỳ của chuỗi vô hạn được hình thành từ f(i). Chúng ta cũng cho G là ma trận mà hàng thứ nhất của nó là chuỗi gp(i) thêm không được lưu trữ theo thứ tự đảo ngược. Các hàng tiếp theo sau của G được tạo thành bằng cách dịch phải các phần tử của hàng trước theo vòng tròn. Bây giờ chúng ta có thể viết       